Test Adleman-Pomerans-Rumeli

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. února 2020; kontroly vyžadují 3 úpravy .

Adlemann-Pomeranz-Rumeli test (nebo Adleman-Pomeranz-Rumeli test, APR test ) je dosud nejúčinnějším, deterministickým a nepodmíněným testem primality , vyvinutý v roce 1983. Pojmenováno na počest svých výzkumníků - Leonarda Adlemana , Karla Pomeranse a Roberta Roumeliho . Algoritmus obsahuje aritmetiku v cyklomatických polích .

Následně algoritmus vylepšili Henry Cohen a Hendrik Lenstra na APR-CL , jehož dobu běhu pro libovolné číslo lze vypočítat jako , kde je nějaká vypočítaná konstanta. $n$ $O((\ln n)^{c\,\ln \,\ln \,\ln n})$ $C$

Historie

Až do roku 1980 byla u všech známých algoritmů testování primality, kromě pravděpodobnostních a neprokázaných, časová složitost algoritmu exponenciální. Nicméně, v roce 1983 byl vyvinut algoritmus, který leží blízko P - třídě . Přísně vzato, algoritmus do této třídy nepatří, nicméně pomalu rostoucí složitost umožňuje praktické použití algoritmu. $O((\ln n)^{c\,\ln \,\ln \,\ln n})$

Například pro číslo - googolplex , $n$ $\ln \ln \ln n\cca 5{,}44282$

Starý vtip říká:
"Ukázalo se jít do nekonečna, ale nikdo ho nikdy neviděl dělat." $\log \log n$ Ian Stewart

Klíčové pojmy

Euklidovské prvočíslo

Nechť existuje nějaká konečná množina prvočísel . Pokud jsou pro některé prvočíslo splněny následující podmínky : ${\mathcal {J}}$ $q$

$q-1$ je číslo bez čtverců
všichni prvočíslí dělitelé patří do množiny $q-1$ ${\mathcal {J}}$

se pak nazývá euklidovské prvočíslo s ohledem na množinu . $q$ ${\mathcal {J}}$

Sada "počátečních" prvočísel

Pro dané číslo sestrojíme množinu tak, že součin všech euklidovských prvočísel vzhledem k této množině bude větší než . Vyberme co nejmenší . $n$ ${\mathcal {J}}={\mathcal {J}}(n)$ ${\sqrt n}$ ${\mathcal {J}}(n)$

Prvky této množiny se budou nazývat množina „počátečních“ prvočísel. $p$

Indq ( x)

Pojďme si představit nějaké číslo . Nechť je jeho primitivní kořen . Pak musí být splněna následující podmínka: $Ind_{q}=Ind_{q}(x)$ ${\displaystyle t_{q))$

$x\equiv {t_{q}}^{Ind_{q}(x)}\mod q$ ,

kde . $(x,q)=1$

Poznámka : Protoževolíme nejmenší nezáporné číslo. $Ind_{q}(x)$

Jacobiho součet

Jacobiho součet je součet v následujícím tvaru:

$J_{a,b}={\sum }{\left({\frac {x}{\mathfrak {L}}}\right)}_{p}^{-a}{\left({ \frac {1-x}{\mathfrak {L}}}\right)}_{p}^{-b}$ ,

kde součet je nad všemi sadami coset pro in , kromě těch, které se rovnají . $X$ $\mathbf {Z} [\zeta _{q}]/{\mathfrak {L}}$ $0,1\mod {\mathfrak {L}}$

Klíčová lemmata

Hlavní lemmata [2] použitá při dokazování správnosti algoritmu:

Lemma 1.

Primární ideály , ležící nad hlavním ideálem , jsou: $\mathbf {Z} [\zeta _{q}]$ $(q)$

{\mathfrak {L}}_{i}=(q,h_{i}(\zeta _{q}))

pro všechny

i=1..g~.

Lemma 2.

