Adleman-Pomerans-Rumeli teszt

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. február 20-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Az Adlemann-Pomeranz-Rumeli teszt (vagy Adleman-Pomeranz - Rumeli teszt, APR teszt ) az eddigi leghatékonyabb , determinisztikus és feltétel nélküli primalitásteszt , amelyet 1983-ban fejlesztettek ki. Kutatói tiszteletére nevezték el - Leonard Adleman , Karl Pomerans és Robert Roumeli . Az algoritmus ciklomatikus mezőkben tartalmaz aritmetikát .

Ezt követően Henry Cohen és Hendrik Lenstra javította az algoritmust APR-CL- re , amelynek futásideje tetszőleges számra úgy számítható ki , hogy , ahol valamilyen számított állandó. $n$ $O((\ln n)^{c\,\ln \,\ln \,\ln n})$ $c$

Történelem

1980-ig az összes ismert primalitástesztelő algoritmus esetében, kivéve a valószínűségi és a nem bizonyított algoritmusokat, az algoritmus időbeli összetettsége exponenciális volt. 1983-ban azonban kifejlesztettek egy algoritmust, amely közel van a P - osztályhoz . Szigorúan véve az algoritmus nem tartozik ebbe az osztályba, azonban a lassan növekvő komplexitás lehetővé teszi az algoritmus gyakorlati alkalmazását. $O((\ln n)^{c\,\ln \,\ln \,\ln n})$

Például egy szám esetén - googolplex , $n$ $\ln \ln \ln n\kb. 5{,}44282$

A régi vicc így szól:
"Bizonyított , hogy a végtelenségig elmegy, de még soha senki nem látta, hogy megcsinálja." $\log \log n$ Ian Stewart

Kulcsfogalmak

Euklideszi prím

Legyen valamilyen véges prímkészlet . Ha valamelyik prímszámra teljesülnek a következő feltételek : ${\mathcal {J}}$ $q$

$q-1$ egy négyzet nélküli szám
minden prímosztó a halmazhoz tartozik $q-1$ ${\mathcal {J}}$

ekkor euklideszi prímnek nevezzük a halmazhoz képest . $q$ ${\mathcal {J}}$

"Kezdő" prímek halmaza

Adott számhoz olyan halmazt készítünk , hogy az összes euklideszi prím szorzata ehhez a halmazhoz képest nagyobb legyen, mint . Válasszuk a lehető legkisebbet . $n$ ${\mathcal {J}}={\mathcal {J}}(n)$ ${\sqrt n}$ ${\mathcal {J}}(n)$

Ennek a halmaznak az elemeit "kezdeti" prímszámok halmazának nevezzük. $p$

Indq ( x)

Mutassunk be néhány számot . Legyen a primitív gyöke . Ekkor a következő feltételnek kell teljesülnie: $Ind_{q}=Ind_{q}(x)$ ${\displaystyle t_{q))$

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

ahol . $(x,q)=1$

Megjegyzés : Mivela legkisebb, nem negatív számot választjuk. $Ind_{q}(x)$

Jacobi sum

A Jacobi-összeg a következő formájú összeg:

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

ahol az összegzés az összes kosethalmazra vonatkozik -ben , kivéve azokat, amelyek egyenlőek . $x$ $\mathbf {Z} [\zeta _{q}]/{\mathfrak {L}}$ $0,1\mod {\mathfrak {L}}$

Kulcslemmák

Az algoritmus helyességének bizonyítására használt fő lemmák [2] :

1. lemma.

A főideálok legfőbb ideáljai , amelyek a főideál felett állnak, a következők: $\mathbf {Z} [\zeta _{q}]$ $(q)$

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

mindenkinek

i=1..g~.

2. lemma.

Legyen rend a csoportban . Vegyük . Valamint hol van egy polinom az egyes . Feltételezzük, hogy az If ideál egy prímosztó , akkor a következőben: $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})~,$

és mindegyik osztható a hazugság valamilyen elsődleges ideáljával

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

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

(r)~.

3. lemma.

Vegyünk egymáshoz és egymáshoz viszonyított elemeket is . $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 ))$ a Hilbert szimbólum .

4. lemma. Ha , akkor

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

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

5. lemma.

Mi olyat választunk . Tegyük fel: vagyis vagy . $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}\jobbra]-\balra[{\frac {b}{p}}{u}\jobbra],$ $\theta _{a,b}(u)=0$ $egy$

Akkor

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

Lemma 6. [3] .

Mindenkinek $a,~b\in \mathbf {Z} :$

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

7. lemma.

Ha , akkor létezik olyan, hogy és $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~,

hol van az inverz elem

u^{-1}

u\mod p~.

Lemma (kivonatok).

Legyenek ideálok úgy, hogy és legyenek konjugált elsődleges ideálok , amelyek rendre osztva. Legyenek ilyenek . Akkor mindenre igaz: ${\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}}$

és ezért

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

Az algoritmus ötlete

Ha összetett szám, akkor van valami osztója . Az egyszerűség kedvéért ezt keressük . $n$ $r$ $r\neq 1~,r\neq n$

Ha ismerjük az egyes párok értékeit , akkor a kínai maradéktétel segítségével megtalálhatjuk a . Mindegyik pár a következőképpen van kiválasztva: , és egy prím euklideszi szám, amely relatíve olyan, hogy $Ind_{q}(r)\mod p$ $p,q$ $r$ $p,q$ $p\in {\mathcal {J}}(n)$ $q$ ${\mathcal {J}}(n)$ $p|q-1~.$

