Witnesses for the Composite
Math 302 Advanced Cryptography
March 6, 2019

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Check some specific values

2 is a witness for n=123

n=123;
PowerMod[2,n,n]

n=409

n=409;
Table[{i,PowerMod[i,n,n],i==PowerMod[i,n,n]},{i,1,n-1}] // TableForm

n=561

n=561;
Table[{i,PowerMod[i,n,n],i==PowerMod[i,n,n]},{i,1,n-1}] // TableForm

FactorInteger[561]

Bummer! 561 is a Carmichael number. It is composite but has no witness

Miller-Rabin witnesses

Verify Prop 3.17 for p=2377

p=2377;
q=297;
k=3;
powers=Table[ 2^i * q, {i,0,k-1}]

a=2;
PowerMod[a,powers,2377]

2 is a MR Witness for 25, 7 is not

n=25;
2^3 * 3

k=3; q=3;
powers = Table[2^i*q, {i,0,k-1}]

a=7;
PowerMod[a,powers, n]

2 is a MR Witness for 561

n=561;
2^4 * 35

k=4; q=35;
powers = Table[2^i*q, {i,0,k-1}]

a=2;
PowerMod[a,powers, n]

Define a mrWitness[ ] function

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

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

If[Mod[aq,n]==1,Return[False]];

i=0;
While[i<k,If[Mod[aq+1,n]==0,Return[False]];
aq=Mod[aq^2,n];
i++];

Return[True]
]

Let’s check some specific values

mrWitness[2,25]