C#. Длинная арифметика. Урок 10. Проверка на простоту

Длинная арифметика   24 марта 2013  Автор статьи:  

Простые числа имеют большое приложение в криптографии. В частности они играют огромную роль в алгоритме RSA. В данной статье мы рассмотрим некоторые алгоритмы проверки чисел на простоту. Все они будут вероятностные. Для того, чтобы ответить на вопрос является ли число n простым, достаточно проверить делиться ли оно на числа с 1 до корня из n. Данный алгоритм нас не устраивает, так как, если мы захотим проверить длинное число на простоту, то это займет достаточно большое количество времени. Существует алгоритм, который работает за константное время, но константа настолько велика, что его не применяют на практике.
Первый алгоритм, который мы рассмотрим будет базироваться на теореме Ферма, которая утверждает, что если число простое, то любое число a удовлетворяет равенству: a^(n-1)=1(mod n). Таким образом, если мы найдем a для которого это условие не выполнится, то число гарантированно составное. В предыдущем уроке мы уже написали функцию, которая умеет возводить число по модулю. Дальнейшие исследования показали, что если мы будем проверять только a = 2, то это даст неплохой результат в том плане, что мы достаточно редко будем ошибаться, отсюда напишем этот тривиальный алгоритм:

public bool ProbablyPrime()
{
return BigInteger.One.Equals(new BigInteger("2").Pow(this.Substract(BigInteger.One), this));
}

Покроем его тестами:

[TestMethod()]
public void ProbablyPrimeTest()
{
Assert.AreEqual(true, new BigInteger("12913356924332233347278197422044747348906424876792150589450624221332165981266259462889177379952464129325141172668517474817617218869650479238131067482631443").ProbablyPrime());
Assert.AreEqual(false, new BigInteger("12913356924332233347278197422044747348906424876792150589450624221332165981266259462889177379952464129325141172668517474817617218869650479238131067482631447").ProbablyPrime());

}

Естественно, что данная проверка не является достаточной.

Рандомизированный тест простоты Миллера — Рабина

Данный тест является существенной модификацией простого теста на простоту. В основе данного теста лежит функция Witness, которая возвращает true в случае, если число составное. По сути она является небольшим улучшением проверки 2^(n-1)=1(mod n). Первым делом мы раскладываем число n-1=2^t*u, где u — нечетное. После этого мы проверяем корни на нетривиальность. В результате после t итераций мы либо вычисляем a^(n-1), либо находим нетривиальные корни:

private static bool Witness(BigInteger a, BigInteger n)
{
BigInteger u = n.Substract(One);
int t = 0;
while (u.Mod(new BigInteger("2")).Equals(Zero))
{
t++;
u = u.Div(new BigInteger("2"));
}
BigInteger[] x = new BigInteger[t+1];
x[0] = a.Pow(u, n);
for (int i = 1; i <= t; i++) { x[i] = x[i - 1].Pow(new BigInteger("2"), n); if (x[i].Equals(One) && !x[i - 1].Equals(One) && !x[i - 1].Equals(n.Substract(One))) { return true; } } if (!x[t].Equals(One)) { return true; } return false; }

Тест Миллера - Рабина выбирает несколько чисел a случайным образом, что гарантирует лучшую вероятность того, что число является простым. Так как a - большое число из некоторого диапазона, то давайте реализуем генерацию случайного большого числа в диапазоне с 0 до n - 1. Но, сначала подправим нормализацию, так как в ней раньше удалялся даже последний ноль, при этом сделаем ее static:

private static List normalize(List arr)
{
while (arr.Count > 1 && arr[arr.Count - 1] == 0)
{
arr.RemoveAt(arr.Count - 1);
}
return arr;
}

Для генерации случайного числа воспользуемся следующим алгоритмом, так как разрядом нашего числа является int, то мы можем генерировать каждый разряд в отдельности. При этом начинать мы можем со старших, тогда создадим некоторый флаг, который будет показывает в каком диапазоне мы можем генерировать число. Если этот флаг true, то мы можем взять только число из промежутка с 0 до значение в текущем разряде числа, иначе мы можем взять любое число до базы.

public static BigInteger Generate(BigInteger n)
{
BigInteger maxBigInteger = n.Substract(One);
BigInteger bigBase = new BigInteger(myBase.ToString());
Random r = new Random();
List arr = new List(maxBigInteger.arr.Count);

bool flag = true;
for (int i = maxBigInteger.arr.Count - 1; i >= 0; i--)
{
int temp;
if (flag)
{
temp = r.Next(maxBigInteger.arr[i] + 1);
flag = maxBigInteger.arr[i] == temp;
}
else
{
temp = r.Next(myBase);
}
arr.Add(temp);
}
arr.Reverse();
return new BigInteger(arr, true);
}

Алгоритм Миллера - Рабина состоит из s проверок числа на простоту, где каждый раз мы генерируем новое случайное большое число a, которое будет называться свидетелем. После этого мы запускаем процедуру Witness, которая отвечает нам на вопрос, является ли число составным, если да, то число составное, если нет, то переходим к следующему свидетелю и так s раз:

public static bool IsPrimeMillerRabin(BigInteger n, int s)
{
BigInteger pred = new BigInteger("0");
for (int j = 0; j < s; j++) { BigInteger a = Generate(n); while (a.Equals(pred)) { a = Generate(n); } if (Witness(a, n)) { return false; } } return true; }

Данный тест может детектировать даже числа Кармайкла, на которых бы обычная проверка радостно валилась. (Числа Кармайкла - это такие составные числа, которые удовлетворяют a^(n-1)=1(mod n) для любых a) При этом данный алгоритм основывается на теореме о том, что любое составное число n имеет половину свидетелей из всех чисел c 0 до n-1. Т.е каждый прогон данного алгоритма уменьшает вероятность того, что число составное в 2 раза.

Научиться программировать

  • на Delphi

  • на Java

  • на C++