RandomPrimeGenerator with Pre-Checks

RandomPrimeGenerator.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace RandomPrimes
{
    public class RandomPrimeGenerator
    {
        public RandomPrimeGenerator(int seed)
        {
            this.Twister = new MersenneTwister(unchecked((uint)seed));
        }

        MersenneTwister Twister { get; set; }
        
        public ulong Next(ulong minimum, ulong maximum)
        {
            ulong initialRandom = this.GenerateRandomULong(minimum, maximum);
            bool searchDirection = (initialRandom & 1) == 1; //Falls die Zufallszahl keine Primzahl ist, wird mit dem letzten Bit die Suchrichtung festgelegt

            //So lange in der festgelegten Richtung suchen, bis eine Primzahl gefunden wurde (das letzte Bit der ursprünglichen Zufallszahl wird gesetzt, damit nur ungerade Zahlen getestet werden)
            ulong candidate;
            for (candidate = initialRandom | 1; !this.CheckPrimeDeterministicMillerRabin(candidate); candidate = searchDirection ? candidate + 2 : candidate - 2)
            {
                if (candidate < minimum)
                {
                    candidate = maximum | 1;
                }
                if (candidate > maximum)
                {
                    candidate = minimum | 1;
                }
            }

            return candidate;
        }

        public ulong NextPrimeFactorPreCheck(ulong minimum, ulong maximum, int preCheckMax)
        {
            ulong initialRandom = this.GenerateRandomULong(minimum, maximum);
            bool searchDirection = (initialRandom & 1) == 1; //Falls die Zufallszahl keine Primzahl ist, wird mit dem letzten Bit die Suchrichtung festgelegt

            //So lange in der festgelegten Richtung suchen, bis eine Primzahl gefunden wurde (das letzte Bit der ursprünglichen Zufallszahl wird gesetzt, damit nur ungerade Zahlen getestet werden)
            ulong candidate;
            for (candidate = initialRandom | 1; !this.CheckPrimePrimeFactorPrecheck(candidate, preCheckMax); candidate = searchDirection ? candidate + 2 : candidate - 2)
            {
                if (candidate < minimum)
                {
                    candidate = maximum | 1;
                }
                if (candidate > maximum)
                {
                    candidate = minimum | 1;
                }
            }

            return candidate;
        }

        public ulong NextIncrementalFermatPreCheck(ulong minimum, ulong maximum, int preCheckRounds)
        {
            ulong initialRandom = this.GenerateRandomULong(minimum, maximum);
            bool searchDirection = (initialRandom & 1) == 1; //Falls die Zufallszahl keine Primzahl ist, wird mit dem letzten Bit die Suchrichtung festgelegt

            //So lange in der festgelegten Richtung suchen, bis eine Primzahl gefunden wurde (das letzte Bit der ursprünglichen Zufallszahl wird gesetzt, damit nur ungerade Zahlen getestet werden)
            ulong candidate;
            for (candidate = initialRandom | 1; !this.CheckPrimeIncrementalFermatPrecheck(candidate, preCheckRounds); candidate = searchDirection ? candidate + 2 : candidate - 2)
            {
                if (candidate < minimum)
                {
                    candidate = maximum | 1;
                }
                if (candidate > maximum)
                {
                    candidate = minimum | 1;
                }
            }

            return candidate;
        }

        public ulong NextRandomFermatPreCheck(ulong minimum, ulong maximum, int preCheckRounds)
        {
            ulong initialRandom = this.GenerateRandomULong(minimum, maximum);
            bool searchDirection = (initialRandom & 1) == 1; //Falls die Zufallszahl keine Primzahl ist, wird mit dem letzten Bit die Suchrichtung festgelegt

            //So lange in der festgelegten Richtung suchen, bis eine Primzahl gefunden wurde (das letzte Bit der ursprünglichen Zufallszahl wird gesetzt, damit nur ungerade Zahlen getestet werden)
            ulong candidate;
            for (candidate = initialRandom | 1; !this.CheckPrimeRandomFermatPrecheck(candidate, preCheckRounds); candidate = searchDirection ? candidate + 2 : candidate - 2)
            {
                if (candidate < minimum)
                {
                    candidate = maximum | 1;
                }
                if (candidate > maximum)
                {
                    candidate = minimum | 1;
                }
            }

            return candidate;
        }
        

        
        private uint[] primes = new uint[] { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 }; //Nur 12 Primzahlen, da für die Tests nicht mehr notwendig sind.
        protected bool CheckPrimePrimeFactorPrecheck(ulong candidate, int preCheckMax)
        {
            //Simpler Pre-Check mit der naiven Primzahl-Prüf-Methode
            for (uint i = 0; i < preCheckMax; i++)
            {
                if (candidate % primes[i] == 0)
                {
                    return false;
                }
            }

            //Fallback zur deterministischen Version vom Miller-Rabin-Primzahltest
            return this.CheckPrimeDeterministicMillerRabin(candidate);
        }

        protected bool CheckPrimeIncrementalFermatPrecheck(ulong candidate, int preCheckRounds)
        {
            //Pre-Check mit dem probabilistischen Fermatschen Primzahltest
            for (int i = 0; i < preCheckRounds; i++)
            {
                int a = i + 2;
                ulong x = (ulong)BigInteger.ModPow(a, candidate - 1, candidate);
                if (x != 1)
                {
                    return false;
                }
            }

            //Fallback zur deterministischen Version vom Miller-Rabin-Primzahltest
            return this.CheckPrimeDeterministicMillerRabin(candidate);
        }

        protected bool CheckPrimeRandomFermatPrecheck(ulong candidate, int preCheckRounds)
        {
            //Pre-Check mit dem probabilistischen Fermatschen Primzahltest
            for (int i = 0; i < preCheckRounds; i++)
            {
                ulong a = this.GenerateRandomULong(2, candidate - 2);
                ulong x = (ulong)BigInteger.ModPow(a, candidate - 1, candidate);
                if (x != 1)
                {
                    return false;
                }
            }

            //Fallback zur deterministischen Version vom Miller-Rabin-Primzahltest
            return this.CheckPrimeDeterministicMillerRabin(candidate);
        }



        protected ulong GenerateRandomULong(ulong minimum, ulong maximum)
        {
            uint first = unchecked((uint)this.Twister.NextInRange(unchecked((int)(minimum >> 32)), unchecked((int)(maximum >> 32))));
            uint second = unchecked((uint)this.Twister.NextInRange(unchecked((int)(minimum & int.MaxValue)), unchecked((int)(maximum & int.MaxValue))));
            return ((ulong)first << 32) | second;
        }

        protected bool CheckPrimeDeterministicMillerRabin(ulong candidate)
        {
            checked
            {
                ulong n1 = candidate - 1;
                ulong d = n1 >> 1;
                int j = 1;
                for (; (d & 1) == 0; d >>= 1, j++) ;
                foreach (uint a in new[] { 2, 3, 5, 7, 11, 13, 17, 19, 23 }) //Die Werte für a habe ich für Testzwecke mal hardgecoded
                {
                    ulong t = (ulong)BigInteger.ModPow(a, d, candidate);

                    if ((t == 1) || (t == n1))
                    {
                        continue;
                    }

                    for (int k = 1; k < j; k++)
                    {
                        t = (ulong)BigInteger.ModPow(t, 2, candidate);

                        if (t == 1)
                        {
                            return false;
                        }
                        if (t == n1)
                        {
                            break;
                        }
                    }

                    if (t != n1)
                    {
                        return false;
                    }
                }

                return true;
            }
        }
    }
}