blob: 8ba87836ba3154c6f648f8df9fe709da40c624df (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
//
// Mono.Math.Prime.Generator.SequentialSearchPrimeGeneratorBase.cs - Prime Generator
//
// Authors:
// Ben Maurer
//
// Copyright (c) 2003 Ben Maurer. All rights reserved
//
using System;
using Mono.Math.Prime;
namespace Mono.Math.Prime.Generator {
#if INSIDE_CORLIB
internal
#else
public
#endif
class SequentialSearchPrimeGeneratorBase : PrimeGeneratorBase {
protected virtual BigInteger GenerateSearchBase (int bits, object context)
{
BigInteger ret = BigInteger.GenerateRandom (bits);
ret.SetBit (0);
return ret;
}
public override BigInteger GenerateNewPrime (int bits)
{
return GenerateNewPrime (bits, null);
}
public virtual BigInteger GenerateNewPrime (int bits, object context)
{
//
// STEP 1. Find a place to do a sequential search
//
BigInteger curVal = GenerateSearchBase (bits, context);
const uint primeProd1 = 3u* 5u * 7u * 11u * 13u * 17u * 19u * 23u * 29u;
uint pMod1 = curVal % primeProd1;
int DivisionBound = TrialDivisionBounds;
uint[] SmallPrimes = BigInteger.smallPrimes;
PrimalityTest PostTrialDivisionTest = this.PrimalityTest;
//
// STEP 2. Search for primes
//
while (true) {
//
// STEP 2.1 Sieve out numbers divisible by the first 9 primes
//
if (pMod1 % 3 == 0) goto biNotPrime;
if (pMod1 % 5 == 0) goto biNotPrime;
if (pMod1 % 7 == 0) goto biNotPrime;
if (pMod1 % 11 == 0) goto biNotPrime;
if (pMod1 % 13 == 0) goto biNotPrime;
if (pMod1 % 17 == 0) goto biNotPrime;
if (pMod1 % 19 == 0) goto biNotPrime;
if (pMod1 % 23 == 0) goto biNotPrime;
if (pMod1 % 29 == 0) goto biNotPrime;
//
// STEP 2.2 Sieve out all numbers divisible by the primes <= DivisionBound
//
for (int p = 10; p < SmallPrimes.Length && SmallPrimes [p] <= DivisionBound; p++) {
if (curVal % SmallPrimes [p] == 0)
goto biNotPrime;
}
//
// STEP 2.3 Is the potential prime acceptable?
//
if (!IsPrimeAcceptable (curVal, context))
goto biNotPrime;
//
// STEP 2.4 Filter out all primes that pass this step with a primality test
//
if (PrimalityTest (curVal, Confidence))
return curVal;
//
// STEP 2.4
//
biNotPrime:
pMod1 += 2;
if (pMod1 >= primeProd1)
pMod1 -= primeProd1;
curVal.Incr2 ();
}
}
protected virtual bool IsPrimeAcceptable (BigInteger bi, object context)
{
return true;
}
}
}
|
