How to resolve the algorithm Miller–Rabin primality test step by step in the Mathematica/Wolfram Language programming language
Published on 22 June 2024 08:30 PM
How to resolve the algorithm Miller–Rabin primality test step by step in the Mathematica/Wolfram Language programming language
Table of Contents
Problem Statement
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime or not. The algorithm, as modified by Michael O. Rabin to avoid the generalized Riemann hypothesis, is a probabilistic algorithm. The pseudocode, from Wikipedia is:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Miller–Rabin primality test step by step in the Mathematica/Wolfram Language programming language
This Wolfram code implements the Miller-Rabin primality test, which is a probabilistic test for determining whether a given number is prime. Here's a step-by-step explanation of the code:
Initialization:
MillerRabin[n_,k_]:=Module[{d=n-1,s=0,test=True},
- The MillerRabin function takes two parameters: n (the number to be tested) and k (the number of iterations for the test).
- It initializes d to n-1, s to 0, and test to True. Here d will store the odd part of n-1(i.e. n-1 = (2^s) * d).
Find d and s:
While[Mod[d,2]==0 ,d/=2 ;s++]
- This while loop finds s and d. d becomes the odd part of n-1 and s stores the number of 2's in the prime factorization of n-1.
Iteration for k times:
Do[
- The Do loop runs for k iterations.
Choose a random integer a in the range [2, n-1]
a=RandomInteger[{2,n-1}];
Calculate x = a^d mod n:
x=PowerMod[a,d,n];
Check if x is 1 or n-1:
If[x!=1,
- If x is not equal to 1, proceed to the next step.
Perform s-1 squarings of x:
For[ r = 0, r < s, r++, If[x==n-1, Continue[]]; x = Mod[x*x, n]; ];
- This loop squares x s-1 times, using the Mod function to ensure the result is always less than n.
- If at any point x becomes equal to n-1, the loop is exited using Continue[].
Check if x is n-1:
If[ x != n-1, test=False ];
- If x is not equal to n-1 after the loop, set test to False.
Output:
Print[test] ]
- After all k iterations are complete, the value of test is printed. If test is True, the number n is considered probably prime; otherwise, it is considered composite.
Example:
MillerRabin[17388,10]
->False
- In this example, the number 17388 is tested with k = 10 iterations. The result is False, indicating that 17388 is not a prime number.
Source code in the wolfram programming language
MillerRabin[n_,k_]:=Module[{d=n-1,s=0,test=True},While[Mod[d,2]==0 ,d/=2 ;s++]
Do[
a=RandomInteger[{2,n-1}]; x=PowerMod[a,d,n];
If[x!=1,
For[ r = 0, r < s, r++, If[x==n-1, Continue[]]; x = Mod[x*x, n]; ];
If[ x != n-1, test=False ];
];
,{k}];
Print[test] ]
MillerRabin[17388,10]
->False
You may also check:How to resolve the algorithm Averages/Root mean square step by step in the min programming language
You may also check:How to resolve the algorithm Concurrent computing step by step in the Ol programming language
You may also check:How to resolve the algorithm Queue/Definition step by step in the V programming language
You may also check:How to resolve the algorithm Sierpinski triangle/Graphical step by step in the Julia programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the M2000 Interpreter programming language