- \(a^{d} \equiv 1 \pmod{n}\)
- \(a^{2^r \cdot d} \equiv -1 \pmod n\)
and where \(r\) is a value between 0 and \(s-1\).
Miller-Rabin Test for Primes in PowerShell
[Primes Home][Home]
Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numbers used in RSA. Given an odd number (\(n\)), we will have an odd number of (\(n-1\)), of which we can calculate the power of 2 with a value of \(s\) so that \(n-1 = 2^s d\). For example, if \(n\) is 25, \((n-1)\) will be 24, and which is \(2 \times 2 \times 2 \times 3\) and which is \(2^3 \times 3\). We then select a random value of \(a\) and which is between 1 and \((n-1)\). We have a prime if:
and where \(r\) is a value between 0 and \(s-1\). |
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 }
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))) { "This is positive" 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 } function isItPrime($n, $k) { $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; } "== Prime Test Using Rabin Miller == " $is_prime = isItPrime 11 4 "11 is prime: "+$is_prime $is_prime = isItPrime 25 4 "25 is prime: "+$is_prime $is_prime = isItPrime 98 4 "98 is prime: "+$is_prime $is_prime = isItPrime 97 4 "97 is prime: "+$is_prime $is_prime = isItPrime 997 4 "997 is prime: "+$is_prime $prime = [BigInt]::Pow(2,255)-19 $is_prime = isItPrime $prime 4 "2^{255}-19 is prime: "+$is_prime try { if ($Args.Count -gt 0) { $prime=[BigInt]::Parse($Args[0]) } } catch { "Value needs to be an integer" } "`nNow trying input value:" $is_prime = isItPrime $prime 4 ""+$prime+" is prime: "+$is_prime
A sample run is
== Prime Test Using Rabin Miller == 11 is prime: True 25 is prime: False 98 is prime: False 97 is prime: True 997 is prime: True 2^{255}-19 is prime: True Now trying input value: 1234567891 is prime: True
and for a value with 230 digits:
== Prime Test Using Rabin Miller == 11 is prime: True 25 is prime: False 98 is prime: False 97 is prime: True 997 is prime: True 2^{255}-19 is prime: True Now trying input value: 56125680981752282333498088313568935051383833838594899821664631784577337171193624243181360054669678410455329112434552942717084003541384594864129940145043086760031292483340068923506115878221189886491132772739661669044958531131327771 is prime: True