Johnny Chen

Math 124 Problem Set 3

1. In PARI, s = (g^{n})^{1208}=lift(Mod(454, 3793)^{1208}) = 2156.

2a. VE RI TAS encodes to

22 + 5 · 27 + 0 · 27^{2} + 18 · 27^{3} + 9 · 27^{4} + 0 · 27^{5} + 20 · 27^{6} + 1 · 27^{7} + 19 · 27^{8} = 5384375093542.

2b.We assume we cannot use consecutive blank spaces, so the longest sequence would be of the form A A A ...A. We seek the maximal n for which 1 + 27^{2} + ... + 27^{2N} < 10^{20}; if the remainder is greater than 27^{N+1}, we can place another A. Therefore (27^{2N+2} − 1)/26 < 10^{20}, so N = 6. Now 10^{20} − (27^{14} − 1)/26 > 27^{13}, so our longest sequence is 14 letters.

3. Write a discrete log program: f(n) = for(i = 1, 96; if(n == lift(Mod(5, 97)^{i}), return(i))); Then f(3) = n=70 and f(7) = m=31. Therefore lift(Mod(5, 97)^{mn}) = s=44.

4. We encrypt m by computing m^{e}(mod n). In PARI, lift(Mod(2005, n)^{e}) = 346299873425.

5a. Since ed ≡ 1(mod ϕ(n)), d = lift(Mod(e, eulerphi(n))^{−1}) = 5195621988839.

5b. To decrypt, lift(Mod(3539014000459, n)^{d}) = 18464, which gives: WHY.

6. No, it’s not secure. An adversary can use Michael’s public key to encrypt each of 0,1,...,26. Then the adversary can match each letter that Nikita sends, one by one, and decrypt her message without having to break the cryptosystem.

7a. Let m = ed − 1, and try for(a = 2, 20, if(Mod(a, n)^{m}! = 1, print(a))); if it prints nothing, set m = m/2 and try again, until we have an m such that there are values for a. We decrease m three times before we find a value m = 47918... with a values 2, 3, 5, 7, 8, .... If we try gcd(lift(Mod(i, n)^{m} − 1, n)) for these a values, we see that for a = 7 we have a p = gcd(7, n) = 37865717, so q = n/p = 37865693.

7b. If we know p and q are close, we use the Fermat factorization method. We set the precision to p150 in PARI, and then set t = floor(sqrt(n)) + 1 = 37865705, and find sqrt(t^{2} − n), which seems to be 12. Now t + s, t − s are our factors: t + s = 37865717, t − s = 37865693, as in part a.