12.11.2020

Тест Адлемана — Померанса — Румели


Тест Адлемана-Померанса-Румели (или Адлемана-Померанца-Румели, тест APR) — наиболее эффективный, детерминированный и безусловный на сегодняшний день тест простоты чисел, разработанный в 1983 году. Назван в честь его исследователей — Леонарда Адлемана, Карла Померанса и Роберта Румели. Алгоритм содержит арифметику в цикломатических полях.

Впоследствии алгоритм был улучшен Генри Коэном и Хендриком Ленстрой до APR-CL, время работы которого для любого числа n {displaystyle n} можно вычислить как O ( ( ln ⁡ n ) c ln ln ln ⁡ n ) {displaystyle O((ln n)^{c,ln ,ln ,ln n})} , где c {displaystyle c} — некоторая вычисляемая константа.

История

До 1980 года у всех известных алгоритмов проверки на простоту, за исключением вероятностных и недоказанных, временная сложность алгоритма была экспоненциальной. Однако в 1983 г. был разработан алгоритм, лежащий вблизи P-класса. Технически алгоритм не относится к этому классу, однако медленно растущая сложность O ( ( ln ⁡ n ) c ln ln ln ⁡ n ) {displaystyle O((ln n)^{c,ln ,ln ,ln n})} позволяет практическое использование алгоритма.

К примеру, для числа n {displaystyle n} — гуголплекс, ln ⁡ ln ⁡ ln ⁡ n ≈ 5,442 82 {displaystyle ln ln ln napprox 5{,}44282}

Ключевые понятия

Евклидово простое число

