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

.

10) 2 3 2

( m + − n = · 7 · 13 · 17

13) 2 2 2 3 2 7 2

( m − − n =− 1 · · · · 11

17) 2 2 2 17 2

( m + − n = · 3 · 7 ·

17) 2 2 2 3 2

( m − − n =− 1 · · · 17 · 41

20) 2

( m + − n = 3 · 11 · 13 · 67

24) 2 11 2

( m + − n = 7 · · 41

24) 2 11 2 17 2

( m − − n =− 1 · ·

and so we obtain the following vectors

( m + X ) 2

X m + X − n Factors Vector

− 697 − 1 · 17 · 41

(1 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0) 0 726

2 2

· 3 3

· 7

(0 , 2 , 3 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0) 1 727 756

2 728 2211 3 · 11 · 67 (0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 1)

2 2 3 3

5 731 6588 · · 61 (0 , 2 , 3 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0)

2 2

7 733 9516 · 3 · 13 · 61 (0 , 2 , 1 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0)

2 2

− 7 719 − 10812 − 1 · · 3 · 17 · 53 (1 , 2 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0)

3 2

10 736 13923 · 7 · 13 · 17 (0 , 0 , 2 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0)

2 2 3 2 7 2

− 13 713 − 19404 − 1 · · · · 11 (1 , 2 , 2 , 2 , 1 , 0 , 0 , 0 , 0 , 0 , 0)

2 2 17 2

17 743 24276 · 3 · 7 · (0 , 2 , 1 , 1 , 0 , 0 , 2 , 0 , 0 , 0 , 0)

− 1 · 2 2 · 3 2

− 17 709 − 25092 · 17 · 41 (1 , 2 , 2 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0)

20 746 28743 3 · 11 · 13 · 67 (0 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 1)

7 · 11 2

24 750 34727 · 41 (0 , 0 , 0 , 1 , 2 , 0 , 0 , 1 , 0 , 0 , 0)

− 1 · 11 2 · 17 2

− 24 702 − 34969 (1 , 0 , 0 , 0 , 2 , 0 , 2 , 0 , 0 , 0 , 0)

We can now reduce the vectors modulo 2 and try to find linear dependencies. Here,
we can simply notice that the vectors for X = 1 and for X = 17 coincide modulo 2.

Indeed, we have

727 2 743 − 2 3 2 17 − 2 · ≡ · (mod n ) .

743 − 1 17 − 1

Since 727 · mod n = 223754 and 3 · mod n = 186273, we have

223754 2 186273 2

≡ mod n and we notice that 223754 − 186273 = 37481 and

gcd(37481 , n ) = 1013, which is a nontrivial factor of n . This leads us to the

factorization n = 521 · 1013.

7.2.6 Factorization Nowadays

The previous methods have been extended to give birth to the more sophisticated
number field sieve method (NFS), due to Hendrik Lenstra and Arjen Lenstra, which is
quite beyond the scope of this topic (see Ref. [115]). We simply mention that the NFS