Adleman-Pomerans-Rumeli test

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 februari 2020; kontroller kräver 3 redigeringar .

Adlemann-Pomeranz-Rumeli-testet (eller Adleman-Pomeranz-Rumeli-testet, APR-testet ) är det mest [1] effektiva, deterministiska och ovillkorliga primalitetstestet hittills , utvecklat 1983. Uppkallad för att hedra sina forskare - Leonard Adleman , Karl Pomerans och Robert Roumeli . Algoritmen innehåller aritmetik i cyklomatiska fält .

Därefter förbättrades algoritmen av Henry Cohen och Hendrik Lenstra till APR-CL , vars körtid för vilket tal som helst kan beräknas som , där är någon beräknad konstant. $n$ $O((\ln n)^{c\,\ln \,\ln \,\ln n})$ $c$

Historik

Fram till 1980 var tidskomplexiteten för algoritmen exponentiell för alla kända primalitetstestningsalgoritmer, förutom probabilistiska och oprövade . Men 1983 utvecklades en algoritm som ligger nära P -klassen . Strängt taget tillhör algoritmen inte denna klass, men långsamt ökande komplexitet tillåter praktisk användning av algoritmen. $O((\ln n)^{c\,\ln \,\ln \,\ln n})$

Till exempel, för ett nummer - googolplex , $n$ $\ln \ln \ln n\approx 5{,}44282$

Det gamla skämtet lyder:
"Visade sig gå till oändligheten, men ingen har någonsin sett honom göra det." $\log \log n$ Ian Stewart

Nyckelbegrepp

Euklidisk prime

Låt det finnas någon ändlig uppsättning primtal . Om följande villkor är uppfyllda för något primtal : ${\mathcal {J}}$ $q$

$q-1$ är ett kvadratfritt tal
alla primtalare hör till mängden $q-1$ ${\mathcal {J}}$

kallas då ett euklidiskt primtal med avseende på mängden . $q$ ${\mathcal {J}}$

En uppsättning "initial" primtal

För ett givet tal konstruerar vi en mängd så att produkten av alla euklidiska primtal med avseende på denna mängd kommer att vara större än . Låt oss välja den minsta möjliga . $n$ ${\mathcal {J}}={\mathcal {J}}(n)$ ${\sqrt n}$ ${\mathcal {J}}(n)$

Elementen i denna uppsättning kommer att kallas uppsättningen av "initial" primtal. $sid$

Indq ( x)

Låt oss presentera några nummer . Låt vara dess primitiva rot . Då måste följande villkor vara uppfyllt: $Ind_{q}=Ind_{q}(x)$ ${\displaystyle t_{q))$

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

var . $(x,q)=1$

Notera : Eftersomvi väljer det minsta icke-negativa talet. $Ind_{q}(x)$

Jacobi summa

En Jacobis summa är en summa av följande form:

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

där summeringen är över alla uppsättningar av coset för i , förutom de som är lika med . $x$ $\mathbf {Z} [\zeta _{q}]/{\mathfrak {L}}$ $0,1\mod {\mathfrak {L}}$

Nyckellemman

De viktigaste lemman [2] som används för att bevisa algoritmens riktighet:

Lemma 1.

De främsta idealen för , som ligger över huvudidealet , är: $\mathbf {Z} [\zeta _{q}]$ $(q)$

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

för alla

i=1..g~.

Lemma 2.

Låt och ha ordning och reda i gruppen . Låt oss ta . Också var är ett polynom i för varje . Vi antar att idealen If är en primtalare , då i : $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})~,$

och var och en delbar med något främsta ideal av lögner över

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

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

(r)~.

Lemma 3.

Låt oss också ta element i samordning med och med respekt för varandra. $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 ))$ är Hilbert-symbolen .

Lemma 4. Om , då

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

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

Lemma 5.

Vi väljer så att . För anta: det är eller . $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}\höger]-\vänster[{\frac {b}{p}}{u}\höger],$ $\theta _{a,b}(u)=0$ $ett$

Sedan

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

Lemma 6. [3] .

För alla $a,~b\in \mathbf {Z} :$

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

Lemma 7.

Om , så finns det sådana att och $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}\not \equiv 0~\mod ~p~,

var är det omvända elementet till

u^{-1}

u\mod p~.

Lemma (Utdrag).

Låt vara ideal i sådant och låt vara konjugera prime ideal dividera respektive. Låt sådant existera . Då är det sant för alla: ${\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}}$

och därför

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

Idén med algoritmen

Om är ett sammansatt tal, så har det någon divisor . För att kontrollera enkelheten letar vi efter denna . $n$ $r$ $r\neq 1~,r\neq n$

Om vi känner till värdena för varje par , så kan vi hitta den kinesiska restsatsen . Varje par väljs enligt följande: , och är ett euklidiskt primtal relativt sådant att $Ind_{q}(r)\mod p$ $p,q$ $r$ $p,q$ $p\in {\mathcal {J}}(n)$ $q$ ${\mathcal {J}}(n)$ $p|q-1~.$

