Тест на простоту Поклингтона - Википедия - Pocklington primality test

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

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

Критерий поклингтона

Базовая версия теста опирается на Теорема поклингтона (или же Критерий поклингтона), который формулируется следующим образом:

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

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

(1)

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

(2)

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

(3)

потом N простое.^[3]

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

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

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

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

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

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

(4)

и, следовательно, по Маленькая теорема Ферма

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

(5)

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

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

${ Displaystyle эквив (а ^ {N-1}) ^ {и} эквив а ^ {и (N-1)} эквив ^ {вверх ((N-1) / р)} эквив ( ^ {вверх}) ^ {(N-1) / p} { pmod {q}}}$,

${ Displaystyle Equiv a ^ {(N-1) / p} { pmod {q}}}$, к (5)

Это показывает, что q разделяет ${ displaystyle gcd ()}$ в (3), и поэтому это ${ displaystyle gcd () neq 1}$; противоречие.^[3]

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

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

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

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

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

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

Если для каждого простого фактора п из А существует целое число ${ displaystyle a_ {p}}$ так что

${ Displaystyle а_ {р} ^ {N-1} Equiv 1 { pmod {N}}}$, и

(6)

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

(7)

тогда N простое.

Доказательство:Позволять п быть основным разделителем А и разреши ${ displaystyle p ^ {e}}$ быть максимальной мощностью п разделение А.Позволять q быть основным фактором N. Для ${ displaystyle a_ {p}}$ из набора следствий${ Displaystyle б эквив а_ {р} ^ {(N-1) / р ^ {е}} { pmod {q}}}$. Это означает${ Displaystyle Ь ^ {п ^ {е}} экви а_ {р} ^ {N-1} экви 1 { pmod {q}}}$ и из-за ${ Displaystyle gcd {(a_ {p} ^ {(N-1) / p} -1, N)} = 1}$ также${ Displaystyle Ь ^ {п ^ {е-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 А верт (д-1)}$.

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

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

Тест

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

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

Пример

Определить

${ 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 {(А, В)} = 1}$.

Неважно, B простое (на самом деле это не так).

Наконец, для каждого простого фактора п из А, методом проб и ошибок найдите а_п это удовлетворяет (6) и (7).

За ${ displaystyle p = 2}$, пытаться ${ displaystyle a_ {2} = 2}$.Поднятие ${ displaystyle a_ {2}}$ с такой высокой мощностью можно эффективно использовать двоичное возведение в степень:

${ Displaystyle а_ {2} ^ {N-1} эквив 2 ^ {27456} эквив 1 { pmod {27457}}}$

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

Так, ${ displaystyle a_ {2} = 2}$ удовлетворяет (6) но нет (7). Поскольку нам разрешено другое а_п для каждого п, пытаться ${ displaystyle a_ {2} = 5}$ вместо:

${ Displaystyle а_ {2} ^ {N-1} Equiv 5 ^ {27456} эквив 1 { pmod {27457}}}$

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

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

За ${ displaystyle p = 3}$, второй простой фактор А, пытаться ${ displaystyle a_ {3} = 2}$:

${ Displaystyle а_ {3} ^ {N-1} Equiv 2 ^ {27456} Equ 1 { pmod {27457}}}$.

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

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

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

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

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

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

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

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

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

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

Рекомендации

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