A Miller-Rabin witness function 
Math 302 Cryptography
February 19, 2025

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

The MR Witness function

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

(* Factor out the powers of 2 from n-1 and find q *)
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 not a MR witness *)
If[PowerMod[a,q,n]==1,
Return[False]
];

(* Now check second condition *)
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], 
(* else *) Return[True]
];

]

Now finding some witnesses

n=2465
mrWitness[2, n]

Let’s look for non-MR witnesses less than 100

n=2465
For[i=2, i<100, i++,
If[ mrWitness[i, n]==False,
Print[i]
]
];

Calculate the proportion of MR Witnesses < n

n=2465;
numW=0;
For[i=2, i<n, i++,
If[ mrWitness[i, n]==True,
numW++
]
];
Print["numW = ", numW, "\nProportion = ", N[numW/n]]