[Course home page] [Course handouts]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security
 
Professor M. J. Fischer
Handout #7
February 18, 2005
Problem Set 3
Due in class on Tuesday, February 22, 2005.
This is a "mini" problem set to give you some practice before the midterm exam with some of the recently-covered number theory. I encourage you to finish these problems by the due date above, but I will give an automatic extension until class time on Thursday to anybody who requests it.

Problem 8:   Chinese remainder theorem

Solve the following system of equations for x:
x ≡ 1 mod 5
x ≡ 4 mod 11
x ≡ 3 mod 17
Use the method of Section 9 of the week 5 lecture notes. Do not do an exhaustive search for x on the computer, although you are welcome to use a computer or calculator to evaluate arithmetic formulas.

Problem 9:   Primitive roots

  1. Give a formula for the number of primitive roots of p when p is prime, and evaluate this formula for p = 11 and p = 23.
  2. Find all primitive roots of p, for p = 11 and p = 23. You may use a computer.

Problem 10:   Square roots

Find all square roots of 1 modulo 77. Again, you may use the computer.


File translated from TEX by TTH, version 3.66.
On 22 Feb 2005, 19:15.