March 22, 2021 
Math 302 Cryptography
Spring 2021

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Useful commands for #2 in the Tutorial

This sequence of commands will check if a is a Miller-Rabin witness for n

a=38
n=289

(* Pull out the 2^k factor of n-1 *)
temp=n-1;
k=0;
While[Mod[temp,2]==0,temp=temp/2;k++];
q=(n-1)/2^k;

(* If a^q = 1 mod n, then a is not a MR witness *)
If[PowerMod[a,q,n]==1,Print["Fails condition (i). Not a witness"],
(* Otherwise, check the 2nd condition by building a table a^(2^i q) mod n 
 and checking if -1 = n-1 mod n is in the list. 
If it is, then not a witness. Otherwise, we have one! *)
atable = Table[ PowerMod[a, (2^i) q, n], {i,0,k-1}];
Print[atable];  
If[ MemberQ[atable, n-1]==True,Print["Fails condition (ii). Not a witness"], 
Print["It's a MR witness!"]
];
]

Or, we can put it all together into a function that returns 
True if a is a MR witness for n, and False if it is not.

mrWitness[a_,n_]:=Module[{temp=n-1,k=0,q,atable,i},

While[Mod[temp,2]==0,temp=temp/2;k++];
q=(n-1)/2^k;

If[PowerMod[a,q,n]==1,Return[False]];
atable = Table[ PowerMod[a, (2^i) q, n], {i,0,k-1}];
(*Print[atable];  You can uncomment this if you want to see the values for Condition (ii) *) 
If[ MemberQ[atable, n-1]==True, Return[False], Return[True]
];

]

mrWitness[39,289]

Pollard’s ρ  for factoring

This function will apply the algorithm discussed in class. 
I think it’s fairly self-explanatory.

pFactor[n_]:=Module[{x=1,y=1,g=1,i=1, f},
f[x_]:=Mod[x^2+1,n];

While[g==1, 
x=f[x];
y=f[f[y]];
g=GCD[Abs[x-y],n];
(*Print[i," ", x," ", y, " ", g];  You can uncomment this to see each stage in the sequences*)
i++
];
Print["Collision at i = ",i-1,", x = ",x,", y = ",y,", g = ", g]
]

pFactor[2465]

Template for #5 in Tutorial

I’ll look for a prime between 1000 and 2000
	First, I’ll ask Mathematica for a random integer, 
	then I’ll check 5 random values less than n to see if any are MR witnesses for n
Try this out a few times before adapting it for #5

n=RandomInteger[{1000,2000}]

(* Keep track of whether or not we've found a MR witness *)
noWitness=True;

For[i=1, i≤ 5 && noWitness==True, i++,
a=RandomInteger[{2,n-1}];
(* If gcd(a,n) ≠ 1, then n is definitely not prime *)
If[GCD[a,n]≠1, noWitness=False; Print["a = ",a,", gcd(a,n)>1"],
(* Otherwise, let's check if a is a MR witness *)
If[mrWitness[a,n]==True, noWitness=False; Print["a = ",a," is a MR witness"]]
 ]
]
If[noWitness==True, Print["I'm leaning toward n being prime"]]