IV054 Coding, Cryptography and Cryptographic Protocols
2008 ­ Exercises VIII.
1. Factor n = 923 using the elliptic curve E : y2
= x3
+ 2x + 9 (mod n) and the
point P = (0, 3). Show the computation steps.
2. Let P be a point on an elliptic curve E : y2
= x3
+ax+b (mod n) where n > 1.
Prove that there exist i, j  N, i = j, such that iP = jP.
3. (a) Factorize 229
- 1 using the second Pollard -algorithm with f(x) = x2
+ 1.
(b) Use the Pollarďs p - 1 method to factor n = 8549 with a = 50 and b = 17.
4. For a modulus n, an exponent e is called a universal exponent if xe
 1 (mod n)
for all x with gcd(x, n) = 1.
Universal Exponent Factorization Method
Let e be a universal exponent for n and set e = 2b
m where b  0 and m is odd.
Execute the following steps.
(i) Choose a random a such that 1 < a < n - 1. If gcd(a, n) > 1, then we have
a factor of n, and we terminate the algorithm. Otherwise go to step (ii).
(ii) Let x0  am
(mod n). If x0  1 (mod n), then go to step (i).
Otherwise, compute xj  x2
j-1 (mod n) for all j = 1, . . . , b.
* If xj  -1 (mod n), then go to step (i).
* If xj  1 (mod n), but xj-1  1 (mod n), then gcd(xj-1 - 1, n) is a
nontrivial factor of n so we can terminate the algorithm.
(a) Use the algorithm above to factor n = 76859539 with the universal exponent
e = 12807000.
(b) Find a universal exponent for n = 2a+2
. Justify your answer.
5. Let n > 0 be an integer. Show that n is a prime if and only if for any k 
{1, 2, . . . , n - 1} n
k
is divisible by n.
6. Consider the elliptic curve E : y2
= x3
+ 568x + 1350 (mod 1723) and the point
X = (524, 1413). Compute the point 144X.
7. Consider the eliptic curve E : y2
= x3
+ x + 3 (mod 11).
(a) Find a group isomorphic to the eliptic curve E.
(b) Suppose that Alice and Bob use E in the elliptic version of the ElGamal
scheme.
Alice chooses Q = (9, 9) and a secret number k. Then she computes P =
k(9, 9) = (6, 7) and makes P public. Bob chooses a message M, a random
number r and sends Y1 = rQ = (5, 10) and Y2 = M + rP = (1, 4) to Alice.
Your task is to find M.