给定一个数字n，检查它是否为素数。我们已经介绍并讨论了用于素性测试的School和Fermat方法。 素性测试|第1组（介绍和学校方法） 素性检验|集2（费马法） 本文讨论了米勒-拉宾方法。这种方法是一种概率方法（如费马法），但通常优于费马法。
null
算法：
// It returns false if n is composite and returns true if n// is probably prime. k is an input parameter that determines// accuracy level. Higher value of k indicates more accuracy.bool isPrime(int n, int k)1) Handle base cases for n < 32) If n is even, return false.3) Find an odd number d such that n-1 can be written as d*2r. Note that since n is odd, (n-1) must be even and r must be greater than 0.4) Do following k times if (millerTest(n, d) == false) return false5) Return true.// This function is called for all k trials. It returns // false if n is composite and returns true if n is probably// prime. // d is an odd number such that d*2r = n-1 for some r>=1bool millerTest(int n, int d)1) Pick a random number 'a' in range [2, n-2]2) Compute: x = pow(a, d) % n3) If x == 1 or x == n-1, return true.// Below loop mainly runs 'r-1' times.4) Do following while d doesn't become n-1. a) x = (x*x) % n. b) If (x == 1) return false. c) If (x == n-1) return true.
例子：
Input: n = 13, k = 2.1) Compute d and r such that d*2r = n-1, d = 3, r = 2. 2) Call millerTest k times.1st Iteration:1) Pick a random number 'a' in range [2, n-2] Suppose a = 42) Compute: x = pow(a, d) % n x = 43 % 13 = 123) Since x = (n-1), return true.IInd Iteration:1) Pick a random number 'a' in range [2, n-2] Suppose a = 52) Compute: x = pow(a, d) % n x = 53 % 13 = 83) x neither 1 nor 12.4) Do following (r-1) = 1 times a) x = (x * x) % 13 = (8 * 8) % 13 = 12 b) Since x = (n-1), return true.Since both iterations return true, we return true.
实施： 下面是上述算法的实现。
C++
// C++ program Miller-Rabin primality test #include <bits/stdc++.h> using namespace std; // Utility function to do modular exponentiation. // It returns (x^y) % p int power( int x, unsigned int y, int p) { int res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } // This function is called for all k trials. It returns // false if n is composite and returns true if n is // probably prime. // d is an odd number such that d*2<sup>r</sup> = n-1 // for some r >= 1 bool miillerTest( int d, int n) { // Pick a random number in [2..n-2] // Corner cases make sure that n > 4 int a = 2 + rand () % (n - 4); // Compute a^d % n int x = power(a, d, n); if (x == 1 || x == n-1) return true ; // Keep squaring x while one of the following doesn't // happen // (i) d does not reach n-1 // (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while (d != n-1) { x = (x * x) % n; d *= 2; if (x == 1) return false ; if (x == n-1) return true ; } // Return composite return false ; } // It returns false if n is composite and returns true if n // is probably prime. k is an input parameter that determines // accuracy level. Higher value of k indicates more accuracy. bool isPrime( int n, int k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Find r such that n = 2^d * r + 1 for some r >= 1 int d = n - 1; while (d % 2 == 0) d /= 2; // Iterate given nber of 'k' times for ( int i = 0; i < k; i++) if (!miillerTest(d, n)) return false ; return true ; } // Driver program int main() { int k = 4; // Number of iterations cout << "All primes smaller than 100: " ; for ( int n = 1; n < 100; n++) if (isPrime(n, k)) cout << n << " " ; return 0; } |
JAVA
// Java program Miller-Rabin primality test import java.io.*; import java.math.*; class GFG { // Utility function to do modular // exponentiation. It returns (x^y) % p static int power( int x, int y, int p) { int res = 1 ; // Initialize result //Update x if it is more than or // equal to p x = x % p; while (y > 0 ) { // If y is odd, multiply x with result if ((y & 1 ) == 1 ) res = (res * x) % p; // y must be even now y = y >> 1 ; // y = y/2 x = (x * x) % p; } return res; } // This function is called for all k trials. // It returns false if n is composite and // returns false if n is probably prime. // d is an odd number such that d*2<sup>r</sup> // = n-1 for some r >= 1 static boolean miillerTest( int d, int n) { // Pick a random number in [2..n-2] // Corner cases make sure that n > 4 int a = 2 + ( int )(Math.random() % (n - 4 )); // Compute a^d % n int x = power(a, d, n); if (x == 1 || x == n - 1 ) return true ; // Keep squaring x while one of the // following doesn't happen // (i) d does not reach n-1 // (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while (d != n - 1 ) { x = (x * x) % n; d *= 2 ; if (x == 1 ) return false ; if (x == n - 1 ) return true ; } // Return composite return false ; } // It returns false if n is composite // and returns true if n is probably // prime. k is an input parameter that // determines accuracy level. Higher // value of k indicates more accuracy. static boolean isPrime( int n, int k) { // Corner cases if (n <= 1 || n == 4 ) return false ; if (n <= 3 ) return true ; // Find r such that n = 2^d * r + 1 // for some r >= 1 int d = n - 1 ; while (d % 2 == 0 ) d /= 2 ; // Iterate given nber of 'k' times for ( int i = 0 ; i < k; i++) if (!miillerTest(d, n)) return false ; return true ; } // Driver program public static void main(String args[]) { int k = 4 ; // Number of iterations System.out.println( "All primes smaller " + "than 100: " ); for ( int n = 1 ; n < 100 ; n++) if (isPrime(n, k)) System.out.print(n + " " ); } } /* This code is contributed by Nikita Tiwari.*/ |
Python3
# Python3 program Miller-Rabin primality test import random # Utility function to do # modular exponentiation. # It returns (x^y) % p def power(x, y, p): # Initialize result res = 1 ; # Update x if it is more than or # equal to p x = x % p; while (y > 0 ): # If y is odd, multiply # x with result if (y & 1 ): res = (res * x) % p; # y must be even now y = y>> 1 ; # y = y/2 x = (x * x) % p; return res; # This function is called # for all k trials. It returns # false if n is composite and # returns false if n is # probably prime. d is an odd # number such that d*2<sup>r</sup> = n-1 # for some r >= 1 def miillerTest(d, n): # Pick a random number in [2..n-2] # Corner cases make sure that n > 4 a = 2 + random.randint( 1 , n - 4 ); # Compute a^d % n x = power(a, d, n); if (x = = 1 or x = = n - 1 ): return True ; # Keep squaring x while one # of the following doesn't # happen # (i) d does not reach n-1 # (ii) (x^2) % n is not 1 # (iii) (x^2) % n is not n-1 while (d ! = n - 1 ): x = (x * x) % n; d * = 2 ; if (x = = 1 ): return False ; if (x = = n - 1 ): return True ; # Return composite return False ; # It returns false if n is # composite and returns true if n # is probably prime. k is an # input parameter that determines # accuracy level. Higher value of # k indicates more accuracy. def isPrime( n, k): # Corner cases if (n < = 1 or n = = 4 ): return False ; if (n < = 3 ): return True ; # Find r such that n = # 2^d * r + 1 for some r >= 1 d = n - 1 ; while (d % 2 = = 0 ): d / / = 2 ; # Iterate given nber of 'k' times for i in range (k): if (miillerTest(d, n) = = False ): return False ; return True ; # Driver Code # Number of iterations k = 4 ; print ( "All primes smaller than 100: " ); for n in range ( 1 , 100 ): if (isPrime(n, k)): print (n , end = " " ); # This code is contributed by mits |
C#
// C# program Miller-Rabin primality test using System; class GFG { // Utility function to do modular // exponentiation. It returns (x^y) % p static int power( int x, int y, int p) { int res = 1; // Initialize result // Update x if it is more than // or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if ((y & 1) == 1) res = (res * x) % p; // y must be even now y = y >> 1; // y = y/2 x = (x * x) % p; } return res; } // This function is called for all k trials. // It returns false if n is composite and // returns false if n is probably prime. // d is an odd number such that d*2<sup>r</sup> // = n-1 for some r >= 1 static bool miillerTest( int d, int n) { // Pick a random number in [2..n-2] // Corner cases make sure that n > 4 Random r = new Random(); int a = 2 + ( int )(r.Next() % (n - 4)); // Compute a^d % n int x = power(a, d, n); if (x == 1 || x == n - 1) return true ; // Keep squaring x while one of the // following doesn't happen // (i) d does not reach n-1 // (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while (d != n - 1) { x = (x * x) % n; d *= 2; if (x == 1) return false ; if (x == n - 1) return true ; } // Return composite return false ; } // It returns false if n is composite // and returns true if n is probably // prime. k is an input parameter that // determines accuracy level. Higher // value of k indicates more accuracy. static bool isPrime( int n, int k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Find r such that n = 2^d * r + 1 // for some r >= 1 int d = n - 1; while (d % 2 == 0) d /= 2; // Iterate given nber of 'k' times for ( int i = 0; i < k; i++) if (miillerTest(d, n) == false ) return false ; return true ; } // Driver Code static void Main() { int k = 4; // Number of iterations Console.WriteLine( "All primes smaller " + "than 100: " ); for ( int n = 1; n < 100; n++) if (isPrime(n, k)) Console.Write(n + " " ); } } // This code is contributed by mits |
PHP
<?php // PHP program Miller-Rabin primality test // Utility function to do // modular exponentiation. // It returns (x^y) % p function power( $x , $y , $p ) { // Initialize result $res = 1; // Update x if it is more than or // equal to p $x = $x % $p ; while ( $y > 0) { // If y is odd, multiply // x with result if ( $y & 1) $res = ( $res * $x ) % $p ; // y must be even now $y = $y >>1; // $y = $y/2 $x = ( $x * $x ) % $p ; } return $res ; } // This function is called // for all k trials. It returns // false if n is composite and // returns false if n is // probably prime. d is an odd // number such that d*2<sup>r</sup> = n-1 // for some r >= 1 function miillerTest( $d , $n ) { // Pick a random number in [2..n-2] // Corner cases make sure that n > 4 $a = 2 + rand() % ( $n - 4); // Compute a^d % n $x = power( $a , $d , $n ); if ( $x == 1 || $x == $n -1) return true; // Keep squaring x while one // of the following doesn't // happen // (i) d does not reach n-1 // (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while ( $d != $n -1) { $x = ( $x * $x ) % $n ; $d *= 2; if ( $x == 1) return false; if ( $x == $n -1) return true; } // Return composite return false; } // It returns false if n is // composite and returns true if n // is probably prime. k is an // input parameter that determines // accuracy level. Higher value of // k indicates more accuracy. function isPrime( $n , $k ) { // Corner cases if ( $n <= 1 || $n == 4) return false; if ( $n <= 3) return true; // Find r such that n = // 2^d * r + 1 for some r >= 1 $d = $n - 1; while ( $d % 2 == 0) $d /= 2; // Iterate given nber of 'k' times for ( $i = 0; $i < $k ; $i ++) if (!miillerTest( $d , $n )) return false; return true; } // Driver Code // Number of iterations $k = 4; echo "All primes smaller than 100: " ; for ( $n = 1; $n < 100; $n ++) if (isPrime( $n , $k )) echo $n , " " ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript program Miller-Rabin primality test // Utility function to do // modular exponentiation. // It returns (x^y) % p function power(x, y, p) { // Initialize result let res = 1; // Update x if it is more than or // equal to p x = x % p; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } // This function is called // for all k trials. It returns // false if n is composite and // returns false if n is // probably prime. d is an odd // number such that d*2<sup>r</sup> = n-1 // for some r >= 1 function miillerTest(d, n) { // Pick a random number in [2..n-2] // Corner cases make sure that n > 4 let a = 2 + Math.floor(Math.random() * (n-2)) % (n - 4); // Compute a^d % n let x = power(a, d, n); if (x == 1 || x == n-1) return true ; // Keep squaring x while one // of the following doesn't // happen // (i) d does not reach n-1 // (ii) (x^2) % n is not 1 // (iii) (x^2) % n is not n-1 while (d != n-1) { x = (x * x) % n; d *= 2; if (x == 1) return false ; if (x == n-1) return true ; } // Return composite return false ; } // It returns false if n is // composite and returns true if n // is probably prime. k is an // input parameter that determines // accuracy level. Higher value of // k indicates more accuracy. function isPrime( n, k) { // Corner cases if (n <= 1 || n == 4) return false ; if (n <= 3) return true ; // Find r such that n = // 2^d * r + 1 for some r >= 1 let d = n - 1; while (d % 2 == 0) d /= 2; // Iterate given nber of 'k' times for (let i = 0; i < k; i++) if (!miillerTest(d, n)) return false ; return true ; } // Driver Code // Number of iterations let k = 4; document.write( "All primes smaller than 100: <br>" ); for (let n = 1; n < 100; n++) if (isPrime(n, k)) document.write(n , " " ); // This code is contributed by gfgking </script> |
输出：
All primes smaller than 100: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
这是怎么回事？ 以下是算法背后的一些重要事实：
- 费马定理 表示，如果n是素数，那么对于每个a，1<=a
n-1 %n=1 - 基本情况确保n必须是奇数。因为n是奇数，所以n-1必须是偶数。偶数可以写成d*2 s 其中d为奇数，s>0。
- 根据以上两点，对于[2，n-2]范围内的每一个随机选取的数字 d*2r %n必须是1。
- 根据 欧几里得引理 ，如果x 2. %n=1或（x） 2. –1）%n=0或（x-1）（x+1）%n=0。然后，如果n是素数，则n除（x-1）或n除（x+1）。这意味着x%n=1或x%n=-1。
- 从第2点和第3点，我们可以得出结论
For n to be prime, either ad % n = 1 OR ad*2i % n = -1 for some i, where 0 <= i <= r-1.
下一篇文章： 素性测试|集4（索洛维·斯特拉森）
这篇文章是有贡献的 鲁希尔·加格 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
