Shor’s for the DLP
Math 202 Cryptography
November 11, 2024

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Function for quantum part of Shor’s to attack the DLP (α^x)≡β mod p where ord(α) is prime

functionPeriod[p, α, β] returns the period of the function f(x,y) = (α^x)(β^y) mod p
Note this will be very slow and should only be used on small-ish values of p

functionPeriod[p_, α_,β_]:=Module[{f,foundOne, fxy,fxyList,a,i,j, preva,prevx,prevy,αorder,period}, 

f[x_,y_]:= Mod[ PowerMod[α,x,p]*PowerMod[β,y,p],p];

fxyList ={}; (* List that will hold values of f(x,y) to look for collision *)
foundOne=False;
αorder=MultiplicativeOrder[α,p]; (* Good thing we have access to a quantum computer *)
a=1; (* Counter used to create powers of α and β *) 

(*Loop through looking for a good collision *)
While[foundOne == False,
i=Floor[a/αorder]+1; (* The power of α *)
j=Mod[a,αorder]+1; (* The power of β *)
fxy=f[i,j];

If[MemberQ[fxyList,fxy]==True, (*If f(i,j) occurs in list *)

preva=Position[fxyList,fxy][[1,1]]; (* Find index of collision with f(i,j) *)
prevx = Floor[preva/αorder]+1; (*Convert index to powers of α and β in collision *)
prevy = Mod[preva,αorder]+1;

If[Mod[prevx-i,p]!= αorder, (*Make sure period is of proper type *)
foundOne=True;
period={Mod[prevx-i,αorder], Mod[prevy-j,αorder]}
];
];

(*Else, if not in the list, add it and try next pair of powers *)
AppendTo[fxyList,fxy];
a++ 
];
Print["Period = ",period]
]

Let’s find the period of the function f(x,y) for the DLP   (4^d)≡12 mod 83

functionPeriod[83,4,12]