CPSC 467b: Cryptography and Computer SecurityHandout #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
      1           2           3          4
(5  mod 33),(5 mod  33),(5 mod  33),(5  mod  33),...?

  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)?

In all cases, justify your answers.

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

Compute ϕ(2600). Show your work.

Problem 4: Euler theorem

Compute 3699845 mod 2600.

Problem 5: Extended Euclidean algorithm

Use the extended Euclidean algorithm to solve the Diaphantine equation

601x - 1251y = 1

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.