Nechte a mějte pořádek ve skupině . Vezměme si . Také kde je polynom pro každý . Předpokládáme, že ideály If je prvočíslo , pak v : $n\geq 2$ $F$ $(\mathbf {Z} /p)^{*}$ $g=(p-1)/f$ $\Phi _{p}(x)\equiv \prod _{i=1}^{g}h_{i}(x)\mod n~,$ $h_{i}(x)$ $\mathbf {Z} [x]$ $F$ ${\mathfrak {A}}_{i}=(n,h_{i}(\zeta _{q}))~.$ $r$ $n$ $\mathbf {Z} [\zeta _{q}]$ $(r)=\prod _{i=1}^{g}(r,{\mathfrak {A}}_{i})~,$

a každý dělitelný nějakým prvotním ideálem lží nad

(r,{\mathfrak {A}}_{i})

\mathbf {Z} [\zeta _{q}]

(r)~.

Lemma 3.

Vezměme také prvky , které spolu a s ohledem na sebe navzájem souvisí . $p>2$ $\alpha ,~\gamma \in \mathbf {Q} (\zeta _{q})$ $\lambda$ $\left({\frac {\alpha }{\gamma }}\right)_{p}=~\left({\frac {\gamma }{\alpha }}\right)_{p}( \alpha ,\gamma )_{\lambda }~.$

${\displaystyle (\cdot ,\cdot )_{\lambda ))$ je Hilbertův symbol .

Lemma 4. Pokud , pak

\alpha \equiv 1\mod \lambda ^{i},~\gamma \equiv 1\mod \lambda ^{j},~i+j\geq p+1

(\alpha ,\gamma )_{\lambda }=1~.

Lemma 5.

Vybíráme takové, že . Předpokládejme : to je nebo . $a,~b\in \mathbf {Z}$ $ab(a+b)\not \equiv 0\mod p$ $u\in \mathbf {Z}$ $\theta _{a,b}(u)=\left[{\frac {a+b}{p}}{u}\right]-\left[{\frac {a}{p}} {u}\right]-\left[{\frac {b}{p}}{u}\right],$ $\theta _{a,b}(u)=0$ $jeden$

Pak

J_{a,b}({\mathfrak {L)))=\prod _{u=1}^{p-1}{\sigma _{u))^{-1}({\mathfrak {A)))^{\theta _{a,b}(u)}~.

Lemma 6. [3] .

Pro všechny $a,~b\in \mathbf {Z} :$

-J_{a,b}({\mathfrak {L)))=1\mod {\lambda }^{2}~.

Lemma 7.

Pokud , pak existují takové , že a $p>2$ $a,b\in \mathbf {Z} ~,$ $ab(a+b)\not \equiv 0\mod p$

{\hat {\theta }}_{a,b}\doteq \sum _{u=1}^{p-1}\theta _{a,b}(u)\cdot u^{- 1}\ne \equiv 0~\mod ~p~,

kde je inverzní prvek k

u^{-1}

u\mod p~.

Lemma (Extrakce).

Dovolit být ideály v takové, že a nechť je konjugovat primární ideály dělení resp. Ať takové existuje . Pak pro všechny platí: ${\mathfrak {A}}~,~{\mathfrak {A}}_{1}$ $\mathbf {Z} [\zeta _{q}]$ $p\nmid N{\mathfrak {A}}=N{\mathfrak {A}}_{1}$ ${\mathfrak {R}}~,~{\mathfrak {R}}_{1}$ ${\mathfrak {A}}~,~{\mathfrak {A}}_{1}$ $\gamma \in \mathbf {Z} [\zeta _{q}]~,$ $\left\langle {\frac {\gamma }{\mathfrak {A}}}\right\rangle _{p}\neq 0,\neq 1$ $\alpha _{1}\in \mathbf {Z} [\zeta _{q}]$

${\left\langle {\frac {\gamma }{\mathfrak {A))}\right\rangle }_{p}^{m}={\left\langle {\frac {\alpha _{ 1}}{{\mathfrak {A}}_{1}}}\right\rangle _{p}}$

a proto

${\left\langle {\frac {\gamma }{\mathfrak {R))}\right\rangle }_{p}^{m}={\left\langle {\frac {\alpha _{ 1}}{{\mathfrak {R}}_{1}}}\right\rangle _{p}}~.$

