0
$\begingroup$

Given a curve with points over GF(p), a subgroup of prime order q and a co-factor h.

How do I calculate the size of q which is also the modulus?

I was thinking q = p/h

$\endgroup$
1
$\begingroup$

Run Schoof's algorithm on the curve parameters to find $qh$, and divide by $h$.

The size $p$ of the coordinate field is only required, by Hasse's theorem, to be near $qh$, within a factor of a square root: $|qh - (p + 1)| \leq 2 \sqrt p$. Consequently, $p/h$ may be near $q$ but is not equal to $q$ except in anomalous curves in which ECDLP is easily solved by additive transfers as described by Smart (preprint), Araki–Satoh, and Semaev (the ‘Smart-ASS’ attack).

For example, Curve25519's coordinate field is $\operatorname{GF}(2^{255} - 19)$, and its order $2^{255} + 221938542218978828286815502327069187944 = qh$ where $q = 2^{252} + 27742317777372353535851937790883648493$ and $h = 8$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Could you explain why I cannot just divide by the co-factor? $\endgroup$ – WeCanBeFriends Apr 26 at 20:12
  • $\begingroup$ @WeCanBeFriends: divide what by the cofactor? You need to know the number of points on the curve (and while it'll be close to $p$, it won't be exactly $p$) $\endgroup$ – poncho Apr 26 at 20:21
  • $\begingroup$ Oh, I was referring to do p/h . TBC I have the order of the basefield p already $\endgroup$ – WeCanBeFriends Apr 26 at 20:33
  • $\begingroup$ @poncho To rephrase, given a group p, how do I find the largest subgroup? $\endgroup$ – WeCanBeFriends Apr 26 at 20:46
  • 1
    $\begingroup$ @WeCanBeFriends: do you mean the order of an elliptic curve based on $GF(p)$; no, in general, it wouldn't (but again, it would be close). Do you mean the order of the multiplicative group $\mathbb{Z}_p^*$? No, that'd be $p-1$. Do you mean the order of the additive group $\mathbb{Z}_p^+$? Yes, that would be (however, that group isn't typically used in cryptography, as things like the 'discrete log' problem (modular division) is easy $\endgroup$ – poncho Apr 26 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.