1) We have shown that if p is a prime number then for all a, a p = a mod p (Fermat). Hence if there exists a such that a p 6= a mod p, then p is a composite number (not a prime). Use this to show 231 is composite number

2-In the following two examples, you are going to extract roots modulo N. In both examples N is prime. This a difficult problem when N is not prime. The RSA encryption is based in this difficulty where the N is product of two large distinct primes (N is published but not its factors). (a) Use the Euclidean Algorithm to show the gcd(19, 96) = 1. Hence find d such that 19d = 1 mod (97) and solve x 19 = 36 mod (97). (b) Solve x 137 = 428 mod 541.

(3) Alice publishes her RSA public key: modulus, that means N = 2038667 and exponent e = 103. (a) Bob wants to send Alice the (plaintext) message m = 892383. What ciphertext does Bob send to Alice? (b) Alice knows that N factors into two primes one of which is p = 1301. Find the decryption exponent d for Alice. (c) Alice receives the ciphertext c = 317730 from Bob. Decrypt the message.

4- In an RSA encryption, Bob got a little creative and wanted to guard against transmission errors. So he encrypted his message m twice by using two encryption exponents e1 and e2. That is, he transmitted to Alice c1 = me1 and c2 = me2 . Now the eves dropper, Eve, has N = pq, e1, e2, c1 and c2. However, Bob made a grave miscalculation: the greatest common divisor of e1 and e2 was 1. Show Eve can recover Bob's plaintext message m without factoring N. Hint. The gcd(e1, e2) = 1 implies that there are integers n and m such that ne1 + me2 = 1.

(5) Miller-Rabin test for primality. Theorem

1. Let p be an odd prime number and factor p 1 = 2k q so that q is odd1 Then for all natural numbers a either a q = 1 mod (p)

a q , a2q , . . . , a2 k1q

(2) . Hence, by logic, if there exists a natural number a such that a q 6= 1 mod (p) and none of the numbers a q , a2q . . . , a2 k1q are 1 mod (p), then p is not a prime number. Let us work through an example to show the Carmichael number p = 118901521 is not a prime number. We will show that a = 2 fulfils both conditions to guarantee that p is not prime. Why did I pick a = 2? That is the smallest number to try; if 2 does not work, try 3. . . . > sage p=118901521 > sage divmod(p-1,16) (7431345, 0) # divmod(p-1,32) will return a non-zero remainder. #So highest power of 2 that can be factored from p-1 is 16=2^4; so k=4. > q=divmod(p-1,16)[0] # the zeroth item of the list divmod is the quotient. > sage mod(2^q, p), # see what is this. It is not 1. Now, we will compute 2q , 2 2q , 2 4q , 2 8q modulo p (here 8 = 2k1 ; the k for this p was 4). We will verify none of them are 1 modulo p, that is 118901520. We can setup a table of 2q , 2 2q , a4q , 2 8q modulo p. The table syntax is table() and rows are in [ ]. So, e.g., table([[1, 2], [3, 4]]) would return a table whose first row is 1, 2 and second row is 3, 4. Look at sage manual for header rows, dividers etc.

Continue the sage worksheet. > var('x') > table([(x, mod(2^(q*2^x), p)) for x in [0..3]]) This will return a table that shows the remainder of 2q , 2 2q , 2 4q , 2 8q when divided by p. None of them are 1 mod (p), i.e., none of the remainders were p 1. For practice, you verify that the Carmichael number p = 75361 is not a prime. Then test an integer that is in fact prime, p = 104513, using a = 3. What did you notice?

Note: It can be shown that numbers of the form (6k + 1)(12k + 1(18k + 1) are Carmichael numbers if each of the three factors are prime. That is how we know 118901521 = 271 541 811 is a Carmich