2 // Mono.Math.Prime.Generator.SequentialSearchPrimeGeneratorBase.cs - Prime Generator
7 // Copyright (c) 2003 Ben Maurer. All rights reserved
8 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
10 // Permission is hereby granted, free of charge, to any person obtaining
11 // a copy of this software and associated documentation files (the
12 // "Software"), to deal in the Software without restriction, including
13 // without limitation the rights to use, copy, modify, merge, publish,
14 // distribute, sublicense, and/or sell copies of the Software, and to
15 // permit persons to whom the Software is furnished to do so, subject to
16 // the following conditions:
18 // The above copyright notice and this permission notice shall be
19 // included in all copies or substantial portions of the Software.
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
22 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
23 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
24 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
25 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
26 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
27 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
30 namespace Mono
.Math
.Prime
.Generator
{
37 class SequentialSearchPrimeGeneratorBase
: PrimeGeneratorBase
{
39 protected virtual BigInteger
GenerateSearchBase (int bits
, object context
)
41 BigInteger ret
= BigInteger
.GenerateRandom (bits
);
47 public override BigInteger
GenerateNewPrime (int bits
)
49 return GenerateNewPrime (bits
, null);
53 public virtual BigInteger
GenerateNewPrime (int bits
, object context
)
56 // STEP 1. Find a place to do a sequential search
58 BigInteger curVal
= GenerateSearchBase (bits
, context
);
60 const uint primeProd1
= 3u* 5u * 7u * 11u * 13u * 17u * 19u * 23u * 29u;
62 uint pMod1
= curVal
% primeProd1
;
64 int DivisionBound
= TrialDivisionBounds
;
65 uint[] SmallPrimes
= BigInteger
.smallPrimes
;
67 // STEP 2. Search for primes
72 // STEP 2.1 Sieve out numbers divisible by the first 9 primes
74 if (pMod1
% 3 == 0) goto biNotPrime
;
75 if (pMod1
% 5 == 0) goto biNotPrime
;
76 if (pMod1
% 7 == 0) goto biNotPrime
;
77 if (pMod1
% 11 == 0) goto biNotPrime
;
78 if (pMod1
% 13 == 0) goto biNotPrime
;
79 if (pMod1
% 17 == 0) goto biNotPrime
;
80 if (pMod1
% 19 == 0) goto biNotPrime
;
81 if (pMod1
% 23 == 0) goto biNotPrime
;
82 if (pMod1
% 29 == 0) goto biNotPrime
;
85 // STEP 2.2 Sieve out all numbers divisible by the primes <= DivisionBound
87 for (int p
= 10; p
< SmallPrimes
.Length
&& SmallPrimes
[p
] <= DivisionBound
; p
++) {
88 if (curVal
% SmallPrimes
[p
] == 0)
93 // STEP 2.3 Is the potential prime acceptable?
95 if (!IsPrimeAcceptable (curVal
, context
))
99 // STEP 2.4 Filter out all primes that pass this step with a primality test
101 if (PrimalityTest (curVal
, Confidence
))
109 if (pMod1
>= primeProd1
)
115 protected virtual bool IsPrimeAcceptable (BigInteger bi
, object context
)