Miller–Rabin primality test: Difference between revisions

Content added Content deleted
No edit summary
Line 1: Line 1:
{{task|Prime Numbers}}{{Wikipedia|Miller–Rabin primality test}}
{{task|Prime Numbers}}{{Wikipedia|Miller–Rabin primality test}}

The [[wp:Miller–Rabin primality test|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 [[wp:Michael O. Rabin|Michael O. Rabin]] to avoid the [[wp:generalized Riemann hypothesis|generalized Riemann hypothesis]], is a probabilistic algorithm.
The [[wp:Miller–Rabin primality test|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 [[wp:Michael O. Rabin|Michael O. Rabin]] to avoid the [[wp:generalized Riemann hypothesis|generalized Riemann hypothesis]], is a probabilistic algorithm.


The pseudocode, from [[wp:Miller-Rabin primality test#Algorithm_and_running_time|Wikipedia]] is:
The pseudocode, from [[wp:Miller-Rabin primality test#Algorithm_and_running_time|Wikipedia]] is:
Line 25: Line 28:
===ordinary integers===
===ordinary integers===


It's easy to get overflows doing exponential calculations. Therefore I implemented my own function for that.
It's easy to get overflows doing exponential calculations.
Therefore I implemented my own function for that.


For Number types >= 2**64 you may have to use an external library -- see below.
For Number types >= 2**64 you may have to use an external library -- see below.


First, a package Miller_Rabin is specified. The same package is used else elsewhere in Rosetta Code, such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]].
First, a package Miller_Rabin is specified.
The same package is used elsewhere in Rosetta Code,
such as for the [[Carmichael 3 strong pseudoprimes]] the [[Extensible prime generator]], and the [[Emirp primes]].


<lang Ada>generic
<lang Ada>generic
Line 224: Line 230:
end Miller_Rabin;</lang>
end Miller_Rabin;</lang>


{{out}}
Output:
<pre>Prime(4547337172376300111955330758342147474062293202868155909489)=TRUE
<pre>Prime(4547337172376300111955330758342147474062293202868155909489)=TRUE
Prime(4547337172376300111955330758342147474062293202868155909393)=FALSE</pre>
Prime(4547337172376300111955330758342147474062293202868155909393)=FALSE</pre>
Line 495: Line 501:
& out$!last
& out$!last
);</lang>
);</lang>
{{out}}
output:
<pre>937 941 947 953 967 971 977 983 991 997</pre>
<pre>937 941 947 953 967 971 977 983 991 997</pre>

=={{header|C}}==
=={{header|C}}==
{{libheader|GMP}}
{{libheader|GMP}}
Line 507: Line 514:
'''miller-rabin.c'''
'''miller-rabin.c'''
{{trans|Fortran}}
{{trans|Fortran}}
For <code>decompose</code> (and header <tt>primedecompose.h</tt>), see [[Prime decomposition#C|Prime decomposition]].
For <code>decompose</code> (and header <tt>primedecompose.h</tt>),
see [[Prime decomposition#C|Prime decomposition]].
<lang c>#include <stdbool.h>
<lang c>#include <stdbool.h>
#include <gmp.h>
#include <gmp.h>
Line 2,390: Line 2,398:
: with a K ≥ 3, rare as hen's teeth.
: with a K ≥ 3, rare as hen's teeth.


This would be in the same vein as: 3 is prime, 5 is prime, 7 is prime, all odd numbers are prime.
This would be in the same vein as:
3 is prime, 5 is prime, 7 is prime, all odd numbers are prime.
<lang rexx>/*REXX program puts the Miller-Rabin primality test through its paces.*/
<lang rexx>/*REXX program puts the Miller-Rabin primality test through its paces.*/
parse arg limit accur . /*get some optional arguments*/
parse arg limit accur . /*get some optional arguments*/
Line 2,453: Line 2,462:
end /*j*/ /*this comment not left blank. */
end /*j*/ /*this comment not left blank. */
return /*whew! All done with the primes*/</lang>
return /*whew! All done with the primes*/</lang>
'''output''' when using the input of: &nbsp; <tt> 10000 10 </tt>
{{out}} when using the input of: &nbsp; <tt> 10000 10 </tt>
<pre style="height:30ex">
<pre style="height:30ex">
There are 1229 primes ≤ 10000
There are 1229 primes ≤ 10000
Line 2,576: Line 2,585:


=={{header|Scala}}==
=={{header|Scala}}==
[[Category:Scala Implementations]]
{{libheader|Scala}}<lang scala>import scala.math.BigInt
{{libheader|Scala}}<lang scala>import scala.math.BigInt


Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"