The Miller-Rabin Test for primes is one of the most popular methods for testing for prime numbers used in RSA. In this case we will generate a random prime number for a given number of bits. Initially we will generate a random number, and then test it for primality. If it is not, we will keep incrementing it by two until we find a prime number.
Random Prime Generation with PowerShell |
Theory
In the Miller-Rabin test we perform \(k\) trials. If any of these trails returns a false, the value is not a prime number (and is a composite. If it returns a true, it is probably prime. First, we have a number to test (\(n\)) and produce a random number (\(a\)) and then compute \(d\) to solve (and where \(r\) is a value greater than 1):
\(n = 2^d \times r + 1\)
We then compute:
\(x = a^d \pmod n\)
If this is 1 or -1, we return a true value for a prime number. This is coded as:
$a = Get-RandomBigInteger -Min 2 -Max ($n - 1); $x= [System.Numerics.BigInteger]::ModPow($a, $d, $n); If (($x -eq 1) -or ($x -eq ($n - 1))) { return $True }
Next we keep squaring the value of \(x \pmod n\) while the value of \(d\) is less than (\(n-1\)) - and where we double \(d\) in each test. The code is:
While ($d -ne ($n-1)) { $x = ($x * $x) % $n; $d = $d*2 if ($x -eq 1) { return $False } if ($x -eq ($n-1)) { "This is negative" return $True } }
The code for the Rabin-Miller method is then:
function PrimeRabinMiller2($d, $n) { $a = Get-RandomBigInteger -Min 2 -Max ($n - 1); $x= [System.Numerics.BigInteger]::ModPow($a, $d, $n); If (($x -eq 1) -or ($x -eq ($n - 1))) { return $True } While ($d -ne ($n-1)) { $x = ($x * $x) % $n; $d = $d*2 if ($x -eq 1) { return $False } if ($x -eq ($n-1)) { "This is negative" return $True } } return $False }
We can then generate a random odd number, and then test it for primality, if it isn't prime we can increment by two, and test again, until we find a prime number:
"== Random Prime with Miller-Rabin Test == " $randBytes=16 $randBytes = [int]$Args[0] $rand = [Security.Cryptography.RandomNumberGenerator]::Create() $r = [byte[]]::new($randBytes) $rand.GetBytes($r) $val = [Numerics.BigInteger]::new($r) if ($val -le 0) { $val=-$val} if (($val % 2) -eq 0) { $val=$val+1} $flag=$False for ($i=0;$i -le 1000; $i=$i+2) { $is_prime = isItPrime $val 4 if ($is_prime -eq $True) { $flag=$True break } $val=$val+1 } if ($flag -eq $True) { "Random prime size: "+$randBytes+ " Bytes, Bits: "+$randBytes*8 "Random prime: "+$val }
Coding
The code is then:
function GetRandomBigInteger($size) { $rand = [Security.Cryptography.RandomNumberGenerator]::Create() $r = [byte[]]::new($randBytes) $rand.GetBytes($r) $val = [Numerics.BigInteger]::new($r) return ($val) } function PrimeRabinMiller($d, $n) { $a = GetRandomBigInteger 2 ($n - 1) $x= [System.Numerics.BigInteger]::ModPow($a, $d, $n); If (($x -eq 1) -or ($x -eq ($n - 1))) { return $True } While ($d -ne ($n-1)) { $x = ($x * $x) % $n; $d = $d*2 if ($x -eq 1) { return $False } if ($x -eq ($n-1)) { return $True } } return $False } function isItPrime($n, $k) { if ($n -eq 2 -or $n -eq 3 -or $n -eq 5 ) { return $True } $d = $n - 1; while (($d % 2) -eq 0) { $d = $d/2; } for ($i = 0; $i -lt $k; $i=$i+1) { $rtn=PrimeRabinMiller $d $n if ($rtn -eq $False) { return $False; } } return $True; } "== Random Prime with Miller-Rabin Test == " $randBytes=16 $randBytes = [int]$Args[0] $val=GetRandomBigInteger($randBytes) if ($val -le 0) { $val=-$val} if (($val % 2) -eq 0) { $val=$val+1} "Random prime size: "+$randBytes+ " Bytes, Bits: "+$randBytes*8 "`nStarting value:`t"+$val $flag=$False $jumps=0 for ($i=0;$i -le 2000; $i=$i+1) { $is_prime = isItPrime $val 4 if ($is_prime -eq $True) { $flag=$True $jumps=2*$i break } $val=$val+2 } if ($flag -eq $True) { "Random prime:`t"+$val "Jump to find:`t"+$jumps }
A sample run is
== Random Prime with Miller-Rabin Test == Random prime size: 128 Bytes, Bits: 1024 Starting value: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466313195 Random prime: 74694127609839394531423695066683807367213906691835690628010806941823113116341160452233302154382226520304305016921580485423591227892665244629327378091261259183162478412317239748423133148888508256284739076437146819181993895696424719945351704588366388739351351476790041575981862249517999445249166915727466314951 Jump to find: 1756
and for a 512-bit prime:
== Random Prime with Miller-Rabin Test == Random prime size: 64 Bytes, Bits: 512 Starting value: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773387 Random prime: 1570047489143950971158469706647749642676906610685433069032127727599272773500362380171988197033189544118765224161943698783713549815590440492717110990773583 Jump to find: 196
and for a 256-bit prime:
== Random Prime with Miller-Rabin Test == Random prime size: 32 Bytes, Bits: 256 Starting value: 678561933854231032073566346504160285991810520328758260539775958564099341129 Random prime: 678561933854231032073566346504160285991810520328758260539775958564099341417 Jump to find: 288
The jump value relates to the finding of the prime number from a random number start. In the example above, we increment by 288 to find the next prime number from our starting point. Generally, the smaller the prime number, the smaller the number of jumps will be. So, large numbers will often take much longer to generate, as there are likely to be more tests.