An Example
The following example is from Trappe & Washington (2006), with some details added.
We want to factor n=455839. Let's choose the elliptic curve y2 = x3 + 5x - 5, with the point P=(1,1) on it, and let's try to compute (10!)P.
First we compute 2P. The slope of the tangent line at P is s=(3x2+5)/(2y)=4, and then the coordinates of 2P=(x′,y′) are x′=s2-2x=14 and y′=s(x-x′)-y=4(1-14)-1=-53, all numbers understood (mod n). Just to check that this 2P is indeed on the curve: (-53)2=2809=143+5·14-5.
Then we compute 3(2P). The slope of the tangent line at 2P is s=(3·142+5)/(2(-53))=-593/106 (mod n). Using the Euclidean algorithm: 455839=4300·106+39, then 106=2·39+28, then 39=28+11, then 28=2·11+6, then 11=6+5, then 6=5+1. Hence gcd(455839,106)=1, and working backwards (a version of the extended Euclidean algorithm): 1=6-5=2·6-11=2·28-5·11=7·28-5·39=7·106-19·39=81707·106-19·455839. Hence 106-1=81707 (mod 455839), and -593/106=-133317 (mod 455839). Given this s, we can compute the coordinates of 2(2P), just as we did above: 4P=(259851,116255). Just to check that this is indeed a point on the curve: y2=54514=x3+5x-5 (mod 455839). After this, we can compute .
We can similarly compute 4!P, and so on, but 8!P requires inverting 599 (mod 455839). The Euclidean algorithm gives that 455839 is divisible by 599, and we have found a factorization 455839=599·761.
The reason that this worked is that the curve (mod 599) has 640=27·5 points, while (mod 761) it has 777=3·7·37 points. Moreover, 640 and 777 are the smallest positive integers k such that on the curve (mod 599) and (mod 761), respectively. Since 8! is a multiple of 640 but not a multiple of 777, we have on the curve (mod 599), but not on the curve (mod 761), hence the repeated addition broke down here, yielding the factorization.
Read more about this topic: Lenstra Elliptic Curve Factorization
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)