Nightingale-Strassen 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 3 januari 2022; kontroller kräver 4 redigeringar .

Nightingale-Strassen-testet är ett probabilistiskt primattest som upptäcktes på 1970-talet av Robert Martin Nightingale tillsammans med Volker Strassen. [1] Testet avgör alltid korrekt att ett primtal är primtal, men för sammansatta tal med viss sannolikhet kan det ge ett felaktigt svar. Den största fördelen med testet är att det, till skillnad från Fermats test , känner igen Carmichael-tal som sammansatta.

Historik

På 1600-talet bevisade Fermat ett uttalande som senare kallades Fermats lilla sats , som fungerar som grunden för Fermats primatitetstest :

Om n är primtal och a inte är delbart med n , då .

a^{n-1} \equiv 1\pmod{n}

Denna kontroll för ett givet n kräver inte mycket beräkning, men det omvända är inte sant. Det finns alltså Carmichael-tal, som är sammansatta, för vilka påståendet som ges i Fermats lilla teorem gäller för alla coprime-heltal med ett givet tal. 1994 visade det sig att det finns oändligt många sådana siffror. [2] I samband med den upptäckta bristen i Fermat-testet har problemet med att öka tillförlitligheten av probabilistiska tester blivit aktuellt. Lehmann var den första som föreslog ett test som sållar bort Carmichael-siffror som sammansatta. Denna brist saknas också i Solovey-Strassen- och Miller-Rabin-testerna på grund av ett starkare bortfallskriterium än Fermats lilla teorem. Oberoende av varandra bevisade D. Lemaire 1976 och R. Nightingale tillsammans med F. Strassen 1977 att det inte finns någon analog till Carmichael-tal, som är sammansatta och samtidigt Euler pseudosimple. [3] På grundval av detta föreslogs Solovay-Strassen-testet för primat, det publicerades 1977, tillägg till det 1978.

Motivering

Solovay-Strassen-testet är baserat på Fermats lilla teorem och Jacobi-symbolens egenskaper [4] :

Om n är ett udda sammansatt tal , överstiger inte antalet heltal a som är coprime till n och mindre än n som uppfyller jämförelsen . $\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ ${\frac {n}{2))$

Sammansatta tal n som uppfyller denna jämförelse kallas Euler-Jacobi pseudoprimer i basen a .

Bevis [5]

Låt oss bevisa att jämförelsen är nödvändig och tillräcklig för att talet n ska vara primtal. $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

Nödvändighet följer av Eulers kriterium för Legendre-symbolen . För att bevisa tillräckligheten använder vi motsägelsemetoden. Antag att n är sammansatt och samtidigt görs jämförelse för Detta innebär att vi får att n är ett Carmichael-tal, så var är ett primtal i = 1,2, ...k

\forall a\in \mathbf {Z_{n}}

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

a^{n-1}=(a^{(n-1)/2})^{2}=\left({\frac {a}{n}}\right)^{2}

\left({\frac {a}{n}}\right)^{2}=1

a^{n-1}=1(modn)

{\displaystyle n=p_{1}p_{2}..p_{k))

{\displaystyle p_{i))

Betrakta b sådan att Låt oss hitta ett sådant a att: Sådant existerar enligt den kinesiska restsatsen och tillhör , eftersom det är coprime till n . Därav motsägelsen med att So vårt antagande att n är sammansatt är falskt.

\left({\frac {b}{p_{1}}}\right)=-1(modn)

a={\begin{cases}b(mod{p_{1))),&{\mbox{if }}i{\mbox{= 1}}\\1(mod{p_{i}} ),&{\mbox{if }}i{\mbox{ = 2,...,k}}\end{cases}}

Z_{n}

\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_ {2}}}\right)....\left({\frac {a}{p_{k}}}\right)=\left({\frac {a}{p_{1}}}\right )=\left({\frac {b}{p_{1}}}\right)=-1

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

\left({\frac {a}{n}}\right)=-1

a^{(n-1)/2}\equiv \ -1(modn)

a^{(n-1)/2}\equiv \ -1(modp_{1})

a^{(n-1)/2}\equiv \ -1(modp_{2})

a\equiv \ 1(modp_{i})

Beviset på att antalet sådana tal inte överstiger n/2 kan hittas i vilken lärobok som helst om talteoretiska algoritmer. [fyra]

Solovay-Strassen-algoritmen

Solovay-Strassen-algoritmen [6] parametreras av antalet rundor k . I varje omgång väljs ett nummer a < n slumpmässigt . Om gcd ( a , n ) > 1, så bestäms det att n är sammansatt. I annat fall kontrolleras jämförelsens giltighet . Om det inte är uppfyllt, så fattas ett beslut att n är sammansatt. Om denna jämförelse håller, då är vittnen n prime . Sedan väljs ett annat slumpmässigt a och proceduren upprepas. Efter att ha hittat k primitetsvittnen i k omgångar dras slutsatsen att n är ett primtal med sannolikhet . $\textstyle a^{(n-1)/2}\equiv \left({a \over n}\right){\pmod {n))$ ${\displaystyle \textstyle 1-2^{-k))$

I pseudokod kan algoritmen skrivas enligt följande:

Inmatning : > 2, testa udda naturligt tal; , en parameter som bestämmer testets noggrannhet. Output : composite , betyder exakt sammansatt; förmodligen prime betyder att det förmodligen är prime.

n

k

n

n

för i = 1, 2, ..., : = slumpmässigt heltal från 2 till , inklusive; om gcd (a, n) > 1, då : print , som är sammansatt, och stoppa . if , då : utdata som är en sammansatt , och stoppa .

