2
$\begingroup$

Is it possible to hit point-at-infinity while performing scalar multiplication in Weierstrass curves?

According to this reply this is only possible when the scalar k is bigger then the order of the curve n. Is it so? If yes why?

$\endgroup$
  • 1
    $\begingroup$ Perhaps I'm late to the party, but in my answer $n$ is not actually the group order. It is the order of the point $P$. In that case, if $1\leq k\leq n-1$, $[k]P$ will indeed never be the point at infinity. $\endgroup$ – CurveEnthusiast Jun 30 '17 at 18:56
  • 1
    $\begingroup$ And to clarify, $n$ is by definition the smallest positive number such that $[n]P=\mathcal{O}$, from which the above claim follows. $\endgroup$ – CurveEnthusiast Jun 30 '17 at 18:59
  • $\begingroup$ I'm quite late to the party but if the question asks whether it is possible to hit the point at infinity as intermediate result of a scalar multiplication computation then the answers below are in general wrong as it really depends on the scalar multiplication algorithm you are using. Example: all methods from wikipedia initialize the temporary result to it. $\endgroup$ – Ruggero Jul 18 '17 at 14:42
6
$\begingroup$

Yes, it is possible.

The smallest scalar $k$ for which $[k]P = \infty$ is called the order of $P$.

For every non-zero point $P$ on the curve there is such a $k$.

This is simply due to the fact that there is only a finite amount of points so if you keep increasing $k$ at some point you must get a repetition $[k]P = [k-i]P$ for some $i$. Now $[k]P - [k-i]P = \infty \iff [i]P = \infty$.

No, $k$ does not have to be bigger than the group order $n$.

In fact for any prime $p$ dividing $n$ there is a point $Q$ such that $[p]Q = \infty$. This is Cauchy's theorem.

On the other hand Lagrange's theorem tells us that the order of every point divides the group order: $[k]P = \infty \Rightarrow k|n$. Therefore, if the group order $n$ is picked to be prime it follows that the order of every non-zero element is $n$.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ $\infty$ is zero. ;) $\endgroup$ – Elias Jun 30 '17 at 11:43
  • 1
    $\begingroup$ There are infinitely many positive $k$ such that $kP = 0$; the order of $P$ is the smallest such $k$, and the others are its positive multiples. $\endgroup$ – fkraiem Jun 30 '17 at 14:08
  • 1
    $\begingroup$ Oh yeah, good point! $\endgroup$ – Elias Jun 30 '17 at 15:11
  • $\begingroup$ Yes, of course there are, unless the number of points is prime. I'm not sure where your confusion comes from. This is basically exactly what Cauchy says. $\endgroup$ – Elias Jun 30 '17 at 15:27
  • 2
    $\begingroup$ No, there are plenty of curves with non-prime order. See galvatron's answer for an example. (And as long as the characteristic of the base field is not 2 or 3 every curve can be written in Weierstrass form.) $\endgroup$ – Elias Jun 30 '17 at 17:25
4
$\begingroup$

Not bigger, but bigger or equal (as the answer you refer to said). On curves with prime order you reach the point at infinity when the scalar $k$ is $k \geq n$, in fact when $k=n$ or it is a multiple of $n$, i.e. $k=\lambda n$. The order of an elliptic curve is defined as the number of distinct points on an elliptic curve $E$ including the point at infinity $\infty$. If the order of the elliptic curve is prime, then then $E$ is a cyclic group and any point on the curve can generate all distinct points on the elliptic curve, by performing point addition.

Point multiplication $kP$ is nothing but a lot of point additions (and doublings but let's assume only additions for the sake of transparency). Take the point $P$ for example on an elliptic curve $E$ of prime order $n$. By performing point multiplication which we said is just a lot of additions, i.e. $P+P+\dots$ you can get all points there are on the curve. After "a while", in fact exactly when you added $P$ to itself $n$ times (which is $nP$) you will get the point at infinity $\infty$. The next one would give you $nP + P = \infty + P=P$ which is $P$ again. This is called the identity law for elliptic curve groups.

|improve this answer|||||
$\endgroup$
1
$\begingroup$

The other answers have handled this correctly (yes, there is a $k$ such that $[k]P = \mathcal O$; no, $k$ can be less than the group order), so here's just an example to keep in mind for illustration, not for actual cryptographic use, taken from the non-free An Introduction to Mathematical Cryptography:

Let $E: y^2 = x^3 + 8x + 7$ over $\mathbb{F}_{73}$. There are $82$ points on this curve. So the only possible subgroup sizes are $2$ and $41$. Sure enough, if $P = (32,53)$, you have $[41]P = \mathcal O$, and $41 | 82$.

|improve this answer|||||
$\endgroup$

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.