Myšlenka algoritmu

Pokud je složené číslo, pak má nějakého dělitele . Pro kontrolu jednoduchosti hledáme toto . $n$ $r$ $r\neq 1~,r\neq n$

Pokud známe hodnoty pro každý pár , pak pomocí čínské věty o zbytku můžeme najít . Každý pár je vybrán následovně: , a je prvočíslo euklidovské číslo relativně takové, že $Ind_{q}(r)\mod p$ $p,q$ $r$ $p,q$ $p\in {\mathcal {J}}(n)$ $q$ ${\mathcal {J}}(n)$ $p|q-1~.$

Algoritmus vyjmenuje všechny možné hodnoty pro všechny na základě skutečnosti, že je známa pouze jedna $Ind_{q}(r)\mod p$ $q$ $q~.$

Algoritmus

Vstup: celé číslo n > 1. A. Krok přípravy

1. Vypočítejte nejmenší kladné číslo bez čtverců takové, že: . $f(n)$ $\prod _{q-1|f(n)}^{q~prime}q>{\sqrt {n))$

Pojďme definovat množinu "počátečních" prvočísel, která jsou děliteli . Říkáme tomu euklidovské prvočíslo, jestliže prvočíslo a $f(n)$ $q$ $q$ $q-1|f(n)$

2. Zkontrolujeme, zda je dělitelné nějakým "počátečním" nebo euklidovským prvočíslem. Pokud existuje dělitel a není roven , pak deklarujeme složený a přerušíme algoritmus. Jinak vypočítáme nejmenší kladný primitivní kořen pro každé euklidovské prvočíslo . $n$ $n$ $n$ ${\displaystyle t_{q))$ $q$

3. Pro každé „počáteční“ prvočíslo najdeme čísla taková, že: $p>2$ $a,~b$

$0<a,b<p$ ,

$a+b\equiv 0~mod~p$ ,

${\hat {\theta }}_{a,b}=\sum _{u=1}^{p-1}\theta _{a,b}(u)\cdot u^{-1 }\equiv 0~\mod ~p~.$

Pro přijetí . $p=2$ $a=b={\hat {\theta }}_{a,b}=1$

4. Pro každé "počáteční" a euklidovská prvočísla, abychom stanovili prvočíslo : ${p|q-1}$

${\mathfrak {L}}_{q}=(q,\zeta _{q}-t_{q}^{(q-1)/p})$ ,

kam patří a je kořenem jednoty . $q$ ${\mathsf {Z}}[\zeta _{q}]$ ${\zeta _{q}}=e^{2\pi i/p}$

Vypočítejte Jacobiho součet $J_{p}(q)\in \mathbf {Q} (\zeta _{q})~:$

pokud , $p=2:~J_{p}(q)=-q$

-li $p>2:~J_{p}(q)=-J_{a,b}({\mathfrak {L))_{q})=-\sum _{x=2}^{q- 1}{\left({\frac {x}{{\mathfrak {L}}_{q}}}\right)}_{p}^{-a}{\left({\frac {1-x }{{\mathfrak {L}}_{q}}}\right)}_{p}^{-b}.$

B. Krok výpočtu

1. Pro každé „počáteční“ prvočíslo najděte gcd v pro a množiny , kde přechází přes všechny hodnoty euklidovských prvočísel a , a přechází přes všechny hodnoty z Gal . Pak buď učiníme rozhodnutí o tom, co je kompozit, nebo postavíme správný ideál v kruhu a také najdeme čísla a taková , že: $p$ $\mathbf {Q} (\zeta _{q})$ $n$ $\sigma J_{p}(q)$ $q$ $p|q-1$ $\sigma$ $(\mathbf {Q} (\zeta _{q})/\mathbf {Q} )$ $n$ ${\mathfrak {A}}$ $\mathbf {Z} [\zeta _{q}]$ $s$ $j(\sigma ,q)$ $1\leq j(\sigma ,q)\leq p$

