Math 124, HW #10, Page 1, December 12, 2001  Student, F.

1. We wish to demonstrate the ElGamal encryption system. There’s some text on the

matter at http://www.ccs.neu.edu/home/yiannis/papers/eg.ps.

We’re simple minded folk here, so we’re going to use a curve from homework 8, y^{2} = x^{3} + x + 1, over the finite field ℤ/5ℤ. We showed that the group structure of this curve is C_{9} and the group is generated by (0, 1). In this simple example, Nikita wishes to send Michael the point (2, 4). First, Nikita and Michael choose secret integers n (= 3) and m (= 2) and publish nB and mB:

? e = ellinit([0,0,0,1,1]*Mod(1,5));
? g = ([0,1]*Mod(1,5));
? nB = ellpow(e,g,3)
%13 = [Mod(2, 5), Mod(1, 5)]
? mB=ellpow(e,g,2)
%14 = [Mod(4, 5), Mod(2, 5)]

So, Nikita has published the point (2, 1) and Michael has published the point (4, 2). (The elliptic curve is well known.) In theory, our elliptic curve has a much bigger order, so it’s not obvious that (2, 1) = 3 · (0, 1). Nikita wishes to send Michael the message (2, 4), which means “Order me a cheeseburger!”.

? P = ellpow(e,g,6)

So, Nikita chooses a random number r, which happens to be 5, and sends Michael (rB, P + r(mB)). So:

? rB = ellpow(e,g,5)
%16 = [Mod(3, 5), Mod(1, 5)]
? rmB=ellpow(e,mB,5)
%19 = [Mod(0, 5), Mod(1, 5)]
? pPrmB=elladd(e,P,rmB)
%23 = [Mod(4, 5), Mod(3, 5)]

At this point, Michael receives the message ((3, 1), (4, 3)). Michael knows m (= 2), so he computes m(rB):

? mrB=ellpow(e,rB,2)
%21 = [Mod(0, 5), Mod(1, 5)]

And subtracts that from the second half of the message:

? ellsub(e,pPrmB,mrB)
%25 = [Mod(2, 5), Mod(4, 5)]

Lo and behold, Michael has retrieved the secret message, (2, 4)!

2. I was kind of curious how well the Pollard method works on small numbers, so I implemented the functions given in the notes and computed:

? N=17^3*31
%12 = 152303
? B=10
%13 = 10
? m=lcmfirst(B)
%14 = 2520
? gcd(2^m-1,N)
%15 = 527

We are left with N = 289 · 527. And we can use the method again:

? gcd(2^m-1,289)
%17 = 17
? gcd(2^m-1,527)
%18 = 527             \\ A little trouble
? B = 4
%19 = 4
? m = lcmfirst(B)
%20 = 12
? gcd(2^m-1,527)
%21 = 1               \\ Some more trouble
? B = 6
%22 = 6
? m=lcmfirst(B)
%23 = 60
? gcd(2^m-1,527)
%24 = 31
? 527/31
%25 = 17

So we have (surprise, surprise), N = 17^{3}·31. 30 is 5-power-smooth, so it’s no surprise that B = 4 didn’t work.

At http://www.users.globalnet.co.uk/~aads/Pminus1.html, there’s a list of big

numbers factored using this algorithm. Unfortunately, the numbers there are too big for our implementation—we get stuck at lcmfirst().

3. Let’s try to factor the same N using ECM.

? N=289*527
%48 = 152303
? m = lcmfirst(10)
%51 = 2520
? e = ellinit([0,0,0,random(N),1]*Mod(1,N));
? ellpow(e,[0,1]*Mod(1,N),m)
  ***   impossible inverse modulo: Mod(17, 152303).
? e=ellinit([0,0,0,random(N),1]*Mod(1,N));
? ellpow(e,[0,1]*Mod(1,N),m)
  ***   impossible inverse modulo: Mod(31, 152303).

That’s kind of neat—since there’s an element of randomness in here, we found two factors. We are left with 289,

? e=ellinit([0,0,0,random(N),1]*Mod(1,N));
? ellpow(e,[0,1]*Mod(1,N),m)
  ***   impossible inverse modulo: Mod(17, 289).

And we’re done. We’ve factored N again.

Mathematica provides a package called “NumberTheory‘FactorIntegerECM‘”. If you look at the top of the file, he describes the algorithm the function uses, based on some paper by some guy named Montgomery.

4. Claim: Fermat’s last theorem is false in the ring ℤ/pℤ when p is an odd prime. Proof: When p = 2, in order that xyz ≠ 0, we must have x = y = z = 1. Regardless of n ≥ 3, we have:

1^{n} + 1^{n} = 1^{n}
1 + 1 = 1
0 = 1.

That’s patently false, so we’re done.

Now consider p odd prime. Let x = y = 1 and let z = \frac{p+1}{2}. For n = 2p − 3, we wish to show that Fermat’s last theorem is false. First, note that z and 2 are inverses:

\frac{p + 1}{2} · 2 ≡ p + 1 ≡ p (mod p).

Using this and Fermat’s Little Theorem, we can compute z^{n}:

2^{2p−2} (\frac{p + 1}{2})^{2p−2} ≡ 1 (mod p)
2^{p−2}2^{p−1} (\frac{p + 1}{2})^{2p−2} ≡ 1 (mod p)
\underbrace{2^{p−1}2^{p−1}}_{=1by FLT}(\frac{p + 1}{2})^{2p−2} ≡ 2 (mod p)

(\frac{p + 1}{2})^{2p−2} ≡ 2 (mod p)

So, we have:

1^{2p−3} + 1^{2p−3} ≡ (\frac{p + 1}{2})^{2p−3} (mod p)
1 + 1 ≡ 2 (mod p). TRUE!

So we’ve found a counterexample to Fermat’s Last Theorem.