Az algoritmus az összes lehetséges értéket felsorolja azon tény alapján, hogy csak egy ismert $Ind_{q}(r)\mod p$ $q$ $q~.$

Algoritmus

Bemenet: egész n > 1. A. Előkészületi lépés

1. Számítsa ki a legkisebb pozitív négyzetmentes számot úgy, hogy: . $f(n)$ $\prod _{q-1|f(n)}^{q~prime}q>{\sqrt {n))$

Határozzuk meg a "kezdeti" prímszámok halmazát, amelyek osztói . Euklideszi prímnek nevezzük , ha a prím és $f(n)$ $q$ $q$ $q-1|f(n)$

2. Ellenőrizzük, hogy osztható -e bármely "kezdő" vagy euklideszi prímszámmal. Ha van osztó, és nem egyenlő -val, akkor összetettnek nyilvánítjuk és megszakítjuk az algoritmust. Egyébként minden euklideszi prímhez kiszámítjuk a legkisebb pozitív primitív gyöket . $n$ $n$ $n$ ${\displaystyle t_{q))$ $q$

3. Minden "kezdeti" prímszámhoz olyan számokat találunk , amelyek: $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~.$

Az elfogadásért . $p=2$ $a=b={\hat {\theta }}_{a,b}=1$

4. Minden "kezdő" és euklideszi prímszámra úgy, hogy rögzítsünk egy prímideált : ${p|q-1}$

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

ahol az egységhez tartozik és ez az egység gyökere . $q$ ${\mathsf {Z}}[\zeta _{q}]$ ${\zeta _{q}}=e^{2\pi i/p}$

Számítsd ki a Jacobi-összeget! $J_{p}(q)\in \mathbf {Q} (\zeta _{q})~:$

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

ha $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. Számítási lépés

1. Minden „kezdeti” prímszámhoz keresse meg a és a halmaz gcd - jét , ahol átfut az euklideszi prímek összes értékén, és , és a Gal összes értéken . Ezután vagy döntünk arról, hogy mi az összetett, vagy megépítjük a megfelelő ideált a ringben , és találunk olyan számokat és , hogy: $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))))$ vagy valahol hol ${\zeta _{q}}^{j(\sigma ,q)}\neq 1$ $f=n~\mod ~p~.$

2. Minden "kezdeti" prímszámnál a következőket tesszük: ha néhány esetén , akkor vegyük . Ebben a kulcsban számokat állítunk össze az összes számára , és úgy, hogy: $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}}.$

Ha mindenért , akkor elfogadjuk . $j(\sigma ,q)~=~p$ $m(\sigma ,q)~=~0$

C. Konszolidációs lépés

Végezzük el az 1-4. lépést minden természetesnél $k~,1\leq k\leq f(n).$

1. Mindegyikre a kínai maradéktétel alapján számítjuk ki a számokat : $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~,$

mindenféle dologra . Tegyük fel azt is $p$ $p|q-1$ $I(k,2)=1~.$

2. Mindegyikhez kiszámoljuk a legkisebb egész számot, egy pozitív számot $q$ $r(k,q)\equiv {t_{q))^{I(k,q)}\mod q.$

3. A kínai maradéktétel segítségével számítsa ki a legkisebb pozitív számot úgy, hogy mindegyikhez! $r(k)$ $r(k)\equiv r(k,q)\mod q$ $q~.$

4. Ha , akkor összetettnek nyilvánítjuk. Ellenkező esetben továbblépünk a következőre $r(k)\neq 1~,~r(k)\neq n~,r(k)|n$ $n$ $k~.$

5. Egyszerűnek nyilvánítjuk . $n$

Nehézségi fok

Az algoritmus végrehajtási idejének becslése a következő tételekből következik [2] :

1. tétel.

Az értékek esetében a fenti algoritmus helyesen határozza meg, hogy időben prím vagy összetett . És a következő becslések érvényesek: egyszerűre $n>1$ $n$ $T(n)$ $f(n)\leq T(n)~,$ $n~,$

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

minden értéknél ahol van egy pozitív, számított állandó.

n~.

c_{1}

2. tétel.

Vannak pozitív, kiszámítható állandók , amelyek mindenre vonatkoznak ${\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)}

Szoftver implementáció

Az UBASIC biztosítja az APRT -CLE (APR Test CL kiterjesztett) nevű algoritmus megvalósítását .
faktoring kisalkalmazás bizonyos feltételekkel az APR-CL algoritmust használja
Pari/GP feltételes APR-CL használata az isprime() implementációban.
Az mpz_aprcl egy nyílt forráskódú megvalósítás . C+GMP-t használ.

Jegyzetek

↑ Stewart, 2015 .
↑ 1 2 Adleman, Pomerance, Rumely, 1983 .
↑ K. Iwasawa. Megjegyzés a jacobi összegről // Symposia Math. - 1975. - S. 447-459 .

Hivatkozások

Ian Stewart. A legnagyobb matematikai feladatok. — M. : Alpina non-fiction, 2015. — 460 p. - ISBN 978-5-91671-318-3 .
Leonard M. Adleman, Carl Pomerance és Robert S. Rumely. [1] (angol) = A prímszámok és az összetett számok megkülönböztetéséről. - 1983. - P. 7-25 .