Yksinkertaisuustodistus

Matematiikassa ja tietojenkäsittelytieteessä ensisijaisuustodistus on tiukka todiste  siitä, että luku on alkuluku . Ensisijaisuusvarmenteen avulla voit tarkistaa, että luku on alkuluku turvautumatta ensisijaisuustesteihin .

Laskennallisen monimutkaisuuden teoriassa ymmärretään pääsääntöisesti, että varmenteen koko sekä sen varmentamiseen tarvittava aika riippuu polynomiaalisesti numeron syötteen pituudesta, eli sen numeroiden määrästä. se.

Polynomisten primaalisuusvarmenteiden olemassaolo osoittaa, että ongelmat, kuten primaalisuustestaus ja kokonaislukujen faktorointi kuuluvat luokkaan NP , koska yhden tämän luokan vastaavan määritelmän mukaan nämä ovat ongelmia, joiden ratkaisu voidaan varmistaa polynomiajassa, jos ylimääräinen todistus tarjotaan. Lisäksi nämä ongelmat ovat co-NP- luokassa , joka seuraa sen määritelmästä NP:n ongelmien komplementtien luokkana - itse asiassa mikä tahansa sen ei-triviaali jakaja voi olla polynomitodistus siitä, että luku on yhdistetty.

Siten primaalisuusvarmenteet olivat yksi ensimmäisistä osoituksista, että ensisijaisuustestaus ei ollut NP-täydellinen , koska jos olisi, siitä seuraisi, että NP-luokka on sisäkkäin co-NP:ssä, mikä puolestaan ​​​​yleensä on[ selventää ] harkittu[ kenen toimesta? ] on virheellinen. Lisäksi polynomivarmenteiden löytäminen teki primaalisuustestauksesta ensimmäisen ongelman, jonka tiedettiin kuuluvan sekä NP:hen että co-NP:hen, mutta jonka tiedettiin kuuluvan luokkaan P. Agrawal-Kayal-Saxena-testin tultua käyttöön vuonna 2002, ensimmäinen (ja tällä hetkellä ainoa[ milloin? ] ) deterministisen polynomin primaalisuustestissä havaittiin, että ongelma on edelleen P:ssä.

Prattin todistus

Historiallisesti ensisijaisuustodistusten käsite otettiin käyttöön Pratt-sertifikaatin myötä , jonka vuonna 1975 hankki Vaughan Pratt [1] , joka kuvasi sen rakennetta ja osoitti, että sertifikaatin koko riippuu polynomiaalisesti numerotietueen pituudesta. , ja myös sen, että se voidaan varmistaa polynomiajan osalta. Sertifikaatti perustuu Lucasin testiin , joka puolestaan ​​seuraa Fermatin pientä lausetta :

Kirjoitetut ehdot tarkoittavat tarkalleen , että elementin järjestys on .

1. Jos tällainen elementti on olemassa, niin ainakin jäännösrenkaan elementit ovat palautuvia modulo , eli koprime kanssa . Siten kaikki luvut ovat koprime kanssa , mikä viittaa tämän luvun yksinkertaisuuteen.
2. Jos luku on alkuluku, jäännösten modulorenkaassa on primitiivinen juuri , jonka järjestyksen on oltava yhtä suuri kuin . ■

Kun sinulla on tällainen luku (kutsutaan yksinkertaisuuden todistajaksi ) ja osiointi alkutekijöihin, voit tarkistaa yllä olevat ehdot nopeasti - sinun on suoritettava eksponentioinnit modulo, joka voidaan tehdä kertolaskuille binääri eksponentiolla . Itse kertolasku naiivissa toteutuksessa ("sarakkeessa") suoritetaan , mikä antaa kokonaisarvion ajoajasta .

Samalla on pidettävä mielessä, että edellä mainittujen ehtojen lisäksi on myös tarkistettava, että todistuksessa alkulukuna esitetyt numerot ovat todella sellaisia ​​- siis primaalisuuden todistajan ja jakautumisen lisäksi alkutekijät, numeron ensisijaisuustodistuksessa on oltava myös kaikkien siinä mainittujen tekijöiden ensisijaisuustodistukset. Näin ollen on kätevää esittää varmenne puun muodossa, jonka solmuissa on alkulukuja ja niitä vastaavia ensisijaisuuden todistajia, ja sen solmun jälkeläiset, johon luku on tallennettu , ovat luvun alkujakajia . Vastaavasti numero vastaa puun lehtiä .

Induktiolla voidaan osoittaa, että tällaisessa puussa on korkeintaan sisäisiä solmuja, eli sellaisia, jotka sisältävät parittoman alkuluvun. Kun otetaan huomioon, että puun jokainen solmu tallentaa bitin numeroiden kirjoittamista varten, voimme päätellä, että puun kokonaiskoko ei ylitä . Kokonaistarkistusaika puolestaan ​​voidaan arvioida muodossa , koska jokaisessa solmussa on suoritettava toimintoja.

Vaikka Prattin sertifikaatit ovat teoriassa hyödyllisiä ja helppo tarkistaa, sertifikaatin löytäminen numerolle edellyttää tekijöiden jakamista ja muita mahdollisesti suuria lukuja. Tämä on helppo tehdä joissakin erikoistapauksissa, esimerkiksi Fermat-alkuluvuilla , mutta yleensä tämä tehtävä on nyt paljon vaikeampi kuin tavallinen luvun alkulukutesti.

Vaikutus "PRIMES on P:ssä"

Artikkeli "PRIMES is in P" [2] oli läpimurto teoreettisessa tietojenkäsittelytieteessä . Tämä Manindra Agrawalin ja hänen kahden oppilaansa Niraj Kayalin ja Nitin Saxenan elokuussa 2002 julkaisema artikkeli todistaa, että kuuluisa primaalisuusongelma voidaan ratkaista deterministisesti polynomiajassa. Tekijät saivat työstään Gödel-palkinnon , joka on 5 000 dollaria [3] , ja vuoden 2006 Fulkerson-palkinnon .

Koska primaalisuustesti voidaan nyt tehdä polynomiajassa AKS-testin avulla, alkulukua voidaan pitää oman ensisijaisuuden varmenteena. Tämä testi valmistuu ajoissa , mikä tekee tällaisesta varmentamisesta kalliimpaa kuin Pratt-varmenteen käyttäminen, mutta ei vaadi itse varmenteen löytämistä.

Muistiinpanot

1. ↑ Vaughan Pratt. "Jokaisella pääpalkinnolla on ytimekäs todistus". SIAM Journal on Computing , voi. 4, s. 214-220. 1975. Lainaukset , koko teksti .
2. ↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin PRIMES on P-  kielellä (englanniksi)  // Annals of Mathematics  : Journal. - 2004. - syyskuu ( osa 160 , nro 2 ) . - s. 781-793 . - doi : 10.4007/annals.2004.160.781 . — .
3. ↑ 2017 Godel-palkinto . Euroopan tietojenkäsittelyteorian yhdistys . EATCS. Haettu: 29. maaliskuuta 2017. (määrätön)

Linkit

• Mathworld: Primality Certificate
• Mathworld Pratt -sertifikaatti
• Mathworld: Atkin-Goldwasser-Kilian-Morain-todistus
• Vasek Chvatal . Luentomuistiinpanot Pratt's Primality Proofsista . Tietojenkäsittelytieteen laitos. Rutgersin yliopisto. PDF-versio Concordia Universityssä .