k

a

n-1

n

a^{(n-1)/2}\not \equiv \left({a \over n}\right){\pmod {n))

n

annars härleda , som är primtal med sannolikhet , och sluta .

n

{\displaystyle \textstyle 1-2^{-k))

Ett exempel på tillämpningen av algoritmen

Låt oss kontrollera talet n = 19 för enkelhetens skull. Vi väljer noggrannhetsparametern k = 2.

k = 1 Vi väljer ett slumptal a = 11; 2 < a < n - 1 Kontrollera villkoret gcd(a,n)>1 gcd(11,19)=1; sedan kontrollerar vi jämförelsen . Vi fick det, därför fortsätter vi till nästa iteration

\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

r=\left({\frac {a}{n}}\right)=\left({\frac {11}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=11^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

k = 2 Vi väljer ett slumptal a = 5; 2 < a < n - 1 Kontrollera villkoret gcd(a,n)>1 gcd(5,19)=1; så vi kontrollerar jämförelsen och detta var den sista iterationen, därför drar vi slutsatsen att 19 är ett primtal med en sannolikhet

\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

r=\left({\frac {a}{n}}\right)=\left({\frac {5}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=5^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

1-2^{-2}

Beräkningskomplexitet och noggrannhet

Noggrannhet jämfört med andra probabilistiska primatitetstester (här är k antalet oberoende omgångar)

testnamn	sannolikhet ( att talet är sammansatt ) [7]	anteckningar
Odla	$2^{-k}$	känner inte igen Carmichael-nummer som sammansatta
Lehmann	$2^{-k}$
Nightingale - Strassen	$2^{-k}$

Den teoretiska komplexiteten för beräkningar av alla tester som anges i tabellen uppskattas till . [3] $O(\log^3n)$
Algoritmen kräver operationer på långa heltal . [ett] $O(k\log _{2}m)$
Vid implementering av algoritmen, för att minska beräkningskomplexiteten, väljs talen a från intervallet 0 < a < c < n , där c är en konstant lika med det maximalt möjliga värdet av ett naturligt tal som passar i ett processorregister. [6]

Applikation

Probabilistiska tester används i system baserade på faktoriseringsproblemet , såsom RSA eller Rabins schema . Men i praktiken är graden av tillförlitlighet för Solovey-Strassen-testet inte tillräcklig, utan istället används Miller-Rabin-testet . Dessutom, med hjälp av kombinerade algoritmer som trial division och Miller-Rabin-testet, med rätt val av parametrar, kan du få bättre resultat än att använda varje test separat. [7]

Testa förbättring

2005, vid den internationella konferensen Bit+ "Informational Technologies -2005" föreslog A. A. Balabanov, A. F. Agafonov, V. A. Ryku ett moderniserat Solovay-Strassen-test. Nightingale-Strassen-testet är baserat på att beräkna Jacobi-symbolen, vilket tar tid motsvarande . Tanken med förbättring är att, i enlighet med Gaussisk kvadratisk reciprocitetssats , gå till beräkningen av värdet som är det reciproka för Jacobi-symbolen, vilket är en enklare procedur. [8] . $\log _{2}n$ $\left({\frac {n}{a}}\right)$

Se även

Pseudoprime

Anteckningar

↑ 1 2 Solovay, Robert M. och Volker Strassen. Ett snabbt Monte-Carlo-test för primalitet // SIAM Journal on Computing : journal. - 1977, inlämnad 1974. - Vol. 6 , nr. 1 . - S. 84-85 . - doi : 10.1137/0206006 .
↑ WR Alford, A. Granville, C. Pomerance. Det finns oändligt många Carmichael Numbers // Annals of Mathematics : journal . - 1994. - Vol. 139 . - s. 703-722 . - doi : 10.2307/2118576 . Arkiverad från originalet den 4 maj 2012.
↑ 1 2 Cheryomushkin, 2001 , sid. 48.
↑ 1 2 Nesterenko, 2011 , sid. 82.
↑ N.Yu. Gyllene . Föreläsningar om datoralgebra. Föreläsning 6. Carmichaels sats Näktergal - Strassen test. Arkiverad 4 november 2014 på Wayback Machine
↑ 1 2 Nesterenko, 2011 , sid. 84.
↑ 1 2 B. Schneier Tillämpad kryptografi - M. : TRIUMPH, 2002. — 11 kap.
↑ Balabanov A. A., Agafonov A. F., Ryku V. A. Algoritm för snabb nyckelgenerering i RSA-krypteringssystemet. Arkivexemplar daterad 5 november 2014 på Wayback Machine - Bulletin of Scientific and Technical Development, 2009 nr 7(23). - S. 11.

Litteratur

Koblitz N. En kurs i talteori och kryptografi . - 2:a. - M . : TVP Scientific Publishing House, 2001. - S. 149 - 160. - 254 sid. — ISBN 5-94057-103-4 .
Nesterenko A. Introduktion till modern kryptografi Talteoretiska algoritmer . - 2011. - S. 79 - 90. - 190 sid. - ISBN 978-5-94506-320-4 .
Cheremushkin AV Föreläsningar om aritmetiska algoritmer i kryptografi . - M. : MTSNMO , 2001. - S. 42 - 59. - 104 sid. — ISBN 5-94057-060-7 . Arkiverad 31 maj 2013 på Wayback Machine
Salomaa A. Offentlig nyckelkryptering / Per. från engelska. I.A. Vikhlyantsev. - M. : Mir, 1995. - S. 176 - 184. - 318 sid. — ISBN 5-03-001991-X . Arkiverad 19 november 2011 på Wayback Machine

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm