Question

write a program to illustrate the Miller-Rabin compositeness test, assuming the Extended Riemann Hypothesis. More precisely, given an integer N, your program should run through a values and apply the Miller-Rabin test to check if N is composite or likely prime. The pseudocode or code should be provided for this purpose. You can proceed to write the pseudocode or code for the Miller-Rabin compositeness test to illustrate how it works for a given integer N.

Answer 1

The Miller-Rabin compositeness test is a probabilistic algorithm that checks if an integer N is a likely prime or composite by performing k trials with random values a within [2, N-2]. Expressing N-1 as 2^s*d, where d is odd, it uses modular exponentiation and squaring to test compositeness. The test provides a 'likely prime' or 'composite' result after iterating through k trials.

Step-by-step explanation:

The Miller-Rabin compositeness test is a probabilistic algorithm used to determine whether a given integer N is likely prime or composite. It is based on the principle that, for a prime number N, certain equalities hold for N-1 when expressed in the form of 2sd, where d is odd and s is a non-negative integer.

Here is the pseudocode for the Miller-Rabin compositeness test:

1. 
   
3. Input: An odd integer N>2, number of trials k.
4. 
   
6. Write N-1 as 2sd with d odd.
7. 
   
9. For i=1 to k:
10. 
    
12. Pick a random integer a in the range [2, N-2].
13. 
    
15. Compute x = ad mod N.
16. 
    
18. If x = 1 or x = N-1, continue to next iteration of the loop.
19. 
    
21. For r = 0 to s-1:
22. 
    
24. Compute x = x2 mod N.
25. 
    
27. If x = 1, return 'composite'.
28. 
    
30. If x = N-1, continue to the next iteration of the outer loop.
31. 
    
33. Return 'composite'.
34. 
    
36. End of outer loop: return 'likely prime'.

The test is repeated k times to reduce the probability of a false positive, that is, identifying a composite number as 'likely prime'. The Extended Riemann Hypothesis suggests a bound on k for a certain level of confidence in the result. However, for practical purposes, certain fixed values of a are often used to simplify the test.