Algoritmen räknar upp alla möjliga värden för alla , baserat på det faktum att endast ett är känt $Ind_{q}(r)\mod p$ $q$ $q~.$

Algoritm

Inmatning: heltal n > 1. A. Förberedelsesteg

1. Beräkna det minsta positiva kvadratfria talet , så att: . $f(n)$ $\prod _{q-1|f(n)}^{q~prime}q>{\sqrt {n))$

Låt oss definiera en uppsättning "initial" primtal som är delare av . Vi kallar det ett euklidiskt primtal om primtal och $f(n)$ $q$ $q$ $q-1|f(n)$

2. Låt oss kontrollera om det är delbart med något "initial" eller euklidiskt primtal. Om det finns en divisor och inte lika med , deklarerar vi sammansatt och avbryter algoritmen. Annars beräknar vi den minsta positiva primitiva roten för varje euklidiskt primtal . $n$ $n$ $n$ ${\displaystyle t_{q))$ $q$

3. För varje "initial" primtal hittar vi tal som: $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~.$

För att acceptera . $p=2$ $a=b={\hat {\theta }}_{a,b}=1$

4. För varje "initial" och euklidiskt primtal så att vi fixar ett primideal : ${p|q-1}$

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

där tillhör och är roten till enheten . $q$ ${\mathsf {Z}}[\zeta _{q}]$ ${\zeta _{q}}=e^{2\pi i/p}$

Beräkna Jacobis summa $J_{p}(q)\in \mathbf {Q} (\zeta _{q})~:$

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

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

B. Beräkningssteg

1. För varje "initial" primtal, hitta gcd i för och för mängden , där den löper över alla värden av euklidiska primtal, och , och kör över alla värden från Gal . Sedan fattar vi antingen ett beslut om vad som är sammansatt, eller så bygger vi det rätta idealet i ringen , och hittar även siffror och , så att: $sid$ $\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))))$ eller någonstans ${\zeta _{q}}^{j(\sigma ,q)}\neq 1$ $f=n~\mod ~p~.$

2. För varje "initial" primtal gör vi följande: om för några , ta sedan . I den här nyckeln konstruerar vi tal för alla och sådana att: $sid$ $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}}.$

Om för alla så accepterar vi . $j(\sigma ,q)~=~p$ $m(\sigma ,q)~=~0$

C. Konsolideringssteg

Låt oss göra steg 1-4 för alla naturliga $k~,1\leq k\leq f(n).$

1. För varje vi beräknar enligt den kinesiska restsatsen beräknar vi talen : $q>2$ $I(k,q)$

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

för alla möjliga saker . Låt oss också anta det $sid$ $p|q-1$ $I(k,2)=1~.$

2. För varje , beräknar vi det minsta heltal, ett positivt tal $q$ $r(k,q)\equiv {t_{q))^{I(k,q)}\mod q.$

3. Använd den kinesiska restsatsen och beräkna det minsta positiva talet så att för varje $r(k)$ $r(k)\equiv r(k,q)\mod q$ $q~.$

4. Om , deklarerar vi sammansatt. Annars går vi vidare till nästa $r(k)\neq 1~,~r(k)\neq n~,r(k)|n$ $n$ $k~.$

5. Vi förklarar enkel. $n$

Svårighetsgrad

Uppskattningen av exekveringstiden för algoritmen följer av följande satser [2] :

Sats 1.

För värden bestämmer ovanstående algoritm korrekt om det är prime eller sammansatt i tid . Och följande uppskattningar är giltiga: för enkelt $n>1$ $n$ $T(n)$ $f(n)\leq T(n)~,$ $n~,$

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

för alla värden Där finns en positiv, beräknad konstant.

n~.

c_{1}

Sats 2.

Det finns positiva, beräkningsbara konstanter som för alla ${\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)}

Programvaruimplementering

UBASIC tillhandahåller en implementering av algoritmen som kallas APRT-CLE (APR Test CL extended)
factoring-appleten använder APR-CL-algoritmen med vissa villkor
Pari/GP villkorad användning av APR-CL i isprime()-implementering.
mpz_aprcl är en implementering med öppen källkod . Använder C+GMP.

Anteckningar

↑ Stewart, 2015 .
↑ 1 2 Adleman, Pomerance, Rumely, 1983 .
↑ K. Iwasawa. En anteckning om jacobi sum // Symposia Math. - 1975. - S. 447-459 .

Referenser

Ian Stewart. De största matematiska problemen. — M. : Alpina facklitteratur, 2015. — 460 sid. - ISBN 978-5-91671-318-3 .
Leonard M. Adleman, Carl Pomerance och Robert S. Rumely. [1] (engelska) = Om att skilja primtal från sammansatta tal. - 1983. - S. 7-25 .