mcs/class/corlib/Mono.Math.Prime.Generator/SequentialSearchPrimeGeneratorBase.cs

   1 //
   2 // Mono.Math.Prime.Generator.SequentialSearchPrimeGeneratorBase.cs - Prime Generator
   3 //
   4 // Authors:
   5 //      Ben Maurer
   6 //
   7 // Copyright (c) 2003 Ben Maurer. All rights reserved
   8 //
   9
  10 //
  11 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System;
  34 using Mono.Math.Prime;
  35
  36 namespace Mono.Math.Prime.Generator {
  37
  38 #if INSIDE_CORLIB
  39         internal
  40 #else
  41         public
  42 #endif
  43         class SequentialSearchPrimeGeneratorBase : PrimeGeneratorBase {
  44
  45                 protected virtual BigInteger GenerateSearchBase (int bits, object context)
  46                 {
  47                         BigInteger ret = BigInteger.GenerateRandom (bits);
  48                         ret.SetBit (0);
  49                         return ret;
  50                 }
  51
  52
  53                 public override BigInteger GenerateNewPrime (int bits)
  54                 {
  55                         return GenerateNewPrime (bits, null);
  56                 }
  57
  58
  59                 public virtual BigInteger GenerateNewPrime (int bits, object context)
  60                 {
  61                         //
  62                         // STEP 1. Find a place to do a sequential search
  63                         //
  64                         BigInteger curVal = GenerateSearchBase (bits, context);
  65
  66                         const uint primeProd1 = 3u* 5u * 7u * 11u * 13u * 17u * 19u * 23u * 29u;
  67
  68                         uint pMod1 = curVal % primeProd1;
  69
  70                         int DivisionBound = TrialDivisionBounds;
  71                         uint[] SmallPrimes = BigInteger.smallPrimes;
  72                         PrimalityTest PostTrialDivisionTest = this.PrimalityTest;
  73                         //
  74                         // STEP 2. Search for primes
  75                         //
  76                         while (true) {
  77
  78                                 //
  79                                 // STEP 2.1 Sieve out numbers divisible by the first 9 primes
  80                                 //
  81                                 if (pMod1 %  3 == 0) goto biNotPrime;
  82                                 if (pMod1 %  5 == 0) goto biNotPrime;
  83                                 if (pMod1 %  7 == 0) goto biNotPrime;
  84                                 if (pMod1 % 11 == 0) goto biNotPrime;
  85                                 if (pMod1 % 13 == 0) goto biNotPrime;
  86                                 if (pMod1 % 17 == 0) goto biNotPrime;
  87                                 if (pMod1 % 19 == 0) goto biNotPrime;
  88                                 if (pMod1 % 23 == 0) goto biNotPrime;
  89                                 if (pMod1 % 29 == 0) goto biNotPrime;
  90
  91                                 //
  92                                 // STEP 2.2 Sieve out all numbers divisible by the primes <= DivisionBound
  93                                 //
  94                                 for (int p = 10; p < SmallPrimes.Length && SmallPrimes [p] <= DivisionBound; p++) {
  95                                         if (curVal % SmallPrimes [p] == 0)
  96                                                 goto biNotPrime;
  97                                 }
  98
  99                                 //
 100                                 // STEP 2.3 Is the potential prime acceptable?
 101                                 //
 102                                 if (!IsPrimeAcceptable (curVal, context))
 103                                         goto biNotPrime;
 104
 105                                 //
 106                                 // STEP 2.4 Filter out all primes that pass this step with a primality test
 107                                 //
 108                                 if (PrimalityTest (curVal, Confidence))
 109                                         return curVal;
 110
 111                                 //
 112                                 // STEP 2.4
 113                                 //
 114                         biNotPrime:
 115                                 pMod1 += 2;
 116                                 if (pMod1 >= primeProd1)
 117                                         pMod1 -= primeProd1;
 118                                 curVal.Incr2 ();
 119                         }
 120                 }
 121
 122                 protected virtual bool IsPrimeAcceptable (BigInteger bi, object context)
 123                 {
 124                         return true;
 125                 }
 126         }
 127 }