Pilipets 8 дек 2021 в 12:46

Криптография и генерация больших однозначно простых чисел — критерий Поклингтона

4 мин

7.2K

Криптография*Алгоритмы*Математика*Научно-популярное

Введение

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

О применении простых чисел в криптографии и не только можно прочитать здесь, а в данной статье сконцентрируемся на самом алгоритме.

Подходы к генерации простых чисел

И так пусть у нас есть заданное число порядка больше $10^{35}$ , и мы хотим получить простое число p:p>=N .

Для начала мы можем воспользоваться одним из решето-алгоритмов для получения всех простых чисел до заданного - Эратосфена, Аткина, Сундарама;
Второй подход это генерация рандомных нечётных чисел больше и проверка каждого из них на простоту через перебор делителей, вероятностные и истинные тесты простоты - подходы можно глянуть здесь;
Наконец третий подход это комбинирование элементов из подходов выше для создания более комплексных алгоритмов;

Описание алгоритма

Рассмотрим алгоритм из 3 подхода, который комбинирует решето Эратосфена для получения первичных простых чисел и критерий Поклингтона, который в свою очередь использует малую теорему Ферма, для получения однозначно простого числа. Как было сказано выше, алгоритм итеративный, то есть мы получаем большее простое из текущего .

Строим решето Эратосфена до , где это некая константа - например . Выбираем стартовое простое число - либо принимаем аргументом, либо из построенного решета. Переходим к шагу 2.
Имеем простое число - если , то результат алгоритма это , иначе мы хотим найти простое число - переходим к шагу 3.
Выбираем рандомно чётное числои запишем кандидат на простоту . Переходим к шагу 4.
Проверяем на делимость с простыми числами низкого порядка, полученными на шаге 1 - если число делится на одно из них, то оно составное и возвращаемся к выбору нового кандидата , то есть шагу 2. Иначе число может быть простым, поэтому переходим к шагу 5.
Выбираем рандомно число и проверяем для нашего кандидата на простоту исполнимость следующих двух условий $a^{n-1} \equiv 1\:(mod\:n)$ и .
Если оба исполняются, то по критерию Поклингтона число простое - заменяем и переходим к следующей итерации по поиску большего числа, то есть шагу 2.
Иначе если не исполняется первое условие - $a^{n-1}\equiv1\:(mod\:n)$ , то по малой теореме Ферма число не является простым, поэтому переходим к выбору нового кандидата, то есть шагу 3.
Иначе если не исполняется вторая часть, то анализ немного сложнее - мы нашли делитель для кандидата , поскольку. Предположим, что , что подразумевает не примитивный делитель, а значит не простое - переходим к повторному выбору, то есть шагу 3.
Остаётся случай, когда , что означает $a^r\equiv1\:(mod\:n)$ , а решений этой конгруэнции существует не больше . Одно из решений это , поэтому на интервале существует не болеерешений, следовательно при действительно простом мы найдём (с вероятностью $1-O(s^{-1})$ ) такое , которое бы удовлетворяло критерию Поклингтона, поэтому переходим к шагу 5 для повтора выбора .

Корректность алгоритма

Можно заметить, что полученное на каждой итерации простое число будет не меньше квадрата предыдущего, то есть иметь в два раза больше цифр - выполняя шаги описанные выше мы дойдём к простому числу больше . Из этого так же следует, что количество цифр в результирующем простом числе p:p>N зависит от выбора начального простого числа для алгоритма, поэтому если мы хотим сделать порядка , то это нужно учесть.

Исследование корректности и эффективности данного алгоритма выходит за пределы этой статьи, однако алгоритм имеет место быть из-за исследований Дирихле о простых числах в арифметических прогрессиях, исследований Люстерника о первом простом числе в такой прогрессии и гипотезы Крамера о расстояниях между двумя последовательными простыми числами.

Код алгоритма на Python

def generatePrime(n : int, primes = None, s = None):
    """Generates prime number with at least n digits:

    : param n: number of 10-based digits in the generate prime is at least n;
    : param primes: an iterable object of numbers that are used as small factors
    for pre-prime verification. If None, is computed using getSieve(1000);
    : param s: initial prime number - if None, last from primes is used;
    """

    # Any prime number higher than the up_limit suffices the result.
    up_limit = 10**n

    # Get the list of small primes which are used as small divisors
    # to reject the n candidate before the Pocklington test.
    if not primes: primes = getSieve(1000)

    if not s: s = primes[-1] # initial prime
    while s < up_limit:
        lo, hi = (s + 1) >> 1, (s << 1) + 1

        # Proceed with finding new prime n
        while True:
            r = random.randint(lo, hi) << 1 # get random even r from [s, 4*s + 2]
            n = s*r + 1 # n is prime candidate, s^2 + 1 <= n <= 4s^2 + 2s + 1

            # reject n if n divides some number in primes list
            if not is_probably_prime(n, primes): continue

            # Here n is probably prime - apply Pocklington criterion to verify it
            while True:
                a = random.randint(2, n-1)

                # Fermat’s little theorem isn't satisfied - choose another n
                if pow(a, n-1, n) != 1: break

                d = math.gcd((pow(a, r, n) - 1) % n, n)
                if d != n:
                    if d == 1: s = n # n is prime, replace s with n
                    else: pass # n isn't prime, choose another n
                    break
                else: pass # a^r mod n == 1, choose another a
            if s == n: break
    return s

После нескольких запусков с разным аргументом n получаем 5 простых чисел:

1)	P1 = 222479360228659844149346639882089160021, D1 = 39
2)	P2 = 327235960958148645696052834806967763219, D2 = 39
3)	P3 = 1703805325300022851813841485118972214405495022945891, D3 = 52
4)	P4 = 848995467487101811203366361379372085728608261197707959, D4 = 54
5)	P5 = 1041875824682281112078115198781702612619843793759431, D5 = 52

В конце убеждаемся в простоте через sympy.ntheory.primetest.isprime.

Заключение

Целью данной статьи было показать читателю эффективный итеративный алгоритм по получению больших однозначно простых чисел, который использует другие алгоритмы на числах - решето Эратосфена, вознесение в степень по модулю, малая теорема Ферма, критерий Поклингтона.

Названия этого алгоритма я не нашёл, поэтому укажите в комментариях, если кто-то знает. Весь код можно глянуть в репозитории.

Теги:

Хабы: