2 // Mono.Math.Prime.PrimalityTests.cs - Test for primality
7 // Copyright (c) 2003 Ben Maurer. All rights reserved
11 // Permission is hereby granted, free of charge, to any person obtaining
12 // a copy of this software and associated documentation files (the
13 // "Software"), to deal in the Software without restriction, including
14 // without limitation the rights to use, copy, modify, merge, publish,
15 // distribute, sublicense, and/or sell copies of the Software, and to
16 // permit persons to whom the Software is furnished to do so, subject to
17 // the following conditions:
19 // The above copyright notice and this permission notice shall be
20 // included in all copies or substantial portions of the Software.
22 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
23 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
24 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
25 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
26 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
27 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
28 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 namespace Mono.Math.Prime {
40 delegate bool PrimalityTest (BigInteger bi, ConfidenceFactor confidence);
47 sealed class PrimalityTests {
49 private PrimalityTests ()
55 private static int GetSPPRounds (BigInteger bi, ConfidenceFactor confidence)
57 int bc = bi.BitCount();
61 // Data from HAC, 4.49
62 if (bc <= 100 ) Rounds = 27;
63 else if (bc <= 150 ) Rounds = 18;
64 else if (bc <= 200 ) Rounds = 15;
65 else if (bc <= 250 ) Rounds = 12;
66 else if (bc <= 300 ) Rounds = 9;
67 else if (bc <= 350 ) Rounds = 8;
68 else if (bc <= 400 ) Rounds = 7;
69 else if (bc <= 500 ) Rounds = 6;
70 else if (bc <= 600 ) Rounds = 5;
71 else if (bc <= 800 ) Rounds = 4;
72 else if (bc <= 1250) Rounds = 3;
76 case ConfidenceFactor.ExtraLow:
78 return Rounds != 0 ? Rounds : 1;
79 case ConfidenceFactor.Low:
81 return Rounds != 0 ? Rounds : 1;
82 case ConfidenceFactor.Medium:
84 case ConfidenceFactor.High:
86 case ConfidenceFactor.ExtraHigh:
88 case ConfidenceFactor.Provable:
89 throw new Exception ("The Rabin-Miller test can not be executed in a way such that its results are provable");
91 throw new ArgumentOutOfRangeException ("confidence");
95 public static bool Test (BigInteger n, ConfidenceFactor confidence)
97 // Rabin-Miller fails with smaller primes (at least with our BigInteger code)
98 if (n.BitCount () < 33)
99 return SmallPrimeSppTest (n, confidence);
101 return RabinMillerTest (n, confidence);
105 /// Probabilistic prime test based on Rabin-Miller's test
107 /// <param name="n" type="BigInteger.BigInteger">
109 /// The number to test.
112 /// <param name="confidence" type="int">
114 /// The number of chosen bases. The test has at least a
115 /// 1/4^confidence chance of falsely returning True.
120 /// True if "this" is a strong pseudoprime to randomly chosen bases.
123 /// False if "this" is definitely NOT prime.
126 public static bool RabinMillerTest (BigInteger n, ConfidenceFactor confidence)
128 int bits = n.BitCount ();
129 int t = GetSPPRounds (bits, confidence);
131 // n - 1 == 2^s * r, r is odd
132 BigInteger n_minus_1 = n - 1;
133 int s = n_minus_1.LowestSetBit ();
134 BigInteger r = n_minus_1 >> s;
136 BigInteger.ModulusRing mr = new BigInteger.ModulusRing (n);
138 // Applying optimization from HAC section 4.50 (base == 2)
139 // not a really random base but an interesting (and speedy) one
141 // FIXME - optimization disable for small primes due to bug #81857
142 if (n.BitCount () > 100)
145 // still here ? start at round 1 (round 0 was a == 2)
146 for (int round = 0; round < t; round++) {
148 if ((round > 0) || (y == null)) {
151 // check for 2 <= a <= n - 2
152 // ...but we already did a == 2 previously as an optimization
154 a = BigInteger.GenerateRandom (bits);
155 } while ((a <= 2) && (a >= n_minus_1));
163 for (int j = 0; ((j < s) && (y != n_minus_1)); j++) {
176 public static bool SmallPrimeSppTest (BigInteger bi, ConfidenceFactor confidence)
178 int Rounds = GetSPPRounds (bi, confidence);
180 // calculate values of s and t
181 BigInteger p_sub1 = bi - 1;
182 int s = p_sub1.LowestSetBit ();
184 BigInteger t = p_sub1 >> s;
187 BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi);
189 for (int round = 0; round < Rounds; round++) {
191 BigInteger b = mr.Pow (BigInteger.smallPrimes [round], t);
193 if (b == 1) continue; // a^t mod p = 1
196 for (int j = 0; j < s; j++) {
198 if (b == p_sub1) { // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
214 // TODO: Implement the Lucus test
215 // TODO: Implement other new primality tests
216 // TODO: Implement primality proving