Miller-Rabin Test for Compositeness &
Finding parameters for DSA

Math 302 Cryptography, March 8, 2017
T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

Definition of procedures

mrWitness[a,n] returns True if a is a MR Witness for the compositeness of n and False otherwise

mrTest[n,r] and mrTestVerbose[n,r] returns True if the random choice of r  random values does not produce a MR Witness for the compositeness of n and returns False if it found a MR Witness. 
In other words, these functions return True if we have evidence that n is prime. 

kbitPrime[k] returns a k-bit value n where 40 random choices of a all returned mrWitness[a,n] == False.
	Thus, the probability that n is composite is (((0.25))^40) = (2^(-80)), so we are fairly confident that n is prime.

parametersDSA[qbits, pbits] returns a pair {q,p} where q is a qbits-bit prime, p is a pbits-bit prime, and q | (p-1)

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]
]

mrTestVerbose[n_,r_]:=Module[{a,g,i},

If[n==2,Print["n=2 is prime"];Return[True]];

If[EvenQ[n],Print[n," is even and composite"];Return[False]];

For[i=1,i≤r,i++,a=RandomInteger[{1,n-1}];
g=GCD[a,n];

If[1<g,Print[n," is composite since ",g," divides ",n];
Return[False]];

If[mrWitness[a,n]==True,Print[n," is composite\n",a," is a Miller-Rabin witness"];
Return[False]]];

Print[n,"\n has no Miller-Rabin witnesses with ",r," random choices and is prime with probability approximately ",N[1-0.25^r,10]];
Return[True]];

mrTest[n_,r_]:=Module[{a,i},
If[n==2,Return[True]];
If[EvenQ[n],Return[False]];

For[i=1,i≤r,i++,
a=RandomInteger[{1,n-1}];

If[GCD[a,n]>1,Return[False]];

If[mrWitness[a,n]==True,Return[False]]
];

Return[True]];

kbitPrime[k_]:=Module[{n,i=1},
n=2*RandomInteger[ {2^(k-2),2^(k-1)}]+1;

While[mrTest[n,40]==False, 
n=2*RandomInteger[ {2^(k-2),2^(k-1)}]+1;
i++];
Print["Required ",i," random choices to find prime"];
Return[n]
]

parametersDSA[qbits_,pbits_ ]:=Module[ {q,p,m,i= 0,j=0,foundp=False}, 
While[ foundp==False, 
q=kbitPrime[qbits];
j++;
For[i=1,(i≤ 4096)&& (foundp==False), i++,
m=RandomInteger[{2^(pbits-1),2^pbits}];
p=m-Mod[m,2*q]+1;
If[mrTest[p,40]==True,
foundp=True];
];
];
Print["Found on choice #",j," of q and choice #",i," of p for this q"];

Return[{q,p}];
]

Examples of using the procedures

Following examples we did by hand in class. . .

mrWitness[2,25]

mrWitness[18,25]

Let’s pick a random 160-bit integer n and use mrTestVerbose[n,10] to see if it is prime

n=RandomInteger[{2^159,2^160-1}]
mrTestVerbose[n,10]

Now let’s look for a 160-bit prime

kbitPrime[160]

Now let’s look for parameters for DSA, verify q | (p-1),  check their primality with Mathematica’s built-in function, and check the number of bits in q and p.

qp=parametersDSA[160,1024]
q=qp[[1]];
p=qp[[2]];
Mod[p,q]
PrimeQ[{q,p}]
IntegerLength[{q,p},2]