Problem Sheet Exercises 8
Jim Laird
April 12, 2021
1. Suppose Oscar receives the ciphertexts 83, 36 and 37, which he knows are
the encryptions of the same plaintext using the exponent 3, and moduli
143, 119 and 95 respectively. Without factorizing, recover the plaintext.
2. How many primitive elements are there modulo p = 11? Describe the
method you should use to find all the primitive elements modulo a prime
p if you wish to minimise the computation required. Find all the primitive
elements modulo 11.
3. Consider the group of integers mod n, with addition. What are the
generators for this group. How can discrete logarithms be computed?
4. Implement Shanks’s algorithm, and use it to compute the discrete logarithm
of 525 to base 3 modulo 809.)
5. (Ex 6.5 from Stinson). Use the factor base {2, 3, 5, 7}, the exponents
4063, 5136, 9865 and the “random” exponent s = 7736 to compute the
discrete logarithm of 9451 to base 5, modulo 10007.
1