Algorithmic Number Theory - A Classical Introduction to Cryptography: Applications for Communications Security - page 193

and

2

x = λ − 2 x 2 mod n = 26093 y = λ ( x 2 − x ) − y 2 mod n = 7008

and ( x , y ) + X 2 by

y 2 − y

λ = mod n = 5816

x 2 − x

and

2

x 3 = λ − x − x 2 mod n = 15187 y 3 = λ ( x − x 3 ) − y mod n = 29168 .

Next we compute X 4 = 4 · X 3 = 2 · (2 · X 3 ). We obtain

i = 1 X 1 = (23482 , 9274)

i = 2 X 2 = (18935 , 21838)

i = 3 X 3 = (15187 , 29168)

i = 4 X 4 = (10532 , 5412)

In order to compute X 5 = 5 · X 4 = (2 · (2 · X 4 )) + X 4 , we first compute

2 · X 4 = (30373 , 40140)

then

2 · (2 · X 4 ) = (27556 , 42335)

but when we add up this point and X 4 , we need to compute

42335 − 5412

λ = mod n

27556 − 10532

but the denominator 27556 17024 is not invertible modulo n . When trying

to invert it with the Euclid algorithm, we end up with the gcd between 17024 and n
which is 133, indeed a factor of n .

− 10532 =

This kind of algorithm illustrates how computation in an ill-designed structure
(namely an elliptic curve over a structure Z n which is not a field) can be performed
until we stumble upon a computation error which yields an interesting result, here the
factorization of n .

7.2.4 Fermat Factorization and Factor Bases

The Fermat factorization algorithm is used to factorize n q . The

purpose is to find a representation of n as the difference of two perfect squares

= pq where p ≈