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