Тест Поклингтона на простоту

В математике тест на простоту Поклингтона–Лемера — это тест на простоту, разработанный Генри Кэбурном Поклингтоном [1] и Дерриком Генри Лемером . [2] Тест использует частичную факторизацию для доказательства того, что целое число является простым . Н − 1 {\displaystyle N-1} Н {\displaystyle N}

Он выдает сертификат простоты, который можно найти с меньшими усилиями, чем тест простоты Лукаса , требующий полной факторизации числа . Н − 1 {\displaystyle N-1}

критерий Поклингтона

Базовая версия теста основана на теореме Поклингтона (или критерии Поклингтона ), которая формулируется следующим образом:

Пусть будет целым числом, и предположим, что существуют натуральные числа a и p, такие что Н > 1 {\displaystyle N>1}

а Н − 1 ≡ 1 ( мод Н ) {\displaystyle a^{N-1}\equiv 1{\pmod {N}}} ( 1 )
p — простое число, и п | Н − 1 {\displaystyle p\vert N-1} п > Н − 1 {\displaystyle p>{\sqrt {N}}-1} ( 2 )
gcd ( а ( Н − 1 ) / п − 1 , Н ) = 1 {\displaystyle \НОД {(a^{(N-1)/p}-1,N)}=1} ( 3 )

Тогда N — простое число. [3] Здесь означает, что после нахождения остатка от деления на k , i и j равны; означает, что i является делителем для j ; а gcd — наибольший общий делитель . я ≡ дж ( мод к ) {\displaystyle i\equiv j{\pmod {k}}} я | дж {\displaystyle i\vert j}

Примечание: Уравнение ( 1 ) — это просто тест Ферма на простоту . Если мы находим любое значение a , не делящееся на N , такое, что уравнение ( 1 ) ложно, мы можем немедленно заключить, что N не является простым числом. (Это условие делимости явно не указано, поскольку оно подразумевается уравнением ( 3 ).) Например, пусть . При , мы находим, что . Этого достаточно, чтобы доказать, что N не является простым числом. Н = 35 {\displaystyle N=35} а = 2 {\displaystyle а=2} а Н − 1 ≡ 9 ( мод Н ) {\displaystyle a^{N-1}\equiv 9{\pmod {N}}}

Доказательство

Предположим, что N не является простым числом. Это означает, что должно быть простое число q , которое делит N. д ≤ Н {\displaystyle q\leq {\sqrt {N}}}

Так как , и так как p — простое число, . п > Н − 1 ≥ д − 1 {\displaystyle p>{\sqrt {N}}-1\geq q-1} п > д − 1 {\displaystyle p>q-1} gcd ( п , д − 1 ) = 1 {\displaystyle \НОД {(p,q-1)}=1}

Таким образом, должно существовать целое число u , мультипликативное обратное числу p по модулю q −1 , обладающее тем свойством, что

ты п ≡ 1 ( мод д − 1 ) {\displaystyle up\equiv 1{\pmod {q-1}}} ( 4 )

и поэтому, по малой теореме Ферма

а ты п ≡ а ( мод д ) {\displaystyle a^{up}\equiv a{\pmod {q}}} ( 5 )

Это подразумевает

1 ≡ а Н − 1 ( мод д ) {\displaystyle 1\;\;\equiv a^{N-1}{\pmod {q}}} , по ( 1 ) так как д | Н {\displaystyle q\vert N}
≡ ( а Н − 1 ) ты ≡ а ты ( Н − 1 ) ≡ а ты п ( ( Н − 1 ) / п ) ≡ ( а ты п ) ( Н − 1 ) / п ( мод д ) {\displaystyle \equiv (a^{N-1})^{u}\equiv a^{u(N-1)}\equiv a^{up((N-1)/p)}\equiv (a^{up})^{(N-1)/p}{\pmod {q}}} ,
≡ а ( Н − 1 ) / п ( мод д ) {\displaystyle \equiv a^{(N-1)/p}{\pmod {q}}} , по ( 5 )

Это показывает, что q делит в ( 3 ) , и, следовательно , это противоречие. [3] gcd ( ) {\displaystyle \gcd()} gcd ( ) ≠ 1 {\displaystyle \gcd()\neq 1}

При наличии N , если можно найти p и a, удовлетворяющие условиям теоремы, то N является простым числом. Более того, пара ( p , a ) представляет собой сертификат простоты , который можно быстро проверить, чтобы удовлетворить условиям теоремы, подтверждая, что N является простым числом.