Пусть имеется некоторое конечное множество J {displaystyle {mathcal {J}}} простых чисел. Если для некоторого простого числа q {displaystyle q} выполнены следующие условия:

  • q − 1 {displaystyle q-1} — свободное от квадратов число
  • все простые делители q − 1 {displaystyle q-1} принадлежат множеству J {displaystyle {mathcal {J}}}
  • тогда q {displaystyle q} называется Евклидовым простым числом относительно множества J {displaystyle {mathcal {J}}} .

    Набор «начальных» простых чисел

    Для заданного числа n {displaystyle n} построим множество J = J ( n ) {displaystyle {mathcal {J}}={mathcal {J}}(n)} такое, что произведение всех Евклидовых простых чисел относительно этого множества будет больше n {displaystyle {sqrt {n}}} . Выберем наименьшее возможное J ( n ) {displaystyle {mathcal {J}}(n)} .

    Элементы p {displaystyle p} из этого множества назовем набором «начальных» простых чисел.

    Indq(x)

    Введем некоторое число I n d q = I n d q ( x ) {displaystyle Ind_{q}=Ind_{q}(x)} . Пусть t q {displaystyle t_{q}} — его первообразный корень. Тогда должно выполняться следующее условие:

    x ≡ t q I n d q ( x ) mod q {displaystyle xequiv {t_{q}}^{Ind_{q}(x)}mod q} ,

    где ( x , q ) = 1 {displaystyle (x,q)=1} .

    Замечание: В качестве I n d q ( x ) {displaystyle Ind_{q}(x)} выбираем наименьшее неотрицательное число.

    Сумма Якоби

    Суммой Якоби называют сумму следующего вида:

    J a , b = ∑ ( x L ) p − a ( 1 − x L ) p − b {displaystyle J_{a,b}={sum }{left({frac {x}{mathfrak {L}}} ight)}_{p}^{-a}{left({frac {1-x}{mathfrak {L}}} ight)}_{p}^{-b}} ,

    где суммирование идет по всем наборам классов смежности для x {displaystyle x} в Z [ ζ q ] / L {displaystyle mathbf {Z} [zeta _{q}]/{mathfrak {L}}} , кроме тех, что равны 0 , 1 mod L {displaystyle 0,1mod {mathfrak {L}}} .

    Ключевые леммы

    Основные леммы, используемые при доказательстве корректности алгоритма:


    Лемма 1.

    Простые идеалы из Z [ ζ q ] {displaystyle mathbf {Z} [zeta _{q}]} , лежащие над главным идеалом ( q ) {displaystyle (q)} это:

    L i = ( q , h i ( ζ q ) ) {displaystyle {mathfrak {L}}_{i}=(q,h_{i}(zeta _{q}))} для всех i = 1.. g   . {displaystyle i=1..g~.}


    Лемма 2.

    Пусть n ≥ 2 {displaystyle ngeq 2} и имеет порядок f {displaystyle f} в группе ( Z / p ) ∗ {displaystyle (mathbf {Z} /p)^{*}} . Возьмем g = ( p − 1 ) / f {displaystyle g=(p-1)/f} . Так же Φ p ( x ) ≡ ∏ i = 1 g h i ( x ) mod n   , {displaystyle Phi _{p}(x)equiv prod _{i=1}^{g}h_{i}(x)mod n~,} где h i ( x ) {displaystyle h_{i}(x)} — многочлен в Z [ x ] {displaystyle mathbf {Z} [x]} для каждого f {displaystyle f} . Будем считать, что идеалы A i = ( n , h i ( ζ q ) )   . {displaystyle {mathfrak {A}}_{i}=(n,h_{i}(zeta _{q}))~.} Если r {displaystyle r} является простым делителем n {displaystyle n} , тогда в Z [ ζ q ] {displaystyle mathbf {Z} [zeta _{q}]} : ( r ) = ∏ i = 1 g ( r , A i )   , {displaystyle (r)=prod _{i=1}^{g}(r,{mathfrak {A}}_{i})~,}

    и каждое ( r , A i ) {displaystyle (r,{mathfrak {A}}_{i})} , делимое на некоторый простой идеал из Z [ ζ q ] {displaystyle mathbf {Z} [zeta _{q}]} , лежит над ( r )   . {displaystyle (r)~.}


    Лемма 3.

    Возьмем p > 2 {displaystyle p>2} и элементы α ,   γ ∈ Q ( ζ q ) {displaystyle alpha ,~gamma in mathbf {Q} (zeta _{q})} взаимно простые с λ {displaystyle lambda } и относительно друг друга. ( α γ ) p =   ( γ α ) p ( α , γ ) λ   . {displaystyle left({frac {alpha }{gamma }} ight)_{p}=~left({frac {gamma }{alpha }} ight)_{p}(alpha ,gamma )_{lambda }~.}

    ( ⋅ , ⋅ ) λ {displaystyle (cdot ,cdot )_{lambda }} — символ Гильберта.


    Лемма 4. Если α ≡ 1 mod λ i ,   γ ≡ 1 mod λ j ,   i + j ≥ p + 1 {displaystyle alpha equiv 1mod lambda ^{i},~gamma equiv 1mod lambda ^{j},~i+jgeq p+1} , тогда ( α , γ ) λ = 1   . {displaystyle (alpha ,gamma )_{lambda }=1~.}


    Лемма 5.

    Выберем a ,   b ∈ Z {displaystyle a,~bin mathbf {Z} } такие, что a b ( a + b ) ≢ 0 mod p {displaystyle ab(a+b) ot equiv 0mod p} . Для u ∈ Z {displaystyle uin mathbf {Z} } положим: θ a , b ( u ) = [ a + b p u ] − [ a p u ] − [ b p u ] , {displaystyle heta _{a,b}(u)=left[{frac {a+b}{p}}{u} ight]-left[{frac {a}{p}}{u} ight]-left[{frac {b}{p}}{u} ight],} то есть θ a , b ( u ) = 0 {displaystyle heta _{a,b}(u)=0} или 1 {displaystyle 1} .

    Тогда J a , b ( L ) = ∏ u = 1 p − 1 σ u − 1 ( A ) θ a , b ( u )   . {displaystyle J_{a,b}({mathfrak {L}})=prod _{u=1}^{p-1}{sigma _{u}}^{-1}({mathfrak {A}})^{ heta _{a,b}(u)}~.}


    Лемма 6..

    Для всех a ,   b ∈ Z : {displaystyle a,~bin mathbf {Z} :}

    − J a , b ( L ) = 1 mod λ 2   . {displaystyle -J_{a,b}({mathfrak {L}})=1mod {lambda }^{2}~.}


    Лемма 7.

    Если p > 2 {displaystyle p>2} , то существуют такие a , b ∈ Z   , {displaystyle a,bin mathbf {Z} ~,} что a b ( a + b ) ≢ 0 mod p {displaystyle ab(a+b) ot equiv 0mod p} и

    θ ^ a , b ≐ ∑ u = 1 p − 1 θ a , b ( u ) ⋅ u − 1 ≢ 0   mod   p   , {displaystyle {hat { heta }}_{a,b}doteq sum _{u=1}^{p-1} heta _{a,b}(u)cdot u^{-1} ot equiv 0~mod ~p~,} где u − 1 {displaystyle u^{-1}} — обратный элемент к u mod p   . {displaystyle umod p~.}


    Лемма (Извлечения).

    Пусть A   ,   A 1 {displaystyle {mathfrak {A}}~,~{mathfrak {A}}_{1}} — идеалы в Z [ ζ q ] {displaystyle mathbf {Z} [zeta _{q}]} такие, что p ∤ N A = N A 1 {displaystyle p mid N{mathfrak {A}}=N{mathfrak {A}}_{1}} и пусть R   ,   R 1 {displaystyle {mathfrak {R}}~,~{mathfrak {R}}_{1}} сопряженные простые идеалы, делящие A   ,   A 1 {displaystyle {mathfrak {A}}~,~{mathfrak {A}}_{1}} соответственно. Пускай существует такое γ ∈ Z [ ζ q ]   , {displaystyle gamma in mathbf {Z} [zeta _{q}]~,} что ⟨ γ A ⟩ p ≠ 0 , ≠ 1 {displaystyle leftlangle {frac {gamma }{mathfrak {A}}} ight angle _{p} eq 0, eq 1} . Тогда для любого α 1 ∈ Z [ ζ q ] {displaystyle alpha _{1}in mathbf {Z} [zeta _{q}]} выполняется:

    ⟨ γ A ⟩ p m = ⟨ α 1 A 1 ⟩ p {displaystyle {leftlangle {frac {gamma }{mathfrak {A}}} ight angle }_{p}^{m}={leftlangle {frac {alpha _{1}}{{mathfrak {A}}_{1}}} ight angle _{p}}}

    и следовательно

    ⟨ γ R ⟩ p m = ⟨ α 1 R 1 ⟩ p   . {displaystyle {leftlangle {frac {gamma }{mathfrak {R}}} ight angle }_{p}^{m}={leftlangle {frac {alpha _{1}}{{mathfrak {R}}_{1}}} ight angle _{p}}~.}

    Идея алгоритма

    Если n {displaystyle n} является составным числом, то оно имеет некий делитель r {displaystyle r} . Для проверки на простоту ищем это r ≠ 1   , r ≠ n {displaystyle r eq 1~,r eq n} .

    Если нам известны значения I n d q ( r ) mod p {displaystyle Ind_{q}(r)mod p} для каждой пары p , q {displaystyle p,q} , то по китайской теореме об остатках мы можем найти r {displaystyle r} . Каждая пара p , q {displaystyle p,q} выбирается следующим образом: p ∈ J ( n ) {displaystyle pin {mathcal {J}}(n)} , а q {displaystyle q} — простое Евклидово число относительно J ( n ) {displaystyle {mathcal {J}}(n)} такое, что p | q − 1   . {displaystyle p|q-1~.}

    В алгоритме перебираются все возможные значения I n d q ( r ) mod p {displaystyle Ind_{q}(r)mod p} для всех q {displaystyle q} , исходя из того, что известно только одно q   . {displaystyle q~.}

    Алгоритм

    Ввод: целое число n > 1.

    A. Шаг подготовки

    1. Вычисляем наименьшее положительное число f ( n ) {displaystyle f(n)} свободное от квадратов, такое что: ∏ q − 1 | f ( n ) q   p r i m e q > n {displaystyle prod _{q-1|f(n)}^{q~prime}q>{sqrt {n}}} .

    Определим множество «начальных» простых чисел, являющиеся делителями f ( n ) {displaystyle f(n)} . Назовем q {displaystyle q} Евклидовым простым числом, если q {displaystyle q} простое и q − 1 | f ( n ) {displaystyle q-1|f(n)}

    2. Проверим — делится ли n {displaystyle n} на любое «начальное» или Евклидово простое число. Если делитель найдется, причем не равный n {displaystyle n} . Тогда объявляем n {displaystyle n} составным и прерываем алгоритм. Иначе вычислим наименьший положительный первообразный корень t q {displaystyle t_{q}} для каждого Евклидового простого числа q {displaystyle q} .

    3. Для каждого «начального» простого числа p > 2 {displaystyle p>2} найдем числа a ,   b {displaystyle a,~b} такие, что:

    0 < a , b < p {displaystyle 0<a,b<p} ,

    a + b ≡ 0   m o d   p {displaystyle a+bequiv 0~mod~p} ,

    θ ^ a , b = ∑ u = 1 p − 1 θ a , b ( u ) ⋅ u − 1 ≡ 0   mod   p   . {displaystyle {hat { heta }}_{a,b}=sum _{u=1}^{p-1} heta _{a,b}(u)cdot u^{-1}equiv 0~mod ~p~.}

    Для p = 2 {displaystyle p=2} примем a = b = θ ^ a , b = 1 {displaystyle a=b={hat { heta }}_{a,b}=1} .

    4. Для каждого «начального» и Евклидового простых чисел, таких что p | q − 1 {displaystyle {p|q-1}} зафиксируем простой идеал:

    L q = ( q , ζ q − t q ( q − 1 ) / p ) {displaystyle {mathfrak {L}}_{q}=(q,zeta _{q}-t_{q}^{(q-1)/p})} ,

    где q {displaystyle q} принадлежит Z [ ζ q ] {displaystyle {mathsf {Z}}[zeta _{q}]} ,а ζ q = e 2 π i / p {displaystyle {zeta _{q}}=e^{2pi i/p}} — корень из единицы.

    Вычислим сумму Якоби J p ( q ) ∈ Q ( ζ q )   : {displaystyle J_{p}(q)in mathbf {Q} (zeta _{q})~:}

    если p = 2 :   J p ( q ) = − q {displaystyle p=2:~J_{p}(q)=-q} ,

    если p > 2 :   J p ( q ) = − J a , b ( L q ) = − ∑ x = 2 q − 1 ( x L q ) p − a ( 1 − x L q ) p − b . {displaystyle p>2:~J_{p}(q)=-J_{a,b}({mathfrak {L}}_{q})=-sum _{x=2}^{q-1}{left({frac {x}{{mathfrak {L}}_{q}}} ight)}_{p}^{-a}{left({frac {1-x}{{mathfrak {L}}_{q}}} ight)}_{p}^{-b}.}

    B. Шаг вычислений

    1. Для каждого «начального» простого числа p {displaystyle p} найдем НОД в Q ( ζ q ) {displaystyle mathbf {Q} (zeta _{q})} для n {displaystyle n} и набора σ J p ( q ) {displaystyle sigma J_{p}(q)} , где q {displaystyle q} пробегает все значения Евклидовых простых чисел, причем p | q − 1 {displaystyle p|q-1} , а σ {displaystyle sigma } пробегает по всем значениям из Gal ( Q ( ζ q ) / Q ) {displaystyle (mathbf {Q} (zeta _{q})/mathbf {Q} )} . Тогда либо выносим решение о том, что n {displaystyle n} составное, либо строим надлежащий идеал A {displaystyle {mathfrak {A}}} в кольце Z [ ζ q ] {displaystyle mathbf {Z} [zeta _{q}]} , а также находим числа s {displaystyle s} и j ( σ , q ) {displaystyle j(sigma ,q)} , 1 ≤ j ( σ , q ) ≤ p {displaystyle 1leq j(sigma ,q)leq p} такие, что:

    ( σ J p ( q ) ) ( n f − 1 ) / p s ≡ ζ q j ( σ , q )   mod   A {displaystyle (sigma J_{p}(q))^{(n^{f}-1)/{p^{s}}}equiv {zeta _{q}}^{j(sigma ,q)}~mod ~{mathfrak {A}}} ,

    p ∤ ( n f − 1 ) / p s {displaystyle p mid {(n^{f}-1)/{p^{s}}}} или некоторое из ζ q j ( σ , q ) ≠ 1 {displaystyle {zeta _{q}}^{j(sigma ,q)} eq 1} , где f = n   mod   p   . {displaystyle f=n~mod ~p~.}

    2. Для каждого «начального» простого числа p {displaystyle p} сделаем следующее: если для некоторого j ( σ 0 , q 0 ) ≠ p {displaystyle j(sigma _{0},q_{0}) eq p} , тогда возьмем γ = σ 0 J p ( q 0 ) {displaystyle gamma =sigma _{0}J_{p}(q_{0})} . В этом ключе построим числа m ( σ , q ) {displaystyle m(sigma ,q)} для всех σ , q {displaystyle sigma ,q} , 0 ≤ m ( σ , q ) ≤ p − 1 {displaystyle 0leq m(sigma ,q)leq p-1} и такие, что:

    ( γ ( n f − 1 ) / p s ) m ( σ , q ) ≡ ( σ J p ( q ) ) ( n f − 1 ) / p s mod   A . {displaystyle (gamma ^{(n^{f}-1)/{p^{s}}})^{m(sigma ,q)}equiv (sigma J_{p}(q))^{(n^{f}-1)/{p^{s}}}mod ~{mathfrak {A}}.}

    Если же для всех j ( σ , q )   =   p {displaystyle j(sigma ,q)~=~p} , примем m ( σ , q )   =   0 {displaystyle m(sigma ,q)~=~0} .

    C. Шаг объединения результатов

    Проделаем шаги 1-4 для всех натуральных k   , 1 ≤ k ≤ f ( n ) . {displaystyle k~,1leq kleq f(n).}

    1. Для каждого q > 2 {displaystyle q>2} вычислим по китайской теореме об остатках вычислим числа I ( k , q ) {displaystyle I(k,q)} :

    I ( k , q ) = k θ ^ a , b − 1 ∑ j = 1 p − 1 j ⋅ m ( σ j − 1 , q ) mod p   , {displaystyle I(k,q)=k{{hat { heta }}_{a,b}}^{-1}sum _{j=1}^{p-1}jcdot m({sigma _{j}}^{-1},q)mod p~,}

    при всевозможных p {displaystyle p} , что p | q − 1 {displaystyle p|q-1} . Так же положим, что I ( k , 2 ) = 1   . {displaystyle I(k,2)=1~.}

    2. Для каждого q {displaystyle q} посчитаем наименьшее целое, положительное число r ( k , q ) ≡ t q I ( k , q ) mod q . {displaystyle r(k,q)equiv {t_{q}}^{I(k,q)}mod q.}

    3. Используя Китайскую теорему об остатках, вычислим наименьшее положительное число r ( k ) {displaystyle r(k)} такое, что r ( k ) ≡ r ( k , q ) mod q {displaystyle r(k)equiv r(k,q)mod q} для каждого q   . {displaystyle q~.}

    4. Если r ( k ) ≠ 1   ,   r ( k ) ≠ n   , r ( k ) | n {displaystyle r(k) eq 1~,~r(k) eq n~,r(k)|n} , тогда объявляем n {displaystyle n} составным. Иначе переходим к следующему k   . {displaystyle k~.}

    5. Объявляем n {displaystyle n} простым.

    Оценка сложности

    Оценка времени выполнения алгоритма вытекает из следующих теорем:

    Теорема 1.

    Для значений n > 1 {displaystyle n>1} вышеупомянутый алгоритм правильно определяет будет ли n {displaystyle n} простым или составным за время T ( n ) {displaystyle T(n)} . И справедливы следующие оценки: f ( n ) ≤ T ( n )   , {displaystyle f(n)leq T(n)~,} для простых n   , {displaystyle n~,}

    T ( n ) ≤ f c 1 ( n )   , {displaystyle T(n)leq f^{c_{1}}(n)~,} для всех значения n   . {displaystyle n~.} Где c 1 {displaystyle c_{1}} — положительная, вычисляемая константа. Теорема 2.

    Существуют такие положительные, вычисляемые константы c 2 ,   c 3 {displaystyle c_{2},~c_{3}} , что для всех n > 100   : {displaystyle n>100~:}

    ( ln ⁡ ( n ) ) c 2 ln ⁡ ln ⁡ ln ⁡ ( n ) < f ( n ) < ( ln ⁡ ( n ) ) c 3 ln ⁡ ln ⁡ ln ⁡ ( n ) {displaystyle (ln(n))^{c_{2}ln ln ln(n)}<f(n)<(ln(n))^{c_{3}ln ln ln(n)}}

    Программная реализация

    • В UBASIC приведена реализация алгоритма под именем APRT-CLE (APR Test CL extended)
    • factoring applet использует алгоритм APR-CL с определёнными условиями
    • Pari/GP условное использование APR-CL в реализации isprime().
    • mpz_aprcl реализация с открытым исходным кодом. Использует C + GMP.

    Похожие новости:

    Натуральный логарифм 2

    Натуральный логарифм 2
    Натуральный логарифм 2 в десятичной системе счисления (последовательность A002162 в OEIS) равен приблизительно ln ⁡ 2 ≈ 0,693

    Алгоритм Кнута — Морриса — Пратта

    Алгоритм Кнута — Морриса — Пратта
    Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать

    Список интегралов элементарных функций

    Список интегралов элементарных функций
    Интегрирование — это одна из двух основных операций в математическом анализе. В отличие от операции дифференцирования, интеграл от элементарной функции может не быть элементарной функцией. Например,

    Теорема Дирихле о простых числах в арифметической прогрессии

    Теорема Дирихле о простых числах в арифметической прогрессии
    Теорема Дирихле о простых числах в арифметической прогрессии гласит: Из этого следует, что каждая бесконечная арифметическая прогрессия, первый член и разность которой — натуральные взаимно простые
    Комментариев пока еще нет. Вы можете стать первым!

    Добавить комментарий!

    Ваше Имя:
    Ваш E-Mail:
    Введите два слова, показанных на изображении: *
    Популярные новости
    Как обустроиться в однокомнатной квартире?
    Как обустроиться в однокомнатной квартире?
    Далеко не каждый проживает в большом доме или многокомнатной квартире. Как же обустроить интерьер...
    Что нужно знать о поверке счетчиков
    Что нужно знать о поверке счетчиков
    Поверка счетчиков воды, газа и света является обязательной процедурой, которую, в соответствии с...
    Гидроизоляция: виды и используемые материалы
    Гидроизоляция: виды и используемые материалы
    Гидроизоляция позволяет создать непроницаемый слой. Он нужен для защиты конструкции от любых...
    Плей Фортуна - играем в азартные слоты онлайн
    Плей Фортуна - играем в азартные слоты онлайн
    Зачем тратить время на посещение реальных игорных заведений, когда под рукой всегда есть их...
    Виртуальное Азино777 - бонусы, слоты, азарт
    Виртуальное Азино777 - бонусы, слоты, азарт
    Виртуальные игровые площадки привлекают любителей игровых автоматов доступностью и внушительным...
    Особенности листового металла
    Особенности листового металла
    Металлопрокат — это различные профили и расходники, которые используются в строительстве и при...
    Плитка azori для ванной комнаты
    Плитка azori для ванной комнаты
    Основным брендом, который выбирают потребители в виде керамической плитки является azori. Его...
    Все новости