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

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

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

Критерий Поклингтона [ править ]

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

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

${\ Displaystyle а ^ {N-1} \ эквив 1 {\ pmod {N}}}$

( 1 )

p простое и${\ displaystyle p \ vert N-1}$${\ displaystyle p> {\ sqrt {N}} - 1}$

( 2 )

${\ Displaystyle \ НОД {(а ^ {(N-1) / p} -1, N)} = 1}$

( 3 )

Тогда N простое. ^[3]

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

Доказательство этой теоремы [ править ]

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

Так как , и так как р простое, .${\ displaystyle p> {\ sqrt {N}} - 1 \ geq q-1}$${\ displaystyle p> q-1}$${\ displaystyle \ gcd {(p, q-1)} = 1}$

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

${\ Displaystyle вверх \ экв 1 {\ pmod {q-1}}}$

( 4 )

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

${\ Displaystyle а ^ {вверх} \ эквив а {\ pmod {q}}}$

( 5 )

Из этого следует

${\ Displaystyle 1 \; \; \ эквив а ^ {N-1} {\ pmod {q}}}$, согласно ( 1 ), поскольку${\ displaystyle q \ vert N}$

${\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}}}$,

${\displaystyle \equiv a^{(N-1)/p}{\pmod {q}}}$, по ( 5 )

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

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

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

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

Обобщенный тест Поклингтона [ править ]

Обобщенная версия теоремы Поклингтона более широко применима, поскольку не требует нахождения единственного большого простого множителя ; кроме того, это позволяет использовать различное значение a для каждого известного простого фактора . ^{[5] : Следствие 1}${\displaystyle N-1}$${\displaystyle N-1}$

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

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

${\displaystyle a_{p}^{N-1}\equiv 1{\pmod {N}}}$, и

( 6 )

${\displaystyle \gcd {(a_{p}^{(N-1)/p}-1,N)}=1}$,

( 7 )

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

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

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

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

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

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

Тест [ править ]

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

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

Пример [ править ]

Определить

${\displaystyle N=27457}$

простое.

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

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

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

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

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

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

${\displaystyle a_{2}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(2^{13728}-1,27457)}=27457}$.

Итак, удовлетворяет ( 6 ), но не ( 7 ) . Как мы позволили другому в _р для каждого р , попробуйте вместо этого:${\displaystyle a_{2}=2}$${\displaystyle a_{2}=5}$

${\displaystyle a_{2}^{N-1}\equiv 5^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(5^{13728}-1,27457)}=1}$.

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

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

${\displaystyle a_{3}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$.

${\displaystyle \gcd {(a_{3}^{(N-1)/3}-1,N)}=\gcd {(2^{9152}-1,27457)}=1}$.

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

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

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

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

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

Расширения и варианты [ править ]

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

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

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

Ссылки [ править ]

• Леонард Юджин Диксон, "История теории чисел" том 1, стр. 370, Chelsea Publishing, 1952 г.
• Генри Поклингтон, «Math. Quest. Educat. Times», (2), 25, 1914, стр. 43-46 (Математические вопросы и решения в продолжении математических колонок «Educational Times»).

Внешние ссылки [ править ]

• Крис Колдуэлл, «Доказательство первичности 3.1: тесты n-1 и тесты Пепина для ферматов» на Prime Pages .
• Крис Колдуэлл, «Доказательство первичности 3.2: n + 1 тестов и тест Лукаса-Лемера для Мерсенна» на Prime Pages .