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



Введение

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

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

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

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

  1. Для начала мы можем воспользоваться одним из решето-алгоритмов для получения всех простых чисел до заданного N- Эратосфена, Аткина, Сундарама;

  2. Второй подход это генерация рандомных нечётных чисел больше N и проверка каждого из них на простоту через перебор делителей, вероятностные и истинные тесты простоты - подходы можно глянуть здесь;

  3. Наконец третий подход это комбинирование элементов из подходов выше для создания более комплексных алгоритмов;

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

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

  1. Строим решето Эратосфена до k, где k это некая константа - например 10^3. Выбираем стартовое простое число s- либо принимаем аргументом, либо из построенного решета. Переходим к шагу 2.

  2. Имеем простое число s- если s>N, то результат алгоритма это p:p=s, иначе мы хотим найти простое число n:n>s - переходим к шагу 3.

  3. Выбираем рандомно чётное числоr : s <= r <= 2 * (2 * s + 1) и запишем кандидат на простоту n=s*r+1. Переходим к шагу 4.

  4. Проверяем n на делимость с простыми числами низкого порядка, полученными на шаге 1 - если число делится на одно из них, то оно составное и возвращаемся к выбору нового кандидата n, то есть шагу 2. Иначе число может быть простым, поэтому переходим к шагу 5.

  5. Выбираем рандомно число a:1<a<n и проверяем для нашего кандидата на простоту nисполнимость следующих двух условий a^{n-1}	 \equiv 1\:(mod\:n)и gcd(a^r-1,n)==1.

    Если оба исполняются, то по критерию Поклингтона число n простое - заменяем s:=n и переходим к следующей итерации по поиску большего числа, то есть шагу 2.

    Иначе если не исполняется первое условие - a^{n-1}\equiv1\:(mod\:n), то по малой теореме Ферма число n не является простым, поэтому переходим к выбору нового кандидата, то есть шагу 3.

    Иначе если не исполняется вторая часть, то анализ немного сложнее - мы нашли делитель d:1<d<=nдля кандидата n, посколькуgcd(a^r-1,n)==d. Предположим, что d ≠n, что подразумевает не примитивный делитель, а значит nне простое - переходим к повторному выбору, то есть шагу 3.

    Остаётся случай, когда d==n, что означает a^r\equiv1\:(mod\:n), а решений этой конгруэнции существует не больше r. Одно из решений это a==1, поэтому на интервале 1<a<nсуществует не болееr-1решений, следовательно при действительно простом n мы найдём (с вероятностью 1-O(s^{-1})) такое a, которое бы удовлетворяло критерию Поклингтона, поэтому переходим к шагу 5 для повтора выбора a.

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

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

Заключение

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

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




