Тест на примитивность MillerRabin в C#
Добро пожаловать. Я пытаюсь реализовать тест MillerRabin для проверки, является ли большое заданное число простым числом. Вот мой код:
public static bool MillerRabinTest(BigInteger number)
{
BigInteger d;
var n = number - 1;
var s = FindK(n, out d);
BigInteger a = 2;
BigInteger y = Calc(a, d, number); //a^d mod number
if (y != BigInteger.One && y != n)
{
for (var r = 1; r <= s - 1; r++)
{
y = Calc(y, 2, number);
if (y == 1)
return false;
}
if (y != n)
return false;
}
return true; //it is probably prime
}
Это хорошо работает для маленьких Bigintegers. Но если мои программы должны вычислять числа, содержащие более 16 бит, программа зависает. Например, после успешной проверки, является ли число простым, программа внезапно перестает отвечать на запросы. Я не понимаю, как это возможно. Если он проверил одно большое число, у него не должно возникнуть проблем с проверкой другого. Даже отладчик не помогает, потому что step options исчезают. Я могу поделиться больше кода функций, если это необходимо. Выше функция работает правильно для небольших чисел.
РЕДАКТИРОВАТЬ. Помогло изменение моей функции по модулю для BigInteger.ModPow. К сожалению, теперь для больших чисел, более 3000 бит, никогда не возвращается простое число, что довольно невозможно. Или действительно цифры трудно найти?
2 ответа
Что ж, на моей рабочей станции (Core i5 3,2 ГГц, IA64 .Net 4.5) требуется около 5 секунд, чтобы проверить, является ли простое число числами, равными 2**3000:
public static class PrimeExtensions {
// Random generator (thread safe)
private static ThreadLocal<Random> s_Gen = new ThreadLocal<Random>(
() => {
return new Random();
}
);
// Random generator (thread safe)
private static Random Gen {
get {
return s_Gen.Value;
}
}
public static Boolean IsProbablyPrime(this BigInteger value, int witnesses = 10) {
if (value <= 1)
return false;
if (witnesses <= 0)
witnesses = 10;
BigInteger d = value - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s += 1;
}
Byte[] bytes = new Byte[value.ToByteArray().LongLength];
BigInteger a;
for (int i = 0; i < witnesses; i++) {
do {
Gen.NextBytes(bytes);
a = new BigInteger(bytes);
}
while (a < 2 || a >= value - 2);
BigInteger x = BigInteger.ModPow(a, d, value);
if (x == 1 || x == value - 1)
continue;
for (int r = 1; r < s; r++) {
x = BigInteger.ModPow(x, 2, value);
if (x == 1)
return false;
if (x == value - 1)
break;
}
if (x != value - 1)
return false;
}
return true;
}
}
Тест и тест
BigInteger value = BigInteger.Pow(2, 3217) - 1; // Mersenne prime number (2.5e968)
Stopwatch sw = new Stopwatch();
sw.Start();
Boolean isPrime = value.IsProbablyPrime(10);
sw.Stop();
Console.Write(isPrime ? "probably prime" : "not prime");
Console.WriteLine();
Console.Write(sw.ElapsedMilliseconds);
Вот мой код, где вы можете проверить простоту от 0 до десятичной.MaxValue=79228162514264337593543950335
ОБНОВИТЬ
я сделал некоторые корректировки, чтобы сделать программу быстрее
в:
Intel (R) Atom (TM) @ 1,60 ГГц
2,00 ГБ ОЗУ
32-битная операционная система
Результаты:
1. UInt32.MaxValue = 4294967295
наибольшее простое число ниже UInt32.MaxValue составляет 4294967291
прошедшее время составляет 0,015600 секунд
2. ulong.MaxValue = UInt64.MaxValue = 18446744073709551615
наибольшее простое число ниже ulong.MaxValue составляет 18446744073709551533
Прошедшее время составляет 3 минуты и 57.6059176 секунд.
3. decimal.MaxValue = 79228162514264337593543950335
наибольшее число ниже десятичного. Испытанное значение MaxValue равно 79228162514264337593543950319, но неизвестно, является ли простое число 79228162514264337593543950319, потому что я прервал работу программы по истечении 3 часов и 40 минут (необходимо проверить на ноутбуках с высокими техническими характеристиками)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PrimalityTest
{
class Program
{
static void Main(string[] args)
{
Console.Write("Enter a number: ");
decimal decimal_number = Convert.ToDecimal(Console.ReadLine());
DateTime date = DateTime.Now;
ulong ulong_a;
ulong ulong_b;
if (decimal_number <= ulong.MaxValue)
{
ulong ulong_number = Convert.ToUInt64(decimal_number);
if (ulong_number < 2)
{
Console.WriteLine(ulong_number + " is not a prime number");
}
else if (ulong_number == 2 || ulong_number == 3)
{
Console.WriteLine(ulong_number + " is a prime number");
}
else if (ulong_number % 2 == 0)
{
Console.WriteLine(ulong_number + " is not a prime number and is divisible by 2");
}
else
{
ulong_a = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(ulong_number)));
for (ulong_b = 3; ulong_b <= ulong_a; ulong_b += 2)
{
if (ulong_number % ulong_b == 0)
{
Console.WriteLine(ulong_number + " is not a prime number and is divisible by " + ulong_b);
goto terminate_ulong_primality_test;
}
}
Console.WriteLine(ulong_number + " is a prime number");
}
terminate_ulong_primality_test:
{
}
}
else
{
if (decimal_number % 2 == 0)
{
Console.WriteLine(decimal_number + " is not a prime number and is divisible by 2");
}
else
{
ulong_a = Convert.ToUInt64(Math.Ceiling(Math.Sqrt(ulong.MaxValue) * Math.Sqrt(Convert.ToDouble(decimal_number / ulong.MaxValue))));
for (ulong_b = 3; ulong_b <= ulong_a; ulong_b += 2)
{
if (decimal_number % ulong_b == 0)
{
Console.WriteLine(decimal_number + " is not a prime number and is divisible by " + ulong_b);
goto terminate_decimal_primality_test;
}
}
Console.WriteLine(decimal_number + " is a prime number");
}
terminate_decimal_primality_test:
{
}
}
Console.WriteLine("elapsed time: " + (DateTime.Now - date));
Console.ReadKey();
}
}
}