Math 5248 Fall 2007

The text for Math 5248 is "Crypto", notes by Paul Garrett, available at Alpha Print in Dinkytown, 1407 4th St SE., 612-379-8535

5248 Syllabus Crypto computations

NEW Final Exam time: 3:35-5:15 Fri Dec 7, Vincent Hall 6

NEW Office Hours: MW 11:15-12:05, F 10:10-11:00.

NEW HW #4.5, see below!

Textbook exercises: 1.1: 10 1.2: 18 1.5: 6,9 1.6: 5,10 14 17 1.7: 5,8,12 6.2: 1,4,6

Extra problems:

E1: Suppose that m and n are positive integers, and there are integers x and y such that xm+yn=10. Show that GCD(m,n) cannot be 6.
E2: How many zeros does the integer 1000! have at the end of its decimal expression?
E3: Suppose that x and n are positive integers. TRUE or FALSE? If 6 divides xⁿ, then 6ⁿ divides xⁿ.
E4: Use the Fundamental Theorem of Arithmetic to show that log₁₀ 3 is an irrational number.
E5: Prove that there are infinitely many prime numbers which are congruent to 3 modulo 4.

Solution to E1: We show that GCD(x,y)=6 is impossible. Suppose that 6 does divide both x and y. Then 6 must divide xm+yn=10, which is not true.

Solution to E2: The number of zeros at the end of the decimal expansion of any integer N is the highest power of 10 dividing N. Thus we need to find how many 2's and 5's are in the prime factorization of 1000!. Clearly there are more 2's than 5's. The number of 5's is [1000/5]+[1000/25]+[1000/125]+[1000/625]=249 so there are 249 trailing zeros.

Solution to E3: True. We prove that 6 must divide x, so that 6ⁿ therefore divides xⁿ. Since 2 divides 6, we have that 2 divides xⁿ, so 2 must appear in the prime factorization of x. Similarly 3 also appears, so 6 divides x.

Solution to E4: We show that log₁₀ 3 =p/q, for positive integers p and q, is impossible. if this occurs, then 10^p/q=3, or 3^q= 10^p=2^p5^p. Since 2,3, and 5 are prime and p and q are postive, this equation contradicts the uniuqeness of prime factorization of the integer 3^q.

Solution to E5: We show that the assumption that there are finitely many primes which are congruent to 3 modulo 4 is impossible. Make this assumption and call these finitely many primes p₁, p₂,..., p_k. Let N be the integer 4*p₁*p₂*...* p_k-1. N is odd, congruent to 3 modulo 4, and has a prime factorization. If all of the primes in N's prime factorization were congruent to 1 modulo 4, then N would also be congruent to 1 modulo 4, which N is not. So some prime, call it q, which is congruent ot 3 modulo 4, divides N. So q is one of the primes p_i, so q divides N-4*p₁*p₂*...* p_k=1, which is a contradiction.

Textbook exercises: 2.1: 3,7 2.2: 3,10 2.3: 1 3.1: 3 4.1: 1 4.4: 4, 9 (may be difficult)

Extra problems:

Problem E1: Vigenere decrypt the ciphertext

AMPGIEPCBHFFPPSVBNMSNGCALVVISEHMGUHNYKREWAPXERSFLRQZOEXEYNRRDOVRGFZQROCQJGNYZF\ JSHLCHLRFJSEBYVGSFWSJYMGSITVFYHMGUYNWIVQCFNSCRSLPWPRZYZTUNBRQPBJSEDSSLSYWSJNBQ\ RVRRBGZAREWARSIRFLZYEUSNOPBBYSZVGUSTTVYJWGSXURGHYMAUSEPCRFOAOWURGTZRRYIPJMAGVR\ DOLJWGSHVNABYHFSCYWSJUSEOSJAHBLFEVRTPFLNTBFRGNWAHLRESEZGXVBTSSEFSCPSCYSRLXZNFF\ SQRYZBHTVRGRGIELCAPWZVZRDEFLCHOVVSHCLWGGVRQPBJSEDXUNHTCSJFCVYGERRVMPLUWTSRRJGC\ LTREHNIMFNDCPEEBBGSIFUCEPANVHVYKGBHNVILBINHELPZVXFVAHUPFNPYJTXULCHCLRNRVYXURQY\ ZYQFOAOCBHFRRSARZHNCVAHUPWXLKVELQVOZZRQFDVNXHESLZYEFSYQSANHELMAVBNDXNGWBYAVGVC\ WEFGWPTRRCCEEIEFKVELYBCXTRTTZNDWGVSFDYQQSAWCFBARZRRVGGSIEROGELRGIEYWGLZRELRTWE\ WAVGVGSIXNZRTHBFQBAIRLSF

Problem E2: Suppose that you have a language with only three letters A, B, C with frequencies 0.7, 0.2, and 0.1 respectively. Vigenere encryption is done modulo 3 to produce the ciphertext ABCBABBBAC. If the key length is known to be 1, 2 or 3, give a reason why the key length of 2 is likely, and find the probable key.

Problem E3: In random English an "e" occurs 11% of the time, while a "t" occurs 9% of the time. Find the probability that a random "word" of length 11 contains exactly 2 e's and 1 t.

Problem E4: What is the probability that a random permutation of length 26 of the 26 letters a-z has all of the vowels before all of the consonants?

Problem E5: Let S be the set of all words of length n in "a", "b", and "c", with each word in S equally likely. Let X be the random variable on S X(s)=3*(#a's in s)-5*(#c's in s). Find the exepcted value E(X).

2.1.3: 5!=120.

2.1.7:(7 choose 4)=35.

2.2.3:((6 choose 4)+(6 choose 5)+(6 choose 6))/2⁶=21/64.

2.2.10: (6+5)/36, 1/36.

2.3.1: (0.8833)¹⁰ and (0.8833)¹⁰⁰.

4.1.4: this is a routine question

4.4.4: Suppose there are n H's and then a T: \sum_{n=0}^\infty n/2^(n+1)/\sum_{n=0}^\infty 1/2^(n+1)=1.

4.4.9: Let a_n be the number of coin flips of length n which do not have HH and which do not end in an H. Then the expected number of flips before you find the first HH is

\sum_{n=0}^\infty n*a_n/2^(n+2)/\sum_{n=0}^\infty a_n/2^(n+2).

Claim: a_n=F_n the nth Fibonacci number. This sequence is 1,1,2,3,5,8,13,..., satisfies F_n=F_{n-1}+F_{n-2}, and has the generating function G(x)=\sum_{n=0}^\infty F_n*x^n=1/(1-x-x^2).

To prove the claim, note that a word in H and T of length n without HH, and ending in T must end in either TT (F_{n-1} choices) or THT (F_{n-2} choices). The initial condition also checks.

So the expected value is 1/2*G'(1/2)/G(1/2)= 4.

E1: The key is "lennon" and the plaintext is the words to "Lucy in the Sky with Diamonds"

E2: just skip this problem

E3: (11 choose 2)*(9 choose 1)*(0.11)² *(0.09)¹*(0.80)⁸

E4: The 5 vowels a,e,i,o,u must be in positions 1 through 5, 5! choices, the 21 consonants then have 21! choices, out of 26! permutations.

E5: Let A be the random variable which is the # of a's in word, and C for the # of c's in a owrd. We have X=3*A-5*C. The expectation is linear so E(X)=3*E(A)-5*E(C). We know that E(A)=1/3*n, and E(C)=1/3*n, so E(X)=-2*n/3.

1. Solve for x: 112*x+14=246 mod 359.

2. True or False? If x is a positive integer which divides y*z, them x must divide y or x must divide z.

3. True or False? If x is a positive integer, then x and x+3 are never both prime.

4. Suppose you are told that there are integers x and y such that x*7638198+y*587273286=12. What is GCD(7638198, 587273286)?

5. Use the Euclidean algorithm to find the inverse of 1111 mod 4632197.

6. How many possible invertible shift ciphers x->a*x+b are there mod 40?

7. Encrypt the message "euler is the greatest" using the affine cipher 3x+11 mod 26.

8. Find a prime number p which is larger than 3 such that x^2=-1 mod p has no solution.

9. An alien written language has 3 characters, "x" "y" and "z". x occurs 60% of the time, y occurs 30%, and z 10%. Find the Friedman average index of coincidence for two random streams of this language. If "YYZYXYYXYYXXZXYYYYZYXYYXYYXXZXYY" is the ciphertext of a shift cipher, what is the plaintext message?

10. Characterize when x^2-1 is prime for a postive integer x.

11. Let W be the set of words of length 8 in "a" "b" "c", P(a)=0.5, P(b)=0.4, P(c)=0.1. Find the probability that a word has exactly 2 "a"'s. If X(w)=#'c in w, what is E(X)?

12. Suppose that n is a positive integer which has 2,3,5, and 7 in its prime factorization. Show that the probability that an integer x between 0 and n-1 has GCD(x,n)=1 is less than 0.20.

13. Let p be a prime number not equal to 5, and let a be any positive integer. True or False? One of the integers a, a+p, a+2*p, a+3*p, a+4*p is divisible by 5.

14. let x=a_n a_n-1...a₁ be the decimal representation of an integer x. (For example x=4512309). Prove that x=0 mod 3 if, and only if, a_n +a_n-1+...+a₁ =0 mod 3. Does this work modulo 9 also?

15. Two elements (x,y) of Z/15 are chosen randomly (x=y is allowed.) Find the probability that 2x+y=7 mod 15, and also that 3x+6y=1 mod 15. (Two different questions.)

16. What is the smallest positive integer x such that 300^x=0 mod 839808000 ?

17. True or False? Let x and y be positive integers. x has an inverse modulo y if and only if y has an inverse modulo x.

18. 1456667 is a prime number. What is 1456666! modulo 1456667? (Hint: Try pairing an integer x with its inverse modulo 1456667.)

19. Let a be a positive integer. Show that GCD(a²+2,a+1)=3 if a=2 mod 3, and is 1 otherwise.

20. Suppose that every student at the U chooses at random a 4 digit ATM password, from 0000 to 9999. If we choose N students, how large should N be so that the probability that two of the students have the same password is at least 1/2?

BONUS QUESTION! Rejected exam question! Find the smallest positive integer x such that (1,000,000)!=0 mod 3^x and (1,000,000)! does not equal 0 mod 3^x+1.

#1(a): Decrypt the ciphertext ``GEAQ FTYLDGK", which has been encrypted by the affine cipher 7x+4 mod 26.

y=7x+4 so x=(y-4)*7^-1. but since -4*26+7*15=1, 7^(-1)=15 mod 26. So the decrpytion map is x=15*y+18.

y=6, x=4 E, y=4 x=0 A, y=0 x=18 S, y=16 x=24 Y "EASY"

y=5 x=15 P, y=19 x=17 R, y=24, x=14 O, y=11 x=1 B, y=3 x=11 L y=6 x=4 E, y=10 x=12 M "PROBLEM"

#1(b): Give an example of two plaintext messages of length 3, each with 3 distinct letters, and with no letters in common, whose encryptions by the affine cipher 8x+4 mod 26 are identical.

The map A(x)=8x+4 mod 26 satisfies A(x+13)=A(x), repeats each 13. So the plaintexts "abc" and "nop" map to the same ciphertext.

#2: True of False? (If true, give a proof, if false, give a counterexample.) If x\ge 2 is a positive integer, then x³+1 is not prime.

TRUE. x³+1=(x+1)*(x²-x+1) factors, and x+1 is strictly less than x³+1 (since x is at least 2) and greater than 1. So x³+1 is not prime.

#3: Suppose that e occurs 11% of the time in random English text. What is the probability that a random fragment of Englist text of length 100 has exactly 11 e's?

(100 choose 11)*(0.11)¹¹*(0.89)¹¹ about 12.7%.

#4: Suppose that a subset S of 3 distinct integers from the set {1,2,3,...,100} is chosen randomly, each 3-subset equally likely.

For an integer k, 0\le k\le 3, what is the probability that S contains exactly k invertible elements modulo 100? (For example, S={3,5,77} contains k=2 invertible elements, 3 and 77.)

There are \phi(100)=100*(1-1/2)*(1-1/5)=40 elements which are invertible mod 100, and 60 which are not. So the answer is

(40 choose k)*(60 choose 3-k)/(100 choose 3). These numbers are about 6.1% k=3, 28.9% k=2, 43.8% k=1, 21.2% k=0.

Note: The answer of (3 choose k)*(0.4)^k(0.6)^3-k is incorrect, as that allows integers to be repeated. Numerically it is close, but not equal, to the correct answer.

#4(b) What is the expected number of invertible elements in S?

The expectation is \sum_{k=0}^3 k*(40 choose k)*(60 choose 3-k)/(100 choose 3) which is 6/5=1.2.

#5: Suppose that x and y are positive integers, and the last digit in y's decimal expansion is a 3. Prove that GCD(20^x, 3^y+4)=1.

The only prime factors of 20^x are 2 and 5. We must show that 2 and 5 do not divide 3^y+4.

2 does not divide 3^y+4 because 3^y is odd, as is 3^y+4.

Let's check if 3^y+4=0 mod 5 is possible, that is, is 3^y=1 mod 5 possible? Since y's last digit is a 3, write y=10*X+3, where X is an integer. Then 3^y=3^10X*3³. But 3⁵=3 mod 5, so 3^10X=1 or 4 mod 5, and thus 3^y=2 or 3 mod 5, which is not 1 mod 5. So 5 does not divide 3^y+4.

Homework #3 Due Wed Oct 17:

Textbook exercises: 7.2: 3,4,7,9 7.3: 3,5,11,12

Extra problems: The web sites Fast Modular Exponentiation
Crypto Java Applets

could be helpful.

Problem E1: Use the RSA modulus 20807*74419= 1548436133 to encrypt the plaintext "stop" with encryption exponent e=7.

Problem E2: Find the decryption exponent for the RSA modulus 20807*74419= 1548436133 of problem E1. Use it to decrypt the ciphertext 148290648. What is the plaintext in English?

Problem E3: Suppose we use an RSA cipher with modulus n=p*q and encryption exponent e, to encrpyt plaintext x to a ciphertext c. What is the decryption of a ciphertext 2^ec?

Problem E4: Suppose that person #1 has RSA modulus n, and encryption exponent e₁, and person #2 has the same RSA modulus n, but a different encrpytion exponent e₂. So n, e₁, are e₂ are public information. Suppose that GCD(e₁, e₂)=1. Suppose that you encrpyt a plaintext message x, and send the appropriate ciphertexts to person #1 and person #2. Show that if I intercept your two ciphertexts, and I can find your original plaintext message x.

7.2.3: 54321³= 208718 mod 210757.

7.2.4: 12091=107*113, so we need the inverse of 3 mod 106*112, which is, from the Euclidean algorithm, -3957 or 7915.

7.2.7: Again 1019 and 1031 are prime, so we need the inverse of 3 mod 1018*1030, which is -349513.

7.2.9: We already know this is true from Euler's thoerem if GCD(x,p*q)=1. So we just need to prove it is true of p divides x, namely both primes p and q divide x^(p-1)(q-1)+1-x. We might as well assume that q does not divide x. Clearly x divides x^(p-1)(q-1)+1-x so p also does. we just need that x^(p-1)(q-1)+1-x=0 mod q. Since x is relatively prime to q, and q is prime, x^q-1=1 mod q, so x^(p-1)(q-1)=1 mod q, and thus x^(p-1)(q-1)+1=x mod q.

7.3.3: The powers of 2 mod 25 are 2,4,8,16,7,14,3,6,12,24,23,21,17,9,18,11,22,19,13,1, so the smallest positive power of 2 which gives 1 is 20=\phi(25).

7.3.5: 2³=3 mod 5, so log₂3=5. mod 5

7.3.11: 2⁷=3 mod 125, so log₂3=7 mod 125

7.3.12: The primitive roots mod 17 are 3,5,6,7,10,11,12,14. Choose r=3 s=5. 3¹⁴=2 mod 17, so log₃2=14 mod 17. 5⁶=2 mod 17, so log₅2=6 mod 17. Also log₃5=5 mod 17, and 14= 5*6 mod 16.

E1: Using a=01, ..., z=26 we get 463430646. If you used a=00, ... z=25 that is ok.

E2: The decryption exponent is 663574675, and the plaintext is 148290648^663574675=521120518 mod 20807*74419, so the plaintext is "EULER".

E3: x^e=c so (2x)^e=2^ec, so the decryption is 2*x.

E4: I know x^e1 and x^e2, and n and e1 and e2. I want to find x. Since GCD(e1,e2)=1, use the Euclidean algorithm to find integers y and z such that y*e1+z*e2=1. Then x=(x^e1)^y*(x^e2)^z mod n, and I know everything on the right side.

Homework #4 Due Wed Oct 31: 9.1: 3,5,7 9.5:3,5 9.7: 2,4,6 10.3:2,5,6 13.1: 1,7 13.2: 2 13.6: 4

E1: Use the Miller-Rabin test to show that 5377 is a composite number. You can choose your own base, 5376=21*2^8.

E2: Find log₁₁(5) mod 9829. Note that 9829 is a prime, and use hand computations (not the computer), and the factorization 9828=2²*3³*7*13.

Solutions to HW #4

9.1.3: 2¹⁰⁰⁰ mod 23=2^{1000 mod 22} mod 23=2¹⁰ mod 23=12.

9.1.5: 2^1000000 mod 17=2^{4*250000 mod 17} mod 23=(-1)^2500000 mod 17=1.

9.1.7: Since x*x^p-2=x^p-1 by Fermat's little theorem, x^p-2 is the inverse to x.

9.5.3: 2⁶²=4³¹=4*16¹⁵=4*16*256⁷= 4*16*256*341³=4*16*256*341*936=370.

9.5.5: 59 is prime, see problem 9.1.7, the inverse is 30.

9.7.2: 101 is prime, GCD(3,100)=1 and the inverse of 3 mod 100 is 67, so a cube root of 46 is 46⁶⁷=59 mod 101. Check: 53³=46 mod 101.

9.7.4: Here 103 is prime, but 3 divides 102, but GCD(3,102/3)=1, so we need the inverse of 3 mod 34, which is 23. So a cube root of 14 mod 103 is 14²³=30 mod 103. Check: 30³=14 mod 103.

9.7.6: Here 101 is prime, and GCD(11,100)=1, the inverse of 11 mod 100 is 91, so an 11th root of 2 mod 101 is 2²³=30 mod 103. Check: 30³=14 mod 103.

10.3.2: Since the inverse of 7 mod 9 is 4, this x=44=8 mod 9 and also the inverse of 3 mod 35 is 12 so the next equation is x=19 mod 35. Since GCD(9,35)=1, we have 4*9-1*35=1, so the solution is x=19*4*9-1*35*8=404=89 mod (9*35).

10.3.5: (Sorry I did 11 and 13 instead of 13 and 17.) x=1 or 12 mod 13 and x=1 or 10 mod 11. Since 6*11-5*13=1, the four solutions mod 13*11 are

1*6*11-1*5*13=1, 1*6*11-10*5*13=131, 12*6*11-1*5*13=12, 12*6*11-10*5*13=142.

10.3.6: The square roots of 2 mod 7 are 3, 4, and mod 23 are 5, 18. Since 10*7-3*23=1 the solutions are

5*10*7-3*3*23=143, 5*10*7-4*3*23=74, 18*10*7-4*3*23=18, 18*10*7-4*3*23=87.

13.1.1: 17⁴⁴=1 mod 45.

13.1.7: The next ones are 1387, 1729, 1905, 2047, etc. The base 3 non-prime pseudoprimes to 1105 are 91, 121, 286,671,703,949, 1105, the base 5 are 4,124,217,561,781.

13.2.2: see 13.1.7, or use (3^p-1)/(3-1)*(3^p+1)/(3+1), where p is a prime not dividing 24.

13.6.4: 3200=128*25, Let's compute 1163²⁵ mod 3201. It is -1 so 3201 is a strong pseudoprime base 1163.

E1: Let's try 2: 2²¹=122, 2⁴²=4130, 2⁸⁴=1056, 2¹⁶⁸=2097, 2^2*168=4400, 2^4*168=2800, 2^8*168=334, 2^16*168=4016, 2^64*168=2633 not 1, therefore composite. Note that the base 45²¹ gives 5093, then 1 so too many square roots of 1, also composite.

E2: First check that 11 is a primitive root so that this log is guaranteed to exist:

11^9828/2=-1, 11^9828/3=9080, 11^9828/7=4013, 11^9828/13=3654, none are 1 so 11 is primitive mod 9829.

The answer to 11^x=5 mod 9829 is x=6570. Let's find x mod 4, mod 27, mod 7 and mod 13, and use the C-R-T to then find x mod 9828.

For x=x0+2*x1+4*M, where x0 and x1 are between 0 and 1: Raise 11^x=5 mod 9829 to the power 9828/2 to get (-1)^x0=1 so x0=0. Then raise to the 9828/4 to get 9828^x1=-1, so x1=1, and x=2 mod 4.

For x=y0+3*y1+9*y2+27*M, as before raising to the power 9828/3 gives 9080^y0 =1, so y0=0. Next try power 9828/9, 9080^y1=1, so y1=0. Finally the power 9828/27 gives 9080^y2=9080, so y2=1, and x=9 mod 27.

For mod 7, x=z0+7*M, z0 between 0 and 6, raise to the power 9828/7, 4013^z0=3981, so z0=4, and x=4 mod 7.

For mod 13 x=w0+13*M, w0 between 0 and 12, raise to the power 9828/13, 3654^w0=3748, so w0=5, and x=5 mod 13.

The solution to x=2 mod 4, x=9 mod 27, x=4 mod7 and x=5 mod 13 is x= 6570 mod 9828.

Directions: Do Problems E1 and E2 if you have the computing power, otherwise do E1' and E2'. The web site Fast Modular Exponentiation could be used for E1' and E2'.
Or here is one I made up specifically for you!

E1. Let p=247024115713. Prove that p is strong pseudoprime base 2,3 and 5. Prove p is prime using the Pocklington-Lehmer criterion. You may use p-1=2¹³*3²*11*17*19*23*41.

E2. Let n=1079580678399507500353. Show that n is not a Fermat pseudoprime. Factor n, using either Pollard's p-1 or Pollard's rho method. Prove your factors are prime.

E1'. Let p=308272901. Prove that p is strong pseudoprime base 2,3 and 5. Prove p is prime using the Pocklington-Lehmer criterion. You may use p-1=2²*5²*13²*17*29*37.

E2'. Let n=579763409. Show that n is not a Fermat pseudoprime. Factor n, using either Pollard's p-1 or Pollard's rho method. Prove your factors are prime.

E1: Check that 2^p-1=1 mod p, 3^p-1=1 mod p, 5^p-1=1 mod p. The values for 2^(p-1)/2k mod p, k from 13 to 0 are not equal to 1, -1 until you hit -1 at k=3 then 1,1,1 so it passes the Miller-Rabin on base 2. For base 3 it hits -1 at k=6 (not before), and for base 5 at k=1.

To prove p is prime write K=2¹³*3²*11, which is greater than the square root of p. We need the special bases for the primes 2,3,and 11. GCD(2^(p-1)/11-1,p)=1, GCD(5^(p-1)/2-1,p)=1, GCD(2^(p-1)/3-1,p)=1.

E2:2^n-1 =578101392302318026451 mod n, so n is not a Fermat pseudoprime.

Using Pollard's p-1 method with 9 primes reveals a factor of 247024115713, prime from E1, the other factor is 4370345281. This is prime, using Pocklington-Lehmer, 4370345280= 2⁶*3⁵*5¹ *7²*31¹*37¹, we need to find the bases for primes 2,3 and 5; 17 works for 2 and 3, and 2 works for 5.

Pollard's rho takes 42752 iterations for seed (2,2), 9432 for (3,3) 14148 for (7,7).

E1': Check that 2^p-1=1 mod p, 3^p-1=1 mod p, 5^p-1=1 mod p. The values for 2^(p-1)/2k mod p, k from 2 to 0 are -1 at k=2 then 1 afterwards, so it passes the Miler-Rabin on base 2. For base 3 it hits 1 at k=2, and for base 5 it hits -1 at k=2 and is 1 afterwards.

To prove p is prime write K=2²*5²*13²*17, which is greater than the square root of p. We need the special bases for the primes 2,5,13, and 17, base 2 works for all 4 primes.

E2': 2^n-1 =477697304 mod n, so n is not a Fermat pseudoprime.

Pollard's p-1 takes the first 5 primes to reveal 30493 (note that 30492=2*2*383*7*11), which is prime, while the rho method needs 53 iterations for seed (2,2) to find 30493, 7 iterations to find 19013 with seed (4,4). 30493 and 19013 are both prime.

7.1-7.5 (primitive roots RSA, discrete logs)
8.1-8.2 (primes and the PNT)
9.1, 9.5 (Fermat's little theorem and exponentials)
10-1-10.4,10.6,(C-R-T, Hensel's lemma, Euler's theorem on \phi(n))
13.1,13.2,13.5,13.6 pseudoprimes
18.1-18.5 (Pollard p-1 rho, Pocklington-Lehmer)

1. Using Hensel's lemma and the C-R-T find a solution to x²=14 mod(125*169).

2. Prove that 2 is a primitive root of 7933.

3. Give an example of a non-prime integer n such that x²-1=0 mod n has more than 2 solutions.

4. What is 79^10123+1 mod 101?

5. What is 16^100999+2 mod 1111?

6. Suppose that p is a prime which is at least 11. Prove there exists integers A and B such that 5*A+B*p=1, and use A and B to find a solution to the two equations x=2 mod p, x=1 mod 5.

7. Prove that 3 is a primitive root mod 1481 and find log₃(100) mod 1481.

8. TRUE or FALSE? Let p be an odd prime. Let d divide p-1. If x and y both are dth roots of 1 mod p, then x*y is also a dth root of 1 mod p.

9. Suppose I randomly choose an integer from 1 to 1480. What is the probability that it is a primitive root mod 1481?

10. Show that 2 is a Fermat pseudoprime mod 12801. Is it strong pseudoprime mod 12801?

11. TRUE or FALSE? 15841 is a strong pseudoprime base 2, but not base 3,5,7.

12. Use RSA modulus n=9461*13903=131536283, encryption exponent e=13 to encrpyt "20051920". What is the decryption of "84115120"?

13. Suppose that p is a prime and p=1 mod 3. Prove that exactly (p-1)/3 non-zero elements in Z/p are cubes, and 2(p-1)/3 elements in Z/p are not cubes. Show how this works for p=7.

14. TRUE or FALSE? There is no solution to x=2 mod 4, x=1 mod 6.

15. Test p=30³²+1 for primality using the Miller-Rabin test. Then establish primality using Pocklington-Lehmer. Why would n=p*q, for some other choice of a prime q, be a poor choice of an RSA modulus?

16. Suppose that p is an odd prime, A is a positive integer, and that n=(2p)^A+1 is also prime. What is the probability, if you choose an integer at random from 1 to n-1 k times, that none of them are primitive roots mod n?

17. Let n=10¹⁰⁰. Does there exist an x relatively prime to n such that x⁷=1 mod n?

Exam #2 results

median=73

A 90-100 (4)
B 70-89 (16)
C 50-69 (10)
D 40-49 (1)
F 0-39 (1)

Solutions to Exam #2

1. 1*(4n+1)-4*n=1, so GCD(4n+1,n)=1. By the C-R-T the solution is x=13*1*(4n+1)-2*4*n mod (n*(4n+1)), or x=44*n+13 mod (n*(4n+1)).

2. Let x=7^(n-1)/2 mod n. Then x is not 1 or -1 mod n, but x²=1 mod n. So mod n there are at least three solutions to x²=1 mod n, so n cannot be prime. Namely n fails the Miller-Rabin test.

3. 37 and 43 are prime, so \phi(n)=36*42=2*2*2*3*3*3*7=1512. Encyption exponents e must be relatively prime to \phi(n), so e=3 does not work. The smallest available e is e=5, GCD(5,36*42)=1. Since 605*5-2*1512=1, the inverse of 5 mod 1512 is d=605.

4. 3,5,17, and 257 are prime, so \phi(n)=2*2² *2⁴*2⁸ =2¹⁵. By Euler's theorem, A^\phi(n)=1 mod n, so A raised to 2¹⁵*B is 1 mod n for any positive integer B, for example B=3⁴¹⁵. So the answer is A.

5. The table is

2 2 323
6 38 1
38 139 1
154 21 19

reveals 19 and thus also 17.

6. The exponents e that work must be relatively prime to p-1=6*q. So e has no 2,3, or q (if q>3) in its prime factorization. Proof: We know that x has order p-1, so x^p-1=1 mod p, and any power x^P =1 mod p must have that P is a multiple of p-1. Suppose that x^e has order p-1, this means x^e*t=1 mod p, t=p-1, but no smaller positive exponent t works. So e*t is never a multiple of p-1 for t less than p-1, this means GCD(e,p-1)=1. Conversely, if GCD(e,p-1)=1, t*e is a multiple of p-1 means that t is a multiple of p-1, so x^e has order p-1 if GCD(e,p-1)=1.

9.6: 4, 6, 9.8:2 ( this question is cancelled), 10.5: 2,4, 10.8: 2,3, 12.5: 2, 4,7,11,12

E1: Use 66202²=4 mod 202903 to factor 202903.

E2: Either show that 31 is not a square mod 2025 or find at least one square root of 31 mod 2025. (You may have to use Hensel's lemma.)

E3: Use 21947²=2³3³ mod 198791 and 997²=2¹3³ mod 198791 to factor 198791. (Hint: Get all even exponents of 2 and 3.)

Solutions to HW #5

9.6,4: 71 is prime, so 50^(71+1)/42=50 mod 71.

9.6.6: 1039 is prime so 2^(1039+1)/42=2 mod 1039.

10.5.2: 203608²-43²=(203608+43)*(203608-43), and GCD(204889,203608+43)=619, GCD(204889,203608-43)=331, the two prime factors are 331 and 619.

10.5.4: 10.5.2: 172719²-31²=(172719+31)*(172719-31), and GCD=691, GCD(173441,172719-31)=251, the two prime factors are 251 and 691.

10.8.2: 101 is prime, check 14^(101-1)/2 mod 101=1, so yes 14 is a square mod 101.

10.8.4: 101 is prime, check 69^(101-1)/2 mod 101=100=-1, so no 69 is not a square mod 101.

12.5.2: 1033 is prime, so 1033=1 mod 4 so yes -1 is a square mod 1003, and (-1/1033)=1.

12.5.4:1033 is prime, (2/1033)=1 so yes 2 is a square mod 1033.

12.5.7: 1009 is prime. (119/1009)=(1009/119)=(57/119)=(119/57)=(5/57)={57/5)=(2/5)=-1. No, 119 is not a square mod 1009.

12.5.11: 2009 is not prime, (2/2009)=(-1)^{(2009*2009-1)/8}=1. This does not necessarily mean that 2 is a square mod 2009! But 2009=7*7*41, and 2 is a square mod 41, and mod 7, so we just need to check that is square mod 7*7 using Hensel's lemma, then use the C-R-T to get that 2 is a square mod 2009.

12.5.12:(3/2009)=-1, so definitely no 3 is not a square mod 2009.

E1: GCD[66200, 202903]=331 is a factor as is GCD[66204, 202903]=613.

E2: (31/2025)=1, and 2025 is not a prime, so 31 may or may not be a square mod 2025=3*3*3*3*5*5. It is a square, the four square roots are 191, 434, 1591, and 1834.

Here is how to find one of these four. 31=1 mod 3 so mod 3 it is a square say 1. Then take 1+3*x2 as a solution to x²2-31=0 mod 9, by Hensels' lemma 2*x2=-(-10)=10 mod 3, or x2=2.

Now we have 1+2*3+x3*9 as a solution mod 27, 2*x3=-(18/9) mod 3 or x3=2.

Next we have 1+2*3+2*3*3+x4*3*3*3 mod 81, Hensel's lemma gives 2*x4=-(594/27) mod 3 or x4=1. So our solution mod 81 is 1+2*3+2*3*3+1*3*3*3=52.

For mod 5 we again start with y1=1, then 1+y2*5, 2*y2=-(-6) mod 5 so y2=3, and the solution is 16 mod 25.

Then use the C-R-T to get a solution mod (81*25)=2025: 13*25-4*81=1, so the solution mod 2025 is 52*13*25-16*4*81=1591.

E3: We have (21947*997)²=(4*27)² mod 198791, so take GCD(21947*997-4*27,198791)=739 and GCD(21947*997-4*27,198791)=269 to get 739*269=198791.

1. Suppose that n is an odd integer which is at least 1000, and some integers A, B and C satisfy A^B=C mod n and A^2B=1 mod n, where C is between n/2 and 2n/3. Prove that n is not prime.

2. Check that 2465 is a Carmichael number.

3. p=1632899 is a prime number. To check that 2 is primitive mod p, which congruences should you check?

4. If an affine cipher A(x)=a*x+b mod 100 is used, what conditions on a do we need to decrypt?

5. True or False? If p is an odd prime and q is another odd integer coprime to p, then q^p-1=1 mod (2p).

6. Prove that 613 is prime using the Pocklington-Lehmer criterion.

7. Solve x²=7 mod 81 using Hensel's lemma.

8. 41299 is prime. Is 5877 a square mod 41299?

9. Solve the simultaneous modular equations 4x+5=3 mod 13 and 3-2x=16 mod 17.

10. Use the Pollard rho method to factor 143861. Use seed (3,3).

11. Use Pollard's p-1 method to factor 143861.

12. If RSA modulus n=143861 is chosen, can e=7 be used as an encryption exponent?

13. Compute 878757^{(876978659633 - 1)/2} mod 876978659633 and the Jacobi symbol (878757/876978659633). Is 876978659633 prime?

14. Find the smallest positive integer x such that GCD(x,111)=1 and 111 is a Fermat pseudoprime mod 111.

15. True or False? x¹⁴=1 mod 15 for all x such that 15 does not divide x.

16. Suppose p is prime and GCD(x,p)=1. What is x^p3-p2 mod (p²)?

17. Use the Euclidean algorithm to find GCD(112,376).

18. 4159 is prime. Show that 3 is primitive mod 4159, and find log₃(2) mod 4159.

19. Find the smallest odd integer n such that (2/n)=1 but 2 is not a square modulo n.

20. Suppose I publish n=83769295013316379 as an RSA modulus, and you find out that \phi(n)=83769294395137176. How do you factor n from this information?

90-100 A (3)
70-89 B (14)
50-69 C (12)
40-49 D (2)
0-39 F (1)

Code Final Exam Score Final Grade

Shinigami 72 B-
Jamba Juice 77 B
pickles 69 B-
SAD 83 A-
copacetic 73 B
kangaroo 60 A-
NoLegsMan 80 B
TFTDUP90 80 B-
uptheladder 88 A-
Justice 90 A-
Vigenere 68 B
Riemann 100 A
NMALIORHB 62 B
Iscored 83 B+
TrogodorTheBurninator17 99 A
JohanSantana 70 B
Alpha 81 B+
Xmas 41 D
gungaden 68 B
8675309 65 C+
GIVEMEA 67 B
EFINE 64 B-
greenwoof 64 C
kaviscout 82 B+
HELPMEEULERGETA'B'YOUAREMYONLYHOPE 81 B
cactus 53 C+
YEAHMATH 77 A-