Комментарии (19):

  1. OGR_kha
    /#23798507

    else: pass

    выглядит незавершенным

    • Sublimentor
      /#23798571

      Я так написал, чтобы подчеркнуть комментарий и следование словесному алгоритму - там действий никаких не нужно в else блоке. Можно заменить на # else: pass n isn't prime, choose another n

      После выполнения инструкции break мы выйдем с цикла по выбору a и перейдём к циклу по выбору n, поэтому произойдёт ровно то, что описано комментарием.

  2. emaxx
    /#23801109 / +1

    Одно из решений это x=1

    Что такое x? Не вижу этой переменной больше нигде

    при действительно простом n мы найдём(можно оценить вероятность от s) такое a

    Самое интересное - эти вероятности и, в целом, требуемые значения s - как раз и не приведено в статье... Без этого вообще непонятно, сколько этот алгоритм будет работать, и насколько он конкурентоспособен по сравнению с другими алгоритмами.

    • Sublimentor
      /#23801139

      А о каких других алгоритмах вы говорите? Пример можно?

      • emaxx
        /#23801171

        Вы же сами даёте ссылки на статьи с другими алгоритмами. Но, для определённости, пример - запуск серии тестов Миллера-Рабина (что, например, используется OpenSSL на практике).

        • Sublimentor
          /#23801183

          Тест Миллера-Рабина вероятностный, который даёт сильное псевдопростое число, а здесь генерируется однозначно простое число.

          • emaxx
            /#23801187

            Вопрос в том, какова стоимость этой гарантии.

            • Sublimentor
              /#23801205

              Я понял, о чём вы говорите. В принципе, я могу дополнить статью сравнением эффективности по времени работы других алгоритмов по генерации простых/псевдопростых чисел с этим - спасибо за предложение по улучшению.

              Но изначальной целью было продемонстрировать сам алгоритм как подход к генерации больших однозначно простых чисел, так как не видел, чтобы он где-то был описан.

              • emaxx
                /#23801259 / +2

                Думаю, сравнение с другими алгоритмами по эффективности было бы очень наглядным!

                Но всё-таки по-прежнему интересен вопрос с асимптотикой в "плохом" случае (я предполагаю, что говорить о "худшем" случае тут неинтересно, поскольку, видимо, алгоритм сильно завязан на рандоме). Сколько разных a нам может понадобиться для проверки одного (положим, "неудачно" выбранного) r? Или сколько, в среднем, r нам понадобится просмотреть?

                • Sublimentor
                  /#23801373

                  Я посмотрел, на существующие криптолибы - по поводу практических оценок эффективности, то сделать это проблематично из-за разных API по генерации простых чисел. Какой-то алгоритм будет генерировать n-e простое, другой - простое c n битами, этот - простое больше n, где-то идут ограничения на кратность 128, 512 бит в размере, где-то и вовсе псевдопростые и т.д.

                  Поэтому больший смысл имеют асимптотические оценки, но для того, чтобы их сделать, то нужно углубляться в те статьи о корректности алгоритма, которые я упомянул ))
                  Ссылки с оценками асимптотики у меня нету, но я читал когда-то об этом алгоритме, но уже не помню, где.

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

                  • emaxx
                    /#23801513 / +2

                    Спасибо за добавленные асимптотики. Это проясняет роль "s" и предварительного решета.

                    Насчёт алгоритма - мне казалось, что в FIPS 186-4 что-то похожее описывалось, но на самом деле, похоже, там другой алгоритм ("Shawe-Taylor"?).

    • Sublimentor
      /#23801149

      В данном случае xможно считать a- когда мы рассматриваем конгруэнцию, то n, r фиксированные параметры, а x это переменная вместо a. Примитивное решениеx==1нас не интересует, так как мы выбирали a>1, поэтому я так и записал.

      • emaxx
        /#23801181

        Эта запись совершенно непонятна.

        • Sublimentor
          /#23801191 / +2

          Спасибо, исправил - заменил x на a.

    • Sublimentor
      /#23801273 / +2

      Если говорить про вероятность того, что для простого nмы найдём нужное a, то это 1 - O(s^{-1}). n и sфиксированные, количество a, которые нас не удовлетворяют, не больше r, всего различных aэто n.

      p=1-O(r/n)=1-O(r/(s*r + 1)) =1-O(s^{-1})

      Добавил оценку вероятности в статью.

  3. paluke
    /#23801775

    Для криптографии важна случайность простого числа. Кажется, ваш алгоритм будет выдавать не совсем случайные числа.

    • Sublimentor
      /#23802875 / +1

      Почему они будут не совсем случайными? Как вы это оценили?

  4. emaxx
    /#23805407 / +1

    После перечитывания FIPS 186-4 (секция C.6) и поиска доп. информации по алгоритму Shawe-Taylor получилось выйти на упоминания алгоритма Maurer, который уже очень похож на то, что описано в статье ("Fast Generation of Secure RSA-Moduli with Almost Maximal Diversity", Maurer, 1989):

    Lemma 1 suggests a method for constructing large primes. One can form the product F = product q_j^beta_j of some known primes q_j, raised to some powers beta_j, and repeatedly choose an integer R < F at random until n = 2RF + 1 can be proved to be prime by an appropriate choice of the base a. Lemma 3 shows that if n is indeed prime and if all q_j's are large, then virtually every base a can be used for certifying the primality of n. On the other hand, if n is composite but does not contain a small prime factor that allows to detect this by trial division, then virtually every base a will satisfy a^{n-1} \ne 1 (mod n) and hence reveal the compositeness of n, unless n is of a very special form.

    Кроме того, там дальше в статье, по-видимому, делаются дополнительные ухищрения, чтобы добиться более равномерной генерации случайных простых.

    Поглядев ещё в статьях, нашёл ещё один близкий аналог - "Generating Provable Primes Efficiently on Embedded Devices" (Clavier, 2012). "Ядро" алгоритма там выглядит ещё ближе к вашему алгоритму:

    We generate a provable prime by doubling at each iteration the size of the current prime p to derive the new prime n = 2rp + 1.

    и псевдокод алгоритма очень похож. Но есть и отличия - например, они стартуют не с решета Эратосфена, а с генерации числа до 2^32 с помощью тестов Миллера-Рабина. У них там много и других интересных соображений - про энтропию, про ускорение подбора случайных параметров путём поиска их в специальной форме, и т. п.

    • Sublimentor
      /#23806103

      Спасибо за ответ - действительно дополняет статью.