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