Jim Belk University of Glasgow

Homework 9

Due Date: Friday, April 15

  1. The Fermat primality test uses the following procedure to check whether a number \(p\) is prime:
    • Choose a random number \(a\) between \(1\) and \(p-1\).
    • Check whether \(a^{p-1} \equiv 1\;(\mathrm{mod}\;p)\). If not, then \(p\) isn't prime.
    A number \(p\) that passes several iterations of the Fermat test is very likely to be prime.
    1. Write a function FermatTest that uses ten iterations of the Fermat test to check whether a number is prime.
    2. Use your function from part (a) to find the smallest prime number greater than \(10^{100}\).
    3. Use your function from part (a) to find the smallest pair of twin primes greater than \(10^{100}\).
    4. Use your function from part (a) to find the smallest Sophie Germain prime greater than \(10^{100}\).
    1. Write a function IsPrimitive that takes a prime \(p\) and a number \(a\) as input and tests whether \(a\) is a primitive element modulo \(p\). (Use a built-in SageMath or Mathematica function to factor \(p-1\).)
    2. Use your program from part (a) to compute the smallest primitive element modulo 56647695441392941981.
    1. Write a function DiscreteLog that takes a prime \(p\), a primitive element \(g\), and a number \(h\) as input and uses brute force to search for a number \(a\) such that \(g^a \equiv h\;(\mathrm{mod}\;p)\).
    2. You are eavesdropping on Alice and Bob as they use the Diffie-Hellman protocol to agree on a secret encryption key. They decide to use the modulus \(2p+1\), where \(p = 851321\) is a Sophie Germain prime, and primitive element \(g=2\). If Alice sends \(h_1 = 205593\) to Bob and Bob sends \(h_2 = 287047\) to Alice, what is their shared key?