[Course home page] [Course handouts]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security
 
Zheng Ma
Handout #11
March 1, 2005
Solutions to Problem Set 3
Note: Each question counts 10 points.

Problem 6:   Chinese remainder theorem

Solve the following system of equations for x:
x ≡ 1 mod 5
x ≡ 4 mod 11
x ≡ 3 mod 17
Solution: Because n1=5, n2=11 and n3=17 are pairwise relatively prime positive integers, we can apply Chinese Remainder Theorem directly, where a1 = 1, a2 = 4, and a3 = 3:
n=Πi=13ni = 935
N1 = n/n1 = 187, M1 ≡ N1−1 ≡ 3 mod n1
N2 = n/n2 = 85, M2 ≡ N2−1 ≡ 7 mod n2
N3 = n/n3 = 55, M3 ≡ N3−1 ≡ 13 mod n3
x = ( 3
∑
i=1 
 aiMiNi) ≡ 411 mod n.
This answer is easily verified by computing 411 mod ni for i=1, 2, 3.

Problem 7:   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.

Solution:
  1. The number of primitive roots of prime p is φ(φ(p)). So φ(φ(11))=φ(10)=4 and φ(φ(23))=φ(22)=10.

  2. We can use the Lucas test to find all the primitive roots of p as in the following program: 
    #include <lnv3/lnv3.h>
#include <nttl/gcd.h>
#include <nttl/randomPrime.h>
#include <nttl/inverse.h>
#include <stdio.h>
main(int argc, char** argv){
        ln x, p,p_1,q;
        int i,prime=11;
        prime = ((argc > 1) ? atoi(argv[1]):prime);
        p = (ln) prime;
        p_1 = p -1;
        bool test;
        for(x=1 ; x < p; x++){
        test = true;
        for(i=2; i < p;i++){
         if(p_1 % i == 0){
                q = p_1/i;
                if(x.FastExp(q,p)== 1) {test=false;break;}
         }
        }
         if(test) cout<< x << " is a primitive root" <<endl;
        }
}
    So, the primitive roots for 11 are {2,6,7,8}. The primitive roots for 23 are
    {5,7,10,11,14,15,17,19,20,21}.

Problem 8:   Square roots

Find all square roots of 1 modulo 77. Again, you may use the computer.
Solution:   You can write a program to solve this. Here, we show how to find the square roots of 1 without using a computer. We notice that n = p×q = 7 ×11, and p and q are primes. So a ∈ QR77 has exactly four square roots in Z∗77. Let b is one of the square roots, i.e. b2 ≡ 1 mod 77. So b2 ≡ 1 mod 7 and b2 ≡ 1 mod 11. So b must be a square root of 1 in both Z∗7 and Z∗11. Now we know that {(1,1),(−1,−1),(1,−1),(−1,1)} are four such elements in Z∗7×Z∗11. These correspond to {1,76,43,34} ∈ Z∗77 by the Chinese Remainder Theorem.


File translated from TEX by TTH, version 3.40.
On 1 Mar 2005, 15:52.