$(\sigma J_{p}(q))^{(n^{f}-1)/{p^{s}}}\equiv {\zeta _{q}}^{j(\sigma ,q) }~\mod ~{\mathfrak {A}}$ ,

${\displaystyle p\nmid {(n^{f}-1)/{p^{s))))$ nebo někde ${\zeta _{q}}^{j(\sigma ,q)}\neq 1$ $f=n~\mod ~p~.$

2. Pro každé „počáteční“ prvočíslo uděláme následující: pokud pro některé , pak vezměte . V tomto klíči sestrojíme čísla pro všechny , a to tak, že: $p$ $j(\sigma _{0},q_{0})\neq p$ $\gamma =\sigma _{0}J_{p}(q_{0})$ $m(\sigma ,q)$ $\sigma ,q$ $0\leq m(\sigma ,q)\leq p-1$

$(\gamma ^{(n^{f}-1)/{p^{s))})^{m(\sigma ,q)}\equiv (\sigma J_{p}(q)) ^{(n^{f}-1)/{p^{s}}}\mod ~{\mathfrak {A}}.$

Pokud pro všechny , přijímáme . $j(\sigma ,q)~=~p$ $m(\sigma ,q)~=~0$

C. Konsolidační krok

Udělejme kroky 1-4 pro všechny přírodní $k~,1\leq k\leq f(n).$

1. Pro každou počítáme podle čínské věty o zbytku počítáme čísla : $q>2$ $I(k,q)$

$I(k,q)=k({\hat {\theta }}_{a,b}}^{-1}\sum _{j=1}^{p-1}j\cdot m ({\sigma _{j}}^{-1},q)\mod p~,$

na všelijaké věci . Předpokládejme to také $p$ $p|q-1$ $I(k,2)=1~.$

2. Pro každý vypočítáme nejmenší celé číslo, kladné číslo $q$ $r(k,q)\equiv {t_{q))^{I(k,q)}\mod q.$

3. Pomocí čínské věty o zbytku vypočítejte nejmenší kladné číslo takové, že pro každé $r(k)$ $r(k)\equiv r(k,q)\mod q$ $q~.$

4. Jestliže , pak deklarujeme kompozitní. V opačném případě přejdeme na další $r(k)\neq 1~,~r(k)\neq n~,r(k)|n$ $n$ $k~.$

5. Prohlašujeme jednoduché. $n$

Hodnocení obtížnosti

Odhad doby provádění algoritmu vyplývá z následujících vět [2] :

Věta 1.

U hodnot výše uvedený algoritmus správně určuje, zda je prvočíslo nebo složené v čase . A platí následující odhady: pro jednoduché $n>1$ $n$ $T(n)$ $f(n)\leq T(n)~,$ $n~,$

T(n)\leq f^{c_{1}}(n)~,

pro všechny hodnoty Kde je kladná, vypočtená konstanta.

n~.

c_{1}

Věta 2.

Existují kladné, vypočítatelné konstanty takové, že pro všechny ${\displaystyle c_{2},~c_{3))$ $n>100~:$

(\ln(n))^{c_{2}\ln \ln \ln(n)}<f(n)<(\ln(n))^{c_{3}\ln \ln \ ln(n)}

Implementace softwaru

UBASIC poskytuje implementaci algoritmu nazvaného APRT-CLE (APR Test CL extended)
factoring applet používá algoritmus APR-CL za určitých podmínek
Pari/GP podmíněné použití APR-CL v implementaci isprime().
mpz_aprcl je implementace s otevřeným zdrojovým kódem . Používá C+GMP.

Poznámky

↑ Stewart, 2015 .
↑ 1 2 Adleman, Pomerance, Rumely, 1983 .
↑ K. Iwasawa. Poznámka k jacobi sum // Symposia Math. - 1975. - S. 447-459 .

Reference

Ian Stewart. Největší matematické problémy. — M. : Alpina literatura faktu, 2015. — 460 s. - ISBN 978-5-91671-318-3 .
Leonard M. Adleman, Carl Pomerance a Robert S. Rumely. [1] (anglicky) = O rozlišování prvočísel od složených čísel. - 1983. - S. 7-25 .