Primeco-testo: Malsamoj inter versioj
| [kontrolita revizio] | [kontrolita revizio] |
Enhavo forigita Enhavo aldonita
KuBOT (diskuto | kontribuoj) e Roboto: anstataŭigo de "Ŝablono:El" per "Ŝablono:EL" (laŭ VP:AA); kosmetikaj ŝanĝoj |
e plibonigadeto per AWB |
||
Linio 42:
Se la [[ĝeneraligita Rimana hipotezo]] estas alprenita, la [[primeca provo de Miller-Rabin]] povas esti ŝanĝita en determinisman version kun tempo ''[[granda O|Õ]]((log n)<sup>4</sup>)''. En praktiko, ĉi tiu algoritmo estas pli malrapida ol la alia du por ampleksoj de nombroj kiuj povas esti prilaboritaj per la ajna.
La [[primeca provo AKS]], estas pruvita al ruliĝi en ''Õ((log n)<sup>12</sup>)'', poste plibonigita al ''Õ((log n)<sup>6</sup>)'' <ref>
<!--
== (Kompliko, Komplekseco) ==
Linio 58:
Certaj nombro-teoriaj manieroj ekzisti por (testante, testado) ĉu nombro estas primo, tiaj la [[_Lucas_-_Lehmer_ provo]] kaj [[_Proth_'s teoremo|_Proth_'s provo]]. Ĉi tiuj testoj tipe postuli faktorigo de ''n'' + 1, ''n'' − 1, aŭ simila kvanto, kiu signifas ke ili estas neutila por ĝenerala-celo (primeco, plejparte) (testante, testado), sed ili estas ofte sufiĉe pova kiam la testita nombro ''n'' estas sciata al havi speciala (formo, formi).
La _Lucas_-_Lehmer_ provo fidas sur la fakto (tiu, ke, kiu) la [[multiplika (mendi, ordo)]] de nombro ''a'' module ''n'' estas ''n'' − 1 por primo ''n'' kiam ''a'' estas [[primitiva radiko module n]]. Se ni povas montri ''a'' estas primitivo por ''n'', ni povas montri ''n'' estas primo.
== Vidu ankaŭ ==
Linio 69:
== Eksteraj ligiloj ==
{{EL}} Manindra Agrawal, Neeraj Kayal, Nitin Saxena], ''[http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf Primoj estas en P]'', Analoj de Matematiko 160 (2004), ne. 2, pp.
{{EL}} [http://cr.yp.to/primetests.html Distingo de primoj de komponigitaj nombroj], D.J. Bernstein
{{EL}} [http://primes.utm.edu/ La primaj paĝoj]
| |||