1807.sagews

This worksheet was produced by Ken Ribet in connection with the spring, 2010 crytography course at UC Berkeley.  The course uses using the textbook ``An introduction to mathematical cryptography'' by Hopffstein, Pipher and Silverman.  In section 4.5 of the book, the authors talk about the Pollard $\rho$ method for finding discrete logs.  In this worksheet, Ken implements the method to find a discrete log for the prime $144169$.  Amazingly, the method worked!

def experiment(n):
   if n==0:  return
   elif v[n-1][0] < floor(p/3): v.append([Mod(g*v[n-1][0],p),v[n-1][1],Mod(v[n-1][2]+1,p-1),n]); return
   elif v[n-1][0] < floor(2*p/3): v.append([Mod(v[n-1][0]^2,p), Mod(2*v[n-1][1],p-1), Mod(2*v[n-1][2],p-1),n]); return
   else: v.append([Mod(h*v[n-1][0],p),Mod(v[n-1][1]+1,p-1), v[n-1][2],n ]); return

The code above is supposed to make the recursive Pollard $\rho$ sequence $x_i$ as in the book.  Since I'm no programmer, you can surely do better.  For each $i$, starting with $i=0$, I create a 4-tuple $(x_i,a_i,b_i,i)$, where $x_i = h^{a_i}g^{b_i}$.

This initializes the matrix of 4-tuples---I supply the first line:

v=[[1,0,0,0]]

p= 144169

primitive_root(p)

\newcommand{\Bold}[1]{\mathbf{#1}}23

I take $g$ to be the smallest primitive root mod $p=144169$, which you know to be one of my favorite primes.  For $h$, I take 2010; why not?!

g = Mod(23,p)

h = Mod(2010,p)

By running the ``experiment'' program 50 times, I build up the matrix of 4-tuples.

for i in range(50):
    experiment(i)

m=matrix(ZZ,v)

The matrix command turns the list $v$ into a matrix with integral coefficients.

show(m)

\newcommand{\Bold}[1]{\mathbf{#1}}\left($$\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 23 & 0 & 1 & 1 \\ 529 & 0 & 2 & 2 \\ 12167 & 0 & 3 & 3 \\ 135672 & 0 & 4 & 4 \\ 77141 & 1 & 4 & 5 \\ 14237 & 2 & 8 & 6 \\ 39113 & 2 & 9 & 7 \\ 34585 & 2 & 10 & 8 \\ 74610 & 2 & 11 & 9 \\ 142841 & 4 & 22 & 10 \\ 69931 & 5 & 22 & 11 \\ 132281 & 10 & 44 & 12 \\ 37174 & 11 & 44 & 13 \\ 134157 & 11 & 45 & 14 \\ 59540 & 12 & 45 & 15 \\ 40059 & 24 & 90 & 16 \\ 56343 & 24 & 91 & 17 \\ 76438 & 48 & 182 & 18 \\ 30781 & 96 & 364 & 19 \\ 131287 & 96 & 365 & 20 \\ 57600 & 97 & 365 & 21 \\ 142972 & 194 & 730 & 22 \\ 44903 & 195 & 730 & 23 \\ 23586 & 195 & 731 & 24 \\ 109971 & 195 & 732 & 25 \\ 30633 & 196 & 732 & 26 \\ 127883 & 196 & 733 & 27 \\ 135672 & 197 & 733 & 28 \\ 77141 & 198 & 733 & 29 \\ 14237 & 396 & 1466 & 30 \\ 39113 & 396 & 1467 & 31 \\ 34585 & 396 & 1468 & 32 \\ 74610 & 396 & 1469 & 33 \\ 142841 & 792 & 2938 & 34 \\ 69931 & 793 & 2938 & 35 \\ 132281 & 1586 & 5876 & 36 \\ 37174 & 1587 & 5876 & 37 \\ 134157 & 1587 & 5877 & 38 \\ 59540 & 1588 & 5877 & 39 \\ 40059 & 3176 & 11754 & 40 \\ 56343 & 3176 & 11755 & 41 \\ 76438 & 6352 & 23510 & 42 \\ 30781 & 12704 & 47020 & 43 \\ 131287 & 12704 & 47021 & 44 \\ 57600 & 12705 & 47021 & 45 \\ 142972 & 25410 & 94042 & 46 \\ 44903 & 25411 & 94042 & 47 \\ 23586 & 25411 & 94043 & 48 \\ 109971 & 25411 & 94044 & 49 \end{array}$$\right)

The number $135672$ occurs for $i=4$ and $i=28$.  That's our collision!  We get the equation $g^4=h^{197}g^{733}$, which we can simplify to $g^{729}=h^{143971}$.  (Note that the exponents run mod $p-1$.)  It so happens that $\gcd(143971,p-1)=1$, so that we can solve for the discrete log directly by inverting 143971 mod $p-1$.  In other situations, the gcd might be some number $t>1$.  In that case, we find the discrete log only mod $(p-1)/t$, which leaves $t$ different possibilities for the discrete log.  We then find the true discrete log by checking in turn each of the $t$ possibilities.

When I started computing discrete logs by this method a day or two ago, the first example I ran had $p=1009$, $g=11$, $h=100$.  (Don't ask why I took $h$ to be a perfect square; that was a bit silly, I admit.)  My collision produced the equation $h^{18}=g^{432}$.  Since the gcd in this case is $t=18$, I had the discrete log only mod $(p-1)/18 = 56$: it was 24 mod 56.  The discrete log in this case turned out to be $24+2\cdot 56=136$.

Mod(729/143971,p-1)

\newcommand{\Bold}[1]{\mathbf{#1}}21219

This $21219$ is the discrete log that has been found by the Pollard method.  In the next cell, I call sage's discrete log command to check the work.

log(h,g)

\newcommand{\Bold}[1]{\mathbf{#1}}21219