C#. Длинная арифметика. Урок 11. Генерация простых чисел

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

В данном уроке мы научимся генерировать простые числа. Генерация больших чисел одна из важных задач, которая стоит перед человечеством. На основе больших чисел работают различные криптографические протоколы, в частности RSA. Бороздя интернет в поисках ответа на вопрос «как генерировать большие числа?» я наткнулся только на статью, которая рассказывает как строить устойчивые большие числа. Все остальные сайты не могли ответить ничего внятного кроме предложений использовать различные решета: решето Аткина , решето Сундарама или решето Эратосфена. Конечно, никакая модификация данных алгоритмов не поможет нам найти простое число в приемлемое время. Это связанно с тем, что они находят все простые числа, а наша задача найти хотя бы одно, но большое. Тогда я обратился к стандартным библиотекам Java и СSharp в поисках генератора простых чисел. К сожалению, генерация простых чисел в Csharp отсутствовала, а в Java был только метод probablePrime. На одном из форумов Microsoft был задан вопрос: «Почему в Java есть генерация простых чисел, а у вас нет?» На что Microsoft ответила, что не существует алгоритма генерации простых чисел. Что же это означает, неужели вы читали эту статью зря? Для ответа на этот вопрос откроем код класса BigInteger в Java. Данный класс содержит много эвристик, но основная идея в том, что мы строим большие числа специального вида и проверяем их на простоту. Рассмотрим несколько видов простых чисел:

  • Простые числа Каллена n*2^n+1 Например: 1, 141, 4713, 5795, 6611, 18496, 32292, 32469
  • Простые числа Мерсенна 2^n-1 Например: 3, 7, 31, 127, 8191, 131071, 524287, 2147483647

Существует множество видов простых чисел, о них вы можете найти более полную информацию в интернете. Известно, что простые числа распределены по числовому ряду равномерно, т.е если взять любую возрастающую последовательность, то в ней обязательно встретятся простые числа. Таким образом, как бы вы не искали простое число, хоть перебором всех подряд значений, то вы обязательно найдете его. Притом есть такая теорема, что простых чисел на отрезке с 0 до n примерно n/ln(n), что достаточно похоже на правду и при малых n, например при n=10^9 существует 50847534 простых числа, а наша формула даст 48254942, таким образом у нас есть достаточно хорошая вероятность того, что случайным образом выбранное число окажется простым. Данный способ хорош тем, что ищет не простые числа специального вида, которые не желательно использовать в криптографических протоколах, а любые. Итак, первый генератор простых чисел, который мы напишем будет брать случайное число в некотором диапазоне и проверять его на простоту. Для этого модифицируем наш генератор случайных чисел, и научим брать на вход полуинтервал [A,B), где A и B большие числа:

public static BigInteger Generate(BigInteger a, BigInteger b)
{
return Generate(b.Substract(a)).Add(a);
}

Сама функция нахождения простых чисел на отрезке будет иметь вид:

public static BigInteger GeneratePrime(BigInteger a, BigInteger b)
{
int i = 0;
BigInteger last = new BigInteger("1");
while (i < 10000) { BigInteger temp = BigInteger.Generate(a, b); if(BigInteger.IsPrimeMillerRabin(temp, 100)) { return temp; } else { last = temp; i++; } } return null;//не нашли }

Я выставил количество попыток 1000, но данное число можно брать на вход в функция или выставить другое значение, в зависимости от того сколько вы хотите ждать, если в этом полуинтервале нет простых чисел, и насколько вы хотите не находить простое число, если оно есть. Самое главное при использовании данного алгоритма это не брать слишком длинные полуинтервалы, так как вероятность того, что вы попадете в простое число может значительно упасть.
На этом мы заканчиваем цикл уроков по длинной математике. Конечно, мы не рассмотрели все имеющиеся алгоритмы связанные с длинной арифметикой, но по крайне мере можем использовать эту библиотеку для своих целей.
Скачать исходные коды

  • Алекс

    Так это не C#, а Java. В шарпе нет BigInteger’a

    • Алекс

      Ой, я тупанул, простите.

      • Забей, все норм=)

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

  • на Delphi

  • на Java

  • на C++