1
$\begingroup$

I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book.

I have understood the algorithm itself, but unable to understand a specific point the book makes.

We are trying to factor 187.

We use $E: Y^2 = X^3 + 3X + 7 \bmod 187$ with $P = (38, 112)$

When we try to calculate $5P$, we have to calculate the inverse of 11 in 187, which we are unable to since 11 isn't coprime with 187 & hence we are able to find 11 as a factor of 187.

Upto this is clear. However, after this the books says

We examine more closely why we were not able to compute $5P$ modulo 187. If we instead look at the elliptic curve $E$ modulo 11, then a quick computation shows that the point $P = (38,112) \equiv (5,2) \pmod{11}$ satisfies $5P = \mathcal O$ in $E(\mathbb F_{11})$. This means that when we attempt to compute $5P$ modulo 11, we end up with the point $\mathcal O$ at infinity, so at some stage of the calculation we have tried to divide by zero. But here “zero” means zero in $F_{11}$, so we actually end up trying to find the reciprocal modulo 11 of some integer that is divisible by 11.

We have already factored 187 & found that 11 is one of the factors. So what is the point of computing $5P$ in $\mathbb F_{11}$. What insight does this give us?

$\endgroup$
2
  • $\begingroup$ My reading is that "We examine more closely" and the "quick computation" are not intended as steps in the algorithm. They are steps in the explanation of the algorithm. $\endgroup$
    – fgrieu
    Sep 15 at 11:35
  • $\begingroup$ @fgrieu - yes, I understand it's not a step in the algo. But I am unable to figure out what exactly it explains - that's the question $\endgroup$
    – user93353
    Sep 15 at 12:01
3
$\begingroup$

The quote invites computing $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{11}$ in order to experimentally come to the realization this is the point at infinity $\mathcal O$ (the neutral of point addition), and get the intuition that's why the computation of $5\,P$ on the Elliptic Curve of equation $E:\ Y^2\equiv X^3+3X+7\pmod{187}$ (as performed by the algorithm) yields a value that can't be inverted modulo $187$.

This all comes from the Chinese Remainder Theorem. Possible statements and consequences of that are: for $n=p\,q$ with $\gcd(p,q)=1$ (including $n=187$ , $p=11$ , $q=17$ as in the example)

  • Any quantity modulo $n$ can be equivalently computed modulo $p$ and modulo $q$.
  • The ring of integers modulo $n$, noted $\mathbb Z_n$, has a canonical isomorphism with $\mathbb Z_p\times\mathbb Z_q$.
  • For any integer $z$ in $[0,n)$ we can uniquely define $z_p=z\bmod p$ and $z_q=z\bmod q$, and then it holds $z=\left((q^{-1}\bmod p)\,(z_p-z_q)\bmod p\right)\,q+z_q$.
  • For a given Elliptic Curve of equation taken modulo $n$, and points $U$ and $V$ on that curve, if we can compute $U+V$ per the equations of point addition of an Elliptic Curve in a field, yielding $(X,Y)$ ; then we can equivalently do the same for the curves with the same equation taken modulo $p$ and modulo $q$ yielding coordinates $(X_p,Y_p)$ and $(X_q,Y_q)$ , then obtain $(X,Y)$ by twice applying the method in the above bullet point.
  • The above for point addition extends to point multiplication by an integer.

What insight does this give us?

We get the insight that by computing on an Elliptic Curve in the ring $\mathbb Z_n$ for $n$ of (initially) unknown factorization as if it was a field (it's not), we also managed to compute on an Elliptic Curve in the ring $\mathbb Z_p$ where $p$ is an (initially) unknown factor of $n$. And (still without a formal proof, but with an enlightening example) the reason the computation on a curve in $\mathbb Z_n$ hit a non-computable inverse is that the point at infinity $\mathcal O$ was reached on the curve in one of $\mathbb Z_p$ or $\mathbb Z_q$ (assuming $p$ and $q$ are prime, making $\mathbb Z_p$ and $\mathbb Z_p$ fields, and $\mathcal O$ on the corresponding curve well-defined).

This let us understand why the algorithm works, which in turn allows to reason about it and evaluate it's probability of success (that is of uncovering a non-trivial factor of $n$). When $n$ is the product of distinct primes $p_i$, that probability is the sum of the probabilities that the point at infinity is reached for one the curves for each of the $p_j$, minus the (very low) probability that it's hit simultaneously on all curves.

$\endgroup$
5
  • $\begingroup$ How is it concluded that the reason why the gcd did not return 1 is because $5P \bmod 11 = \mathcal O $? $\endgroup$
    – user93353
    Sep 16 at 8:17
  • $\begingroup$ For your point "For any integer $z$ in $[0,n)$ we can uniquely define $z_p=z\bmod p$ and $z_q=z\bmod q$, and then it holds $z=\left((q^{-1}\bmod p)\,(z_p-z_q)\bmod p\right)\,q+z_q$" - Where can I read more about this - is there any name for this relation - what should I search for? $\endgroup$
    – user93353
    Sep 17 at 5:26
  • $\begingroup$ @user93353: this is the formula used in RSA with CRT. It condenses the last formula in 1 and the last two in 2 there with $z$, $z_p$, $z_q$ (now lowercase) where they have $m$, $m_1$, $m_2$. Wikipedia has these. This formula is a little hard to devise but easily verified using the definition of the $\bmod$ operator. I know no source that cares to carefully make this proof. $\endgroup$
    – fgrieu
    Sep 17 at 5:48
  • $\begingroup$ @user93353: Ah, found the official name: generalized to an arbitrary number of factors of $n$, it's Garner’s algorithm. A source is the Handbook of Applied Cryptography, section 14.5.2. There's no proof, and it's not exactly as I state it, but still that's the closest I get. $\endgroup$
    – fgrieu
    Sep 17 at 6:09
  • $\begingroup$ Thank you so much $\endgroup$
    – user93353
    Sep 17 at 6:50

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.