YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer Security Handout #4 Professor M. J. Fischer February 18, 2013

Problem Set 3

Due on Tuesday, February 26, 2013.

Problem 1: Zero divisors

An element a Zn -{0} is said to be a zero divisor modulo n if ab 0 (mod n) for some b Zn -{0}.

1. Explain why there are no zero divisors in Zp when p is prime.
2. Find a zero divisor in Z33.
3. What is the value of the first element to repeat in the sequence

4. Do you think it is possible to find a non-zero number x Z33 and a number k 0 such that xk 0 (mod 33)? Why or why not? Would your answer change for some RSA modulus n other than 33?
5. Suppose n is not required to be an RSA modulus. Can you find numbers n,x,k such that x ⁄≡ 0 but xk 0 (mod n)?

Problem 2: Greatest common divisor

The definition of greatest common divisor can be extended naturally to a sequence of numbers (a1,a2,,ak), not all of which are zero; namely, it is the largest integer d 1 such that daj for all j = 1,2,,k. Describe an efficient algorithm for computing gcd(a1,,ak), and explain why it computes the correct answer.

Problem 3: Euler’s totient function

Problem 4: Euler theorem

Compute 3699845 mod 2600.

Problem 5: Extended Euclidean algorithm

Use the extended Euclidean algorithm to solve the Diaphantine equation

Show the resulting table of triples as in slide 18 of lecture 9 notes.
[Note: You may write a program to produce the table if you wish, but these numbers are small enough to make it quite feasible to carry out the computation by hand or with the aid of a pocket calculator.]

Problem 6: Diffie-Hellman

[Textbook, p.216, problem 7.6.10]

Problem 7: Primitive roots

1. Find a primitive root g of p = 761 and use the Lucas test to prove that you have one.
2. Find a non-trivial1 number g Z*761 that fails to be a primitive root of p, and use the Lucas test to prove your answer correct.