Other Applications - Elliptic Curves: Number Theory and Cryptography - page 189

curves. It turned out to be very effective for factoring numbers of around 60
decimal digits, and, for larger numbers, finding prime factors having around
20 to 30 decimal digits.
We start with an example.

Example 7.1
We want to factor 4453. Let E be the elliptic curve y 2 = x 3 +10 x 2mod

4453 and let P =(1 , 3). Let's try to compute 3 P . First,wecompute2 P .The
slope of the tangent line at P is

−

3 x 2 +10
2 y

= 13

6 ≡

3713 (mod 4453) .

We used the fact that gcd(6 , 4453) = 1 to find 6 − 1 ≡ 3711 (mod 4453). Using

this slope, we find that 2 P =( x, y ), with

3713 2 x ≡ − 2 ≡ 4332 , y ≡− 3713( x − 1) − 3 ≡ 3230 .

To compute 3 P ,weadd P and 2 P .Theslopeis

3230 − 3

4332 − 1 = 3227 4331 .

But gcd(4331 , 4453) = 61 = 1. Therefore, we cannot find 4331 − 1 (mod 4453),
and we cannot evaluate the slope. However, we have found the factor 61 of
4453, and therefore 4453 = 61 · 73.
Recall (Section 2.11) that

E ( Z 4453 )= E ( F 61 ) ⊕ E ( F 73 ) .

If we look at the multiples of P mod 61 we have

P ≡ (1 , 3) , 2 P ≡ (1 , 58) , 3 P ≡∞ , 4 P ≡ (1 , 3) , ... (mod 61) .

However, the multiples of P mod 73 are

P ≡ (1 , 3) , 2 P ≡ (25 , 18) , 3 P ≡ (28 , 44) , ..., 64 P ≡∞ (mod 73) .

Therefore, when we computed 3 P mod 4453, we obtained mod 61 and a

finite point mod 73. This is why the slope had a 61 in the denominator and
was therefore infinite mod 61. If the order of P mod 73 had been 3 instead
of 64, the slope would have had 0 mod 4453 in its denominator and the gcd
would have been 4453, which would have meant that we did not obtain the
factorization of 4453. But the probability is low that the order of a point
mod 61 is exactly the same as the order of a point mod 73, so this situation
will usually not cause us much trouble. If we replace 4453 with a much larger
composite number n and work with an elliptic curve mod n and a point P

∞