Generating Prime NumbersMany public key algorithms depend on prime number, which are difficult to factorize when multiplied together. This program creates the ones from: The results are then:
Code usedstring primeList = ""; static ulong RecursiveModulo(ulong uBase, ulong uPower, ulong uDivisor) { ulong uAux; if (uPower == 0) return 1; //a^2c mod n = (ac mod n)2 mod n else if (uPower % 2 == 0) { uAux = RecursiveModulo(uBase, uPower / 2, uDivisor); return (uAux * uAux) % uDivisor; } //ac+1 mod n = (ac mod n) ยท a mod n else return (RecursiveModulo(uBase, uPower - 1, uDivisor) * uBase) % uDivisor; } public static bool TestPrime(ulong uNumber, uint uIterations) { Random Rnd = new Random(); ulong uAux; for (ulong i = 0; i < uIterations; ++i) { uAux = (ulong)(Rnd.Next()) % uNumber; if (uAux == 0) uAux = uNumber - 1; if (RecursiveModulo(uAux, uNumber - 1, uNumber) != 1) { return false; } } return true; } bool findprimes = true; public void goPrimes(int val) { int j = -1; DateTime startTime = DateTime.Now; // for (uint i = 2; i < Math.Pow(2, 32); i++) for (uint i = 2; i < val; i++) { if (i == 2) primes = String.Format("\r\nPrime numbers 1 to {0}:\r\n", val); if (findprimes == false) { return; } if (TestPrime(i, 2) == true && findprimes == true) { j++; if (j % 6 == 0) primes += "\r\n"; primes += Convert.ToString(i) + "\t"; } } TimeSpan elapsed = DateTime.Now - startTime; string nicePrettyString = elapsed.ToString(); primes += String.Format("\r\n\r\nTime taken is {0}\r\n", nicePrettyString); } |