Основная трудность заключается в нахождении значения p, которое удовлетворяет ( 2 ). Во-первых, обычно трудно найти большой простой множитель большого числа. Во-вторых, для многих простых чисел N такого p не существует. Например, не имеет подходящего p, поскольку , и , что нарушает неравенство в ( 2 ) ; другие примеры включают и . Н = 17 {\displaystyle N=17} Н − 1 = 2 4 {\displaystyle N-1=2^{4}} п = 2 < Н − 1 {\displaystyle p=2<{\sqrt {N}}-1} Н = 19 , 37 , 41 , 61 , 71 , 73 , {\displaystyle N=19,37,41,61,71,73,} 97 {\displaystyle 97}

При p найти a не так уж и сложно. [4] Если N — простое число, то по малой теореме Ферма любое a в интервале будет удовлетворять ( 1 ) (однако случаи и тривиальны и не будут удовлетворять ( 3 )). Это a будет удовлетворять ( 3 ) до тех пор, пока ord( a ) не делится . Таким образом, случайно выбранное a в интервале имеет хорошие шансы на работу. Если a — генератор mod N , его порядок равен ⁠ ⁠ и поэтому метод гарантированно будет работать для этого выбора. 1 ≤ а ≤ Н − 1 {\displaystyle 1\leq a\leq N-1} а = 1 {\displaystyle а=1} а = Н − 1 {\displaystyle а=N-1} ( Н − 1 ) / п {\displaystyle (N-1)/п} 2 ≤ а ≤ Н − 2 {\displaystyle 2\leq a\leq N-2} Н − 1 {\displaystyle N-1}

Обобщенный тест Поклингтона

Вышеуказанную версию теоремы Поклингтона иногда невозможно применить, поскольку некоторые простые числа таковы, что не существует простого числа, делящегося на . Следующая обобщенная версия теоремы Поклингтона применима более широко. [5] : Следствие 1  Н {\displaystyle N} п {\displaystyle p} Н − 1 {\displaystyle N-1} п > Н − 1 {\displaystyle p>{\sqrt {N}}-1}

Теорема: Разложим N  − 1 на множители , как N  − 1 =  AB , где A и B — взаимно простые числа, разложение A на простые множители известно, но разложение B не обязательно известно. А > Н {\displaystyle A>{\sqrt {N}}}

Если для каждого простого множителя p числа A существует целое число такое, что а п {\displaystyle а_{р}}

а п Н − 1 ≡ 1 ( мод Н ) {\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}} , и ( 6 )
gcd ( а п ( Н − 1 ) / п − 1 , Н ) = 1 {\displaystyle \НОД {(a_{p}^{(N-1)/p}-1,N)}=1} , ( 7 )

тогда N — простое число.

Доказательство

Пусть p — простое число, делящее A , и пусть — максимальная степень числа p, делящая A. Пусть q — простой множитель N. Для из следствия следует множество . Это означает , что и ввиду также . п е {\displaystyle p^{e}} а п {\displaystyle а_{р}} б ≡ а п ( Н − 1 ) / п е ( мод д ) {\displaystyle b\equiv a_{p}^{(N-1)/p^{e}}{\pmod {q}}} б п е ≡ а п Н − 1 ≡ 1 ( мод д ) {\displaystyle b^{p^{e}}\equiv a_{p}^{N-1}\equiv 1{\pmod {q}}} gcd ( а п ( Н − 1 ) / п − 1 , Н ) = 1 {\displaystyle \НОД {(a_{p}^{(N-1)/p}-1,N)}=1} б п е − 1 ≡ а п ( Н − 1 ) / п ≢ 1 ( мод д ) {\displaystyle b^{p^{e-1}}\equiv a_{p}^{(N-1)/p}\not \equiv 1{\pmod {q}}}

Это означает, что порядок равен b ( mod q ) {\displaystyle b{\pmod {q}}} p e {\displaystyle p^{e}}

Таким образом, . То же самое наблюдение справедливо для каждого простого коэффициента мощности A , что подразумевает . p e | ( q − 1 ) {\displaystyle p^{e}\vert (q-1)} p e {\displaystyle p^{e}} A | ( q − 1 ) {\displaystyle A\vert (q-1)}

В частности, это означает q > A ≥ N . {\displaystyle q>A\geq {\sqrt {N}}.}

Если бы N было составным, оно обязательно имело бы простой множитель, который меньше или равен . Было показано, что такого множителя нет, что доказывает, что N является простым. N {\displaystyle {\sqrt {N}}}

Комментарии

Тест на простоту Поклингтона–Лемера следует непосредственно из этого следствия. Чтобы использовать это следствие, сначала найдите достаточно множителей числа N  − 1 , чтобы произведение этих множителей превышало . Назовем это произведение A . Затем пусть B = ( N  − 1)/ A будет оставшейся, неразложенной частью числа N  − 1 . Неважно, является ли B простым числом. Нам просто нужно проверить, что ни одно простое число, которое делит A, также делит B , то есть что A и B являются взаимно простыми. Затем для каждого простого множителя p числа A найдите , который удовлетворяет условиям ( 6 ) и ( 7 ) следствия. Если такое s может быть найдено, следствие подразумевает, что N является простым числом. N {\displaystyle {\sqrt {N}}} a p {\displaystyle a_{p}} a p {\displaystyle a_{p}}

По словам Коблица, = 2 часто работает. [3] a p {\displaystyle a_{p}}

Пример

Определите,

N = 27457 {\displaystyle N=27457}

является простым.

Сначала найдем малые простые множители . Мы быстро найдем, что N − 1 {\displaystyle N-1}

N − 1 = 2 6 ⋅ 3 ⋅ B = 192 ⋅ B {\displaystyle N-1=2^{6}\cdot 3\cdot B=192\cdot B} .

Мы должны определить, удовлетворяют ли и условиям Следствия. , так что . Таким образом, мы разложили достаточно для применения Следствия. Мы также должны проверить, что . A = 192 {\displaystyle A=192} B = ( N − 1 ) / A = 143 {\displaystyle B=(N-1)/A=143} A 2 = 36864 > N {\displaystyle A^{2}=36864>N} A > N {\displaystyle A>{\sqrt {N}}} N − 1 {\displaystyle N-1} gcd ( A , B ) = 1 {\displaystyle \gcd {(A,B)}=1}

Не имеет значения, является ли число B простым (на самом деле, это не так).

Наконец, для каждого простого множителя p числа A методом проб и ошибок найдите значение p , удовлетворяющее условиям ( 6 ) и ( 7 ) .

Для , попробуйте . Возведение в эту высокую степень можно эффективно выполнить с помощью двоичного возведения в степень : p = 2 {\displaystyle p=2} a 2 = 2 {\displaystyle a_{2}=2} a 2 {\displaystyle a_{2}}

a 2 N − 1 ≡ 2 27456 ≡ 1 ( mod 27457 ) {\displaystyle a_{2}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}
gcd ( a 2 ( N − 1 ) / 2 − 1 , N ) = gcd ( 2 13728 − 1 , 27457 ) = 27457 {\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(2^{13728}-1,27457)}=27457} .

Итак, удовлетворяет ( 6 ) , но не ( 7 ) . Поскольку нам разрешено разное a p для каждого p , попробуйте вместо этого: a 2 = 2 {\displaystyle a_{2}=2} a 2 = 5 {\displaystyle a_{2}=5}

a 2 N − 1 ≡ 5 27456 ≡ 1 ( mod 27457 ) {\displaystyle a_{2}^{N-1}\equiv 5^{27456}\equiv 1{\pmod {27457}}}
gcd ( a 2 ( N − 1 ) / 2 − 1 , N ) = gcd ( 5 13728 − 1 , 27457 ) = 1 {\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(5^{13728}-1,27457)}=1} .

Таким образом, удовлетворяются оба условия: ( 6 ) и ( 7 ) . a 2 = 5 {\displaystyle a_{2}=5}

Для второго простого множителя числа A попробуйте : p = 3 {\displaystyle p=3} a 3 = 2 {\displaystyle a_{3}=2}

a 3 N − 1 ≡ 2 27456 ≡ 1 ( mod 27457 ) {\displaystyle a_{3}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}} .
gcd ( a 3 ( N − 1 ) / 3 − 1 , N ) = gcd ( 2 9152 − 1 , 27457 ) = 1 {\displaystyle \gcd {(a_{3}^{(N-1)/3}-1,N)}=\gcd {(2^{9152}-1,27457)}=1} .

a 3 = 2 {\displaystyle a_{3}=2} удовлетворяет как ( 6 ) , так и ( 7 ) .

Это завершает доказательство того, что является простым. Сертификат простоты для будет состоять из двух пар (2, 5) и (3, 2). N = 27457 {\displaystyle N=27457} N = 27457 {\displaystyle N=27457} ( p , a p ) {\displaystyle (p,a_{p})}

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

