Jim Belk University of Glasgow

Homework 10

Due Date: Friday, April 22

    1. Write a function DiscreteLog that uses the baby step-giant step algorithm to solve discrete logarithm problems. The function should take a triple \((g,h,p)\) as input, where \(p\) is a prime, \(g\) is a primitive root modulo \(p\), and \(1\leq h < p\), and output a solution to the equation \[ g^x \,\equiv\, h\;(\mathrm{mod}\;p). \] Make sure to use an efficient built-in function such as Mathematica's Intersection[] function or the set.intersection() method in Python to find a match between the two lists.
    2. Use your function from part (a) to find the discrete logarithm in the case where \(g\) is 7, \(h\) is 1103096137808, and \(p\) is 1991661221551.
  2. Let \(p = 4k-1\) be a prime. Prove that \[ \biggl(\frac{d}{p}\biggr) \,=\, 1 \] for every positive divisor \(d\) of \(k\). Make sure that your proof works for every positive divisor.
  3. Let \(p>2\) be a prime. Prove that \[ \sum_{k=1}^{p-2}\biggl(\frac{k(k+1)}{p}\biggr) \,=\, -1. \]
  4. Let \(p>2\) be a prime. Prove that \[ \Biggl(\,\sum_{k=0}^{p-1} \cos\biggl(\frac{2\pi k^2}{p}\biggr)\Biggr)^{\!\!2} \,=\, \begin{cases}p & \text{if }p\equiv 1\;(\mathrm{mod}\;4), \\[3pt] 0 & \text{if }p\equiv 3\;(\mathrm{mod}\;4).\end{cases} \] Note: The \(\displaystyle \frac{2\pi k^2}{p}\) here is just a fraction.