Fixed BigInteger Primality<\/p>\n\n\n\n
using System;\nusing System.Numerics;\nusing System.Threading;\npublic class FixedIntXPrimality\n{\n private readonly FixedBigInteger _twoSixtyFourPlusIntMax = new FixedBigInteger(\"18446744073709551616\", 64);\n private readonly uint[] _w0 = {2};\n private readonly uint[] _w1 = {2, 3};\n private readonly uint[] _w10 = {2, 3, 5, 7, 11, 13, 17, 19, 23};\n private readonly uint[] _w11 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};\n private readonly uint[] _w12 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};\n private readonly uint[] _w2 = {31, 73};\n private readonly uint[] _w3 = {2, 3, 5};\n private readonly uint[] _w4 = {2, 3, 5, 7};\n private readonly uint[] _w5 = {2, 7, 61};\n private readonly uint[] _w6 = {2, 13, 23, 1662803};\n private readonly uint[] _w7 = {2, 3, 5, 7, 11};\n private readonly uint[] _w8 = {2, 3, 5, 7, 11, 13};\n private readonly uint[] _w9 = {2, 3, 5, 7, 11, 13, 17};\n private readonly int[] LowPrimes =\n {\n 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,\n 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,\n 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,\n 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677,\n 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881,\n 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997\n };\n private int _bitWidth;\n private FixedBigIntegerRandomNumberGenerator _rng;\n public int CandidateTried;\n public FixedIntXPrimality(int bitWidth)\n {\n _bitWidth = bitWidth;\n _rng = new FixedBigIntegerRandomNumberGenerator(_bitWidth);\n _rng.OddsOnly = true;\n _rng.Unsigned = true;\n }\n public void ResetBitWidth(int bitWidth)\n {\n _bitWidth = bitWidth;\n _rng = new FixedBigIntegerRandomNumberGenerator(_bitWidth);\n _rng.OddsOnly = true;\n _rng.Unsigned = true;\n }\n private bool TrialDivision(FixedBigInteger candidate)\n {\n for (var i = 0; i < LowPrimes.Length; i++)\n {\n var p = LowPrimes[i];\n if (i < p)\n {\n if (candidate % p != 0)\n continue;\n return false;\n }\n break;\n }\n return true;\n }\n private static bool PrimeCheckM10LD(FixedBigInteger n)\n {\n var d1 = (int) (n % 10);\n return d1 == 1 || d1 == 3 || d1 == 7 || d1 == 9;\n }\n private static bool PrimeCheckM6(FixedBigInteger n)\n {\n var d1 = (int) (n % 6);\n return d1 == 1 || d1 == 5;\n }\n public bool IsPrime(uint bi)\n {\n return IsPrime((FixedBigInteger) bi);\n }\n public bool IsPrime(int bi)\n {\n bi = Math.Abs(bi);\n return IsPrime((FixedBigInteger) bi);\n }\n public bool IsPrime(short bi)\n {\n bi = Math.Abs(bi);\n return IsPrime((FixedBigInteger) bi);\n }\n public bool IsPrime(ushort bi)\n {\n return IsPrime((FixedBigInteger) bi);\n }\n public bool IsPrime(byte bi)\n {\n return IsPrime((FixedBigInteger) bi);\n }\n public bool IsPrime(sbyte bi)\n {\n bi = Math.Abs(bi);\n return IsPrime((FixedBigInteger) bi);\n }\n private bool CheckLowPrimes(FixedBigInteger val)\n {\n foreach (var v in LowPrimes)\n if (val == v)\n return true;\n return false;\n }\n public bool IsPrime(FixedBigInteger candidate)\n {\n if (candidate == 1)\n return false;\n if (candidate == 2 || candidate == 3 || candidate == 5)\n return true;\n if (candidate <= 1000)\n return CheckLowPrimes(candidate);\n if (!PrimeCheckM10LD(candidate))\n return false;\n if (!PrimeCheckM6(candidate))\n return false;\n if (!TrialDivision(candidate))\n return false;\n if (candidate < 2047)\n {\n if (!MillerRabin(candidate, _w0))\n return false;\n }\n else if (candidate > 2047 && candidate <= 1373653)\n {\n if (!MillerRabin(candidate, _w1))\n return false;\n }\n else if (candidate > 1373653 && candidate <= 9080191)\n {\n if (!MillerRabin(candidate, _w2))\n return false;\n }\n else if (candidate > 9080191 && candidate <= 25326001)\n {\n if (!MillerRabin(candidate, _w3))\n return false;\n }\n else if (candidate > 25326001 && candidate <= 3215031751)\n {\n if (!MillerRabin(candidate, _w4))\n return false;\n }\n else if (candidate > 3215031751 && candidate <= 4759123141)\n {\n if (!MillerRabin(candidate, _w5))\n return false;\n }\n else if (candidate > 4759123141 && candidate <= 1122004669633)\n {\n if (!MillerRabin(candidate, _w6))\n return false;\n }\n else if (candidate > 1122004669633 && candidate <= 2152302898747)\n {\n if (!MillerRabin(candidate, _w7))\n return false;\n }\n else if (candidate > 2152302898747 && candidate <= 3474749660383)\n {\n if (!MillerRabin(candidate, _w8))\n return false;\n }\n else if (candidate > 3474749660383 && candidate <= 341550071728321)\n {\n if (!MillerRabin(candidate, _w9))\n return false;\n }\n else if (candidate > 341550071728321 && candidate <= 3825123056546413051)\n {\n if (!MillerRabin(candidate, _w10))\n return false;\n }\n else if (candidate > 3825123056546413051 && candidate < _twoSixtyFourPlusIntMax)\n {\n if (!MillerRabin(candidate, _w11))\n return false;\n }\n else if (candidate > _twoSixtyFourPlusIntMax)\n {\n if (!MillerRabin(candidate, _w12))\n return false;\n }\n return true;\n }\n private bool MillerRabin(FixedBigInteger candidate, uint[] w)\n {\n var s = 0;\n var d = candidate - FixedBigInteger.One;\n while ((d & 1) == 0)\n {\n d >>= 1;\n s++;\n }\n if (s == 0)\n return false;\n var nmo = candidate - FixedBigInteger.One;\n for (var i = 0; i < w.Length; ++i)\n {\n var x = BigInteger.ModPow(w[i], (BigInteger) d, (BigInteger) candidate);\n if (x == 1 || x == nmo)\n continue;\n for (var r = 1; r < s; ++r)\n {\n x = BigInteger.ModPow(x, 2, (BigInteger) candidate);\n if (x == 1)\n return false;\n if (x == nmo)\n break;\n }\n if (x == nmo)\n continue;\n return false;\n }\n return true;\n }\n public FixedBigInteger GetPrimeNumber(bool fixedWidth = false)\n {\n var bw = 0;\n if (!fixedWidth)\n {\n var MaxBytes = _bitWidth >> 3;\n var bwb = new byte[2];\n _rng.GetBytes(bwb);\n bw = bwb[0] % MaxBytes + 1;\n if (bw < 1)\n bw = 1;\n }\n else\n {\n bw = _bitWidth >> 3;\n }\n var buffer = new byte[bw];\n var n = new FixedBigInteger(0, 0);\n CandidateTried = 0;\n var btrd = new Thread(() =>\n {\n while (true)\n {\n CandidateTried++;\n _rng.GetBytes(buffer);\n n = new FixedBigInteger(buffer, _bitWidth) | 1;\n if (n == 1)\n continue;\n if (n > n.MaxValue)\n continue;\n if (IsPrime(n))\n break;\n }\n }) {Priority = ThreadPriority.Highest};\n btrd.Start();\n btrd.Join();\n return n;\n }\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"Fixed BigInteger Primality<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[2],"tags":[14,12,13],"_links":{"self":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/71"}],"collection":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/comments?post=71"}],"version-history":[{"count":1,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/71\/revisions"}],"predecessor-version":[{"id":72,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/posts\/71\/revisions\/72"}],"wp:attachment":[{"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/media?parent=71"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/categories?post=71"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaeljohnsteiner.com\/index.php\/wp-json\/wp\/v2\/tags?post=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}