В нашем примере мы можем с уверенностью сказать, что 2 и 3 являются простыми числами, и таким образом мы доказали наш результат. Сертификат простоты — это список пар, который можно быстро проверить в следствии. ( p , a p ) {\displaystyle (p,a_{p})}

Если бы наш пример включал большие простые множители, сертификат был бы более сложным. Сначала он состоял бы из нашего начального раунда a p s , которые соответствуют «простым» множителям A ; Затем для каждого множителя A , простота которого неопределенна, у нас было бы больше a p , и так далее для множителей этих множителей, пока мы не достигнем множителей, простота которых определена. Это может продолжаться для многих слоев, если начальное простое число велико, но важным моментом является то, что может быть создан сертификат, содержащий на каждом уровне простое число, которое нужно проверить, и соответствующее a p s , которое можно легко проверить.

Расширения и варианты

В статье 1975 года Брилхарта, Лемера и Селфриджа [5] дано доказательство того, что показано выше как «обобщенная теорема Поклингтона» в виде теоремы 4 на странице 623. Приведены дополнительные теоремы, которые допускают меньшую факторизацию. Сюда входит их теорема 3 (усиление теоремы Прота 1878 года):

Пусть где p — нечетное простое число, такое что . Если существует a, для которого , но , то N — простое число. N − 1 = m p {\displaystyle N-1=mp} 2 p + 1 > N {\displaystyle 2p+1>{\sqrt {N}}} a ( N − 1 ) / 2 ≡ − 1 ( mod N ) {\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}} a m / 2 ≢ − 1 ( mod N ) {\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}}

Если N велико, часто бывает трудно разложить на множители достаточное количество для применения приведенного выше следствия. Теорема 5 статьи Брилхарта, Лемера и Селфриджа допускает доказательство простоты, когда факторизованная часть достигла только . Представлено много дополнительных таких теорем, которые позволяют доказать простоту N на основе частичной факторизации , , , и . [5] [6] [7] N − 1 {\displaystyle N-1} ( N / 2 ) 1 / 3 {\displaystyle (N/2)^{1/3}} N − 1 {\displaystyle N-1} N + 1 {\displaystyle N+1} N 2 + 1 {\displaystyle N^{2}+1} N 2 ± N + 1 {\displaystyle N^{2}\pm N+1}

Ссылки

  • Леонард Юджин Диксон, «История теории чисел», том 1, стр. 370, Chelsea Publishing, 1952 г.
  • Генри Поклингтон, «Math. Quest. Educat. Times», (2), 25, 1914, стр. 43-46 (Математические вопросы и решения в продолжение математических колонок «Educational times».)
  1. ^ Поклингтон, Генри К. (1914–1916). «Определение простой или составной природы больших чисел теоремой Ферма». Труды Кембриджского философского общества . 18 : 29–30 . Получено 22 июня 2022 г.
  2. ^ DH Lehmer (1927). «Проверки простоты с помощью обратной теоремы Ферма». Bull. Amer. Math. Soc . 33 (3): 327–340. doi : 10.1090/s0002-9904-1927-04368-3 .
  3. ^ abc Koblitz, Neal (1994). Курс теории чисел и криптографии . Graduate Texts in Mathematics. Vol. 144 (2nd ed.). Springer. ISBN 0-387-94293-9.
  4. ^ Роберто Аванци; Анри Коэн; Кристоф Дош; Герхард Фрей; Таня Ланге ; Ким Нгуен; Фредерик Веркаутерен (2005). Справочник по криптографии эллиптических и гиперэллиптических кривых. Бока-Ратон: Чепмен и Холл/CRC.
  5. ^ abc Brillhart, John ; Lehmer, DH ; Selfridge, JL (апрель 1975 г.). "Новые критерии простоты и факторизации 2m ± 1" (PDF) . Mathematics of Computation . 29 (130): 620–647. doi : 10.1090/S0025-5718-1975-0384673-1 . JSTOR  2005583.
  6. ^ Уильямс, Хью К.; Холте, Р. (июль 1978 г.). «Некоторые наблюдения о проверке простоты». Математика вычислений . 32 (143): 905–917. doi : 10.2307/2006495 . JSTOR  2006495.
  7. ^ Классические тесты
  • Крис Колдуэлл, «Доказательство простоты 3.1: тесты n-1 и тесты Пепина для Ферма» на Prime Pages .
  • Крис Колдуэлл, «Доказательство простоты 3.2: тесты n+1 и тест Люка-Лемера для Мерсенна» на Prime Pages .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pocklington_primality_test&oldid=1221097228"