Share to:

Test pierwszości AKS

Test pierwszości AKS (lub test pierwszości Agrawal-Kayal-Saxena) – deterministyczny test pierwszości opublikowany przez Manindra Agrawal, Neeraj Kayal i Nitin Saxena z IIT Kanpur 6 sierpnia 2002 r. w artykule zatytułowanym PRIMES is in P. Za jego opracowanie autorzy zostali uhonorowani Nagrodą Gödla w 2006 r.

Algorytm ten stwierdza czy dana liczba jest pierwsza, czy złożona w czasie wielomianowym.

Znaczenie

AKS jest pierwszym opublikowanym algorytmem badającym czy dana liczba jest pierwsza, który jest wielomianowy (szybki), deterministyczny (jednoznaczny) i bezwarunkowy. Oznacza to, że maksymalny czas działania tego algorytmu można opisać funkcją wielomianową z liczby cyfr badanej liczby, pozwalającą udowodnić, że zawsze zwróci on poprawną odpowiedź (a nie tylko z pewnym prawdopodobieństwem), a jego działanie nie opiera się na żadnych nieudowodnionych hipotezach (takich jak np. hipoteza Riemanna).

Podstawa testu

Przy założeniu, że $n$ ≥2 jest liczbą całkowitą, $a$ jest również liczbą całkowitą względnie pierwszą z $n,$ test AKS opiera się na twierdzeniu, że równość:

(x-a)^{n}\equiv (x^{n}-a)\ (\operatorname {mod} \,n),

jest prawdziwa wtedy i tylko wtedy, gdy $n$ jest liczbą pierwszą. $x$ należy rozumieć jako formalny symbol (przestrzeń wielomianów). Równość ta jest uogólnieniem małego twierdzenia Fermata na wielomiany i można ją łatwo udowodnić korzystając z rozwinięcia:

(x-a)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}(-a)^{n-k}

i faktu że:

{n \choose k}\equiv 0\ (\operatorname {mod} \,n)

dla wszystkich $0<k<n,$ o ile $n$ jest liczbą pierwszą. Sama ta równość jest więc już testem pierwszości, ale jej sprawdzenie wymaga wykładniczego czasu. W teście AKS zamiast rozważać pełną wersję tej równości, sprawdza się ją modulo pewien wielomian $x^{r}-1.$ Oczywiście, równość dalej jest spełniana przez liczby pierwsze, ale mogą istnieć liczby złożone, które zaczynają ją spełniać. Kluczem jest więc znalezienie odpowiedniego $r$ i niewielkiego zbioru liczb A, tak żeby tylko liczby pierwsze spełniały ją dla wszystkich $a$ ze zbioru A.

Algorytm składa się z dwóch części. Pierwsza polega na znalezieniu odpowiedniej liczby pierwszej $r=kq+1,$ takiej że:

P(r-1)=q,

gdzie

P(x)

jest największym dzielnikiem pierwszym

x,

q\geqslant 4{\sqrt {r}}\log _{2}n,

n^{k}\not \equiv 1\ (\operatorname {mod} \,r).

W tej części niezbędne jest sprawdzenie, że $n$ nie dzieli się przez żadne $p\leqslant r.$ Jeśli się dzieli, algorytm kończy działanie pokazując, że $n$ jest liczbą złożoną.

W drugiej części przeprowadzana jest odpowiednia liczba testów w pierścieniu ilorazowym wielomianów $\mathbb {Z} _{n}[x]/(x^{r}-1).$ Każdy test polega na sprawdzeniu równości dwóch wielomianów:

jeśli

(x-a)^{n}\equiv (x^{n}-a)\ (\operatorname {mod} \,n,x^{r}-1)

dla wszystkich dodatnich $a,$ takich że:

a\leqslant 2{\sqrt {r}}\log _{2}n,

to $n$ jest liczbą pierwszą. W każdym innym przypadku jest liczbą złożoną.

Opis algorytmu wymagał uzupełniania o dwa elementy: dowód poprawności oraz ustalenie jego złożoności obliczeniowej. Zostało to zrealizowane przez pokazanie, że odpowiednie $r$ zawsze można znaleźć, ustalenie wielkości tego $r$ i udowodnienie, że testy przeprowadzone w drugiej części są wystarczające do stwierdzenia pierwszości $n.$

Ponieważ czas działania obu części zależy od wielkości $r,$ podanie górnego ograniczenia na $r$ wystarczyło do określenia złożoności algorytmu na $\mathrm {O} (\log ^{12+\epsilon }n)$ . To górne ograniczenie jest bardzo zgrubne – jeśli prawdziwe jest założenie o rozkładzie liczb pierwszych Sophie Germain, to złożoność algorytmu automatycznie maleje do $\mathrm {O} (\log ^{6+\epsilon }n).$

Bibliografia

Manindra Agrawal, Neeraj Kayal, Nitin Saxena, „PRIMES is in P”, Annals of Mathematics 160 (2004), no. 2, s. 781–793.

Teoria liczb

ogólne typy liczb

relacje

podzielność	dzielnik i wielokrotność cechy podzielności
zdefiniowane podzielnością	czynnik pierwszy względna pierwszość kongruencje liczby towarzyskie zaprzyjaźnione

działania

liczby pierwsze

podstawy	lemat Euklidesa liczby złożone
testy pierwszości	AKS APR cyklotomiczny ECPP Fermata Lucasa-Lehmera Millera-Rabina Solovaya-Strassena certyfikat pierwszości
sita	Eratostenesa Atkina
faktoryzacja	zasadnicze twierdzenie arytmetyki algorytmy Fermata rho Pollarda Shora GNFS metoda sita liczbowego sito kwadratowe
hipotezy	Gilbreatha Goldbacha słaba liczb pierwszych bliźniaczych Pólyi

równania
diofantyczne

liniowe	tożsamość Bézouta
kwadratowe	równanie Pitagorasa (trójek pitagorejskich) równanie Pella
wyższych stopni	równanie Fermata (wielkie twierdzenie Fermata) równanie Catalana (twierdzenie Mihăilescu)
układy równań	cegiełka Eulera prostopadłościan idealny
powiązane zagadnienia	dziesiąty problem Hilberta

twierdzenia
arytmetyki modularnej

inne zagadnienia

twierdzenia limitacyjne

pierwsze Gödla o niezupełności

Read other articles:

SV Juventus

Football clubSV JuventusFull nameSport Vereniging JuventusFounded1973GroundMunicipal StadiumBonaireCapacity3,000LeagueBonaire League2018–198th Home colours Away colours SV Juventus is a football team from Antriòl, Kralendijk on Bonaire in the Caribbean Netherlands, playing at the top level. The club was founded in 1973 as a split-off from SV Vitesse.[1] Squad Note: Flags indicate national team as defined under FIFA eligibility rules. Players may hold more than one non-FIFA national...

Malawi Adventist University

Private Christian university in Ntcheu, Malawi The topic of this article may not meet Wikipedia's notability guidelines for companies and organizations. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: Malawi Adventist University –...

مونيفا

Monevaمونيفا (بالإسبانية: Moneva)‏[1] مونيفا مونيفا تقسيم إداري البلد إسبانيا[2] المنطقة أراغون المسؤولون المقاطعة سرقسطة خصائص جغرافية إحداثيات 41°07′38″N 0°49′47″W / 41.1272282°N 0.8298211°W / 41.1272282; -0.8298211[3] [4] المساحة 61,40 كم² كم² الارتفاع 659 متر&#...

Rufus Hathaway

American physician and painter (1770–1822) Lady with Her Pets, 1790, Metropolitan Museum of Art Rufus Hathaway (1770–1822) was an American physician and folk art painter. He lived in southern Massachusetts, where he painted numerous portraits between 1790 and 1795.[1] He later studied medicine and established himself as a doctor at Duxbury.[2] Hathway was born in Freetown, Massachusetts, and was the eldest of six children born to Asa Hathaway and Mary Phillips;[1] ...

Gray Academy of Jewish Education

SchoolGray Academy ofbad EducatioLocation123 Doncaster St, Winnipeg, ManitobaInformationEstablished1997School boardWinnipeg Board of Jewish EducationPresidentBryan BorzykowskiHead of schoolLori BinderGradesNursery–12Enrollment490School fees$11,175 CADWebsitegrayacademy.ca The Gray Academy of Jewish Education is a pluralistic Jewish day school in Winnipeg, Manitoba, and the only K–12 Jewish day school in western Canada.[1] The trustee and policy-making body of the school is the Win...

Consulate General of France, Atlanta

Consulate General of France in AtlantaConsulat Général de France à AtlantaLocationBuckhead Tower at Lenox Square, Suite 567, 3399 Peachtree Road Atlanta GA 30326Coordinates33°45′18″N 84°23′24″W / 33.75500°N 84.39000°W / 33.75500; -84.39000Consul GeneralAnne-Laure DesjonquèresWebsiteatlanta.consulfrance.org/-english- The Consulate General of France in Atlanta is the French diplomatic outpost to the U.S Southeast. Its jurisdiction covers the states of Ala...

Ruta Provincial 1003 (Buenos Aires)

Ruta Provincial 1003 Buenos Aires, Argentina La RP 1003 al lado del Cementerio Santa Mónica, Libertad. Datos de la rutaIdentificador RP 1003 Tipo Ruta provincialLongitud 13 kmOtros datosPartidos Merlo MorónIntersecciones en Morón en LibertadOrientación • Este RP 17 en Morón (34°41′28.1″S 58°38′04.2″O / -34.691139, -58.634500) • Oeste RP 21 en Libertad (34°42′49.1″S 58°42′52.8″O / -34.713639, -58...

Bemby Gusti

Artikel ini perlu dikembangkan agar dapat memenuhi kriteria sebagai entri Wikipedia.Bantulah untuk mengembangkan artikel ini. Jika tidak dikembangkan, artikel ini akan dihapus. Bemby Gusti adalah seorang musikus dan komponis Indonesia. Filmografi Film Tahun Judul Dikreditkan sebagai Catatan Komponis 2006 Berbagi Suami Ya 2007 Quickie Express Ya 2008 Perempuan Punya Cerita Ya Radit dan Jani Ya Gara-Gara Bola Ya Takut: Faces of Fear Ya 2009 Pintu Terlarang Ya Meraih Mimpi Ya Heart-Break.com Ya ...

Raden Purwadi

Raden PurwadiInformasi pribadiLahir0 Juli 1965 (umur 58)Mempawah, Kalimantan BaratKebangsaanIndonesiaAlma materAkademi Kepolisian (1988)Karier militerPihak IndonesiaDinas/cabang Kepolisian Negara Republik IndonesiaMasa dinas1988—2023Pangkat Inspektur Jenderal PolisiNRP65070699SatuanReserseSunting kotak info • L • B Irjen. Pol. (Purn.) Drs. H. Raden Purwadi, S.H. (lahir Juli 1965) adalah seorang Purnawirawan Polri yang jabatan terakhirnya adalah Widyaiswara Utama...

Équipe du Togo de football à la Coupe d'Afrique des nations 2010

Cet article relate le parcours de l'équipe du Togo lors de la Coupe d'Afrique des nations 2010 organisée en Angola du 10 janvier 2010 au 31 janvier 2010. Effectif Liste des 23 donnée le 29 décembre 2009[1]. Statistiques arrêtées le 22 décembre 2009. Numéro / Nom Équipe actuelle Sél. Date de naissance J. Gardiens de but 16 Kossi Agassa FC Istres 46 (0) 2 juillet 1978 22 Baba Tchagouni Dijon Football Côte-d'Or 1 (0) 31 décembre 1990 1 Kodjovi Dodji Obilalé GSI Pontivy 5 (0) 8 octob...

Live Niguz

1995 single by OnyxLive NiguzSingle by Onyxfrom the album The Show and All We Got Iz Us B-sideKill Dem AllReleasedJuly 18, 1995 [1]Recorded1994StudioLGK Studios, Leonia, New JerseyGenrehardcore rap, East Coast hip hopLength3:31LabelDef JamRush Associated LabelsJMJ RecordsSongwriter(s)Fred ScruggsKirk JonesTyrone TaylorIsaac HayesProducer(s)Fredro StarrSticky FingazSonee SeezaOnyx singles chronology Shifftee (1993) Live Niguz (1995) Last Dayz (1995) Music videoLive Niguz on YouTube Live Ni...

Amiga demos

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (December 2022) (Learn how and when to remove this template message) This article needs additional citations for verification. Please help improve thi...

Lucifer (South Korean TV series)

2007 South Korean television series LuciferPromotional posterHangul마왕Hanja魔王Literal meaningDevilRevised RomanizationMawang GenreDramaMysteryRomanceWritten byKim Ji-wooDirected byPark Chan-hongStarringUhm Tae-woongJu Ji-hoonShin Min-aMusic byPark Hye-jiYoo Hye-joonCountry of originSouth KoreaOriginal languageKoreanNo. of episodes20ProductionExecutive producerLee Deok-geonRunning time70 minutesProduction companyOlive 9Original releaseNetworkKBS2Release21 March (2007-03-21) –...

Ghislaine Thesmar

Portrait de Ghislaine Thesmar par Serge Ivanoff, Paris, 1976. Ghislaine Thesmar (nascida em 1943) é uma bailarina e coreógrafa francesa. Thesmar nasceu em 1943 em Pequim, na China.[1] Foi casada com o colega bailarino e coreógrafo francês Pierre Lacotte de 1968 até à sua morte em 2023.[2] De 1972 a 1985, foi Étoile (dançarina principal) do Ballet da Ópera de Paris.[1] Referências ↑ a b «Thesmar, Ghislaine». Ballerina Gallery. 19 de novembro de 2020. Consultado em 10 de abril de ...

Estação Autobuses del Norte

Autobuses del Norte Estação Autobuses del NorteIndicador da estação. Uso atual Estação do Metrô da Cidade do México Administração Sistema de Transporte Colectivo Linha Linha 5 Posição Superfície Níveis 1 Plataformas 2 (laterais) Vias 2 Movimento em 2016 8.682.345[1] Serviços Conexões Informações históricas Inauguração 30 de agosto de 1982 (41 anos)[2] Localização Autobuses del NorteLocalização da Estação Autobuses del Norte19° 28' 44 N 99° 08'...

Megalithic Symphony

2011 studio album by AwolnationMegalithic SymphonyStandard edition cover. The deluxe edition features the same image at sunrise, while the 10th anniversary edition features it at sunset.Studio album by AwolnationReleasedMarch 15, 2011 (2011-03-15)RecordedRed Bull Studios, AWOLSTUDIO, Avatar Studios, Main and Market, Gymnasium, Fireside Sound StudioGenre Electronic rock[1][2] electropop[3] alternative rock[3] indie rock[2] pop rock...

Worcester Bleach and Dye Works

United States historic placeWorcester Bleach and Dye WorksU.S. National Register of Historic Places Show map of MassachusettsShow map of the United StatesLocation60 Fremont St., Worcester, MassachusettsCoordinates42°14′29″N 71°49′3″W / 42.24139°N 71.81750°W / 42.24139; -71.81750Architectural styleClassical RevivalNRHP reference No.00001343 [1]Added to NRHPNovember 08, 2000 The Worcester Bleach and Dye Works is a historic factory compl...

Perumbavoor Assembly constituency

Constituency of the Kerala legislative assembly in India PerumbavoorConstituency for theThe Kunnathunad Taluk headquarters office and Mini-Civil Station at PerumbavoorConstituency detailsCountryIndiaDistrictErnakulamEstablished1957 - presentTotal electors1,84,514 (2021)ReservationNoneMember of Legislative AssemblyIncumbent Eldhose Kunnappilly PartyINCAlliance UDFElected year2021 Perumbavoor State assembly constituency is one of the 140 state legislative assembly constituencies in K...

222 Main

Skyscraper in Salt Lake City 222 Main222 Main, July 2013Alternative namesHamilton Partners TowerEtymologyBuiling's street addressGeneral informationStatusCompletedTypehigh-rise office buildingLocation222 South Main StreetSalt Lake City, Utah 84111United StatesCoordinates40°45′51″N 111°53′28″W / 40.76417°N 111.89111°W / 40.76417; -111.89111Construction started2008CompletedDecember 2009Cost$125 millionOwnerPRIME US-222 MAIN, LLCManagementLincoln Property Comp...

Barth syndrome

Not to be confused with Bart syndrome. Human genetic metabolism disorder Medical conditionBarth SyndromeOther names3-Methylglutaconic aciduria type II, X-linked cardioskeletal myopathy and neutropenia, BTHS, Cardioskeletal myopathy with neutropenia and abnormal mitochondria, Cardioskeletal myopathy-neutropenia syndromeCardiolipinSpecialtyEndocrinology SymptomsDilated cardiomyopathy, neutropenia, short stature, muscle weakness.[1]ComplicationsHeart failure, delayed motor skills, i...

Roanoke Municipal Airport

O. Z. Whitehead

Liste von Apfelsorten