Introduction to Cryptography with Open-Source Software

Basic num ber theory 53

(ii) Check it with the values p = 71, e = 11, d = 51, m = 40.

(iii) What problem provides the security for this system? Suppose an

attacker, using a known plaintext attack, has p, m and c. How can

the a ttacker find e (and d)?

44. Lucas’s primality test (named for Edouard Lucas, 1842–1891, a French

mathematician) works as follows: for a number n to be tes ted, first find

all prime factors of n − 1. If a number a < n can be found for which

a

n−1

= 1 (mod n)

and

a

(n−1)/q

6= 1 (mod n)

for all prime factors q of n − 1 , then n is prime.

(a) Show that 79 is pr ime by using a = 3.

(b) Show that 1009 is prime by using a = 11.

(c) What happens