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.

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

- Explain why there are no zero divisors in Z
_{p}when p is prime. - Find a zero divisor in Z
_{33}. - What is the value of the first element to repeat in the sequence
- Do you think it is possible to find a non-zero number x Z
_{33}and a number k ≥ 0 such that x^{k}≡ 0 (mod 33)? Why or why not? Would your answer change for some RSA modulus n other than 33? - Suppose n is not required to be an RSA modulus. Can you find numbers n,x,k such that x ⁄≡ 0 but
x
^{k}≡ 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
(a_{1},a_{2},…,a_{k}), not all of which are zero; namely, it is the largest integer d ≥ 1 such that d∣a_{j} for all
j = 1,2,…,k. Describe an efficient algorithm for computing gcd(a_{1},…,a_{k}), and explain why it computes
the correct answer.

Problem 3: Euler’s totient function

Compute ϕ(2600). Show your work.

Compute 3^{699845} 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.]

[Textbook, p.216, problem 7.6.10]

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