Alkuluku

Alkuluku on luonnollinen luku, jolla on täsmälleen kaksi luonnollista jakajaa . Toisin sanoen luonnollinen luku on alkuluku, jos se eroaa ja on jaollinen ilman jäännöstä vain itsestään ja itsestään [1] . $s$ $yksi$ $yksi$ $s$

Esimerkki: luku on alkuluku (jaollinen luvulla ) , mutta se ei ole alkuluku, koska ja lisäksi se on jaollinen - sillä on kolme luonnollista jakajaa. $2$ $yksi$ $2$ $neljä$ $yksi$ $neljä$ $2$

Alkulukujen ominaisuuksien tutkimus liittyy lukuteoriaan , ja aritmetiikan päälause vahvistaa niiden keskeisen roolin siinä: mikä tahansa ylittävä kokonaisluku on joko alkuluku tai se voidaan ilmaista alkulukujen tulona, ja tällainen esitys on ainutlaatuinen tekijöiden järjestykseen asti [1] . Yksikköä ei viitata alkulukuina, koska muuten ilmoitetusta laajennuksesta tulee epäselvä [2] : . $yksi$ $x=1\cdot x=1\cdot 1\cdot x=1\cdot 1\cdot ...\cdot 1\cdot x$

Luonnolliset luvut voidaan jakaa kolmeen luokkaan: yksi (sillä on yksi luonnollinen jakaja), alkuluku (sillä on kaksi luonnollista jakajaa), yhdistelmäluku (sillä on enemmän kuin kaksi luonnollista jakajaa) [1] . Alku- ja yhdistelmälukuja on äärettömän monta.

Alkulukujen sarja alkaa näin:

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 7 , 7 , 9 _ _ _ _ _ 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

On olemassa useita algoritmeja sen tarkistamiseen, onko luku alkuluku. Esimerkiksi hyvin tunnettu jakajalaskentamenetelmä on primitiivinen ja hidas muihin verrattuna.

Alkulukuja käytetään laajalti matematiikassa ja siihen liittyvissä tieteissä. Monet tietotekniikan algoritmit , kuten epäsymmetriset salausjärjestelmät , käyttävät kokonaislukujen tekijöihinjako-ominaisuuksia [4] .

Monet alkulukuihin liittyvät ongelmat jäävät auki .

Alkuluvun käsitteestä on olemassa yleistyksiä mielivaltaisille renkaille ja muille algebrallisille rakenteille .

Historia

Ei tiedetä, milloin alkuluvun käsite määriteltiin, mutta ensimmäiset todisteet juontavat juurensa ylemmälle paleoliittiselle ajalle, jonka Ishangon luu vahvistaa [5] .

Muinaisten egyptiläisten matemaatikoiden säilyneissä asiakirjoissa on vihjeitä siitä, että heillä oli ajatuksia alkuluvuista: esimerkiksi Rhindin papyrus , joka juontaa juurensa toiselle vuosituhannelle eKr., sisältää taulukon luvun 2:sta suhteisiin , jota edustaa kolmen tai neljän egyptiläisen murtoluvun summa, yksikkö osoittajassa ja eri nimittäjissä. Murtolukujen, joiden nimittäjillä on yhteinen jakaja, laajennukset ovat samanlaisia, joten egyptiläiset tiesivät ainakin alkuluvun ja yhdistelmäluvun eron [6] . $n$

Varhaisimmat meille tulleet alkulukututkimukset ovat antiikin Kreikan matemaatikoiden ansiota . He keksivät Eratosthenesin seulan , algoritmin kaikkien alkulukujen 1:stä peräkkäiseen etsimiseen . Noin vuonna 300 eKr. julkaistu Euklidesin elementit sisältää tärkeitä lauseita alkuluvuista, mukaan lukien niiden joukon äärettömyydestä, Eukleideen lemmasta ja aritmeettisen peruslauseen [7] . $n$

1600-luvulle asti alkulukujen alalla ei ollut merkittäviä uusia teoksia [8] . Vuonna 1640 Pierre de Fermat muotoili Fermat'n pienen lauseen , jonka Leibniz ja Euler todistivat , sekä kahden neliösumman lauseen ja oletti myös, että kaikki muodon luvut ovat alkulukuja, ja jopa osoitti tämän . Mutta jo seuraavalle Fermat-luvulle Euler osoitti jaollisuuden luvulla . Uusia alkulukuja Fermat-sekvenssistä ei ole toistaiseksi löydetty. Samaan aikaan ranskalainen munkki Marin Mersenne huomasi, että sekvenssi , jossa on alkuluku, antaa myös alkuluvun [9] ( Mersennen numerot ). $2^{{2^{n}}}+1$ $n = 4$ $2^{2^{5}}+1$ $641$ $2^{p}-1$ $s$

Eulerin lukuteorian työ sisälsi paljon tietoa alkuluvuista. Hän osoitti, että ääretön lukusarja on divergentti. Vuonna 1747 hän osoitti, että jopa täydelliset luvut ovat sekvenssin arvoja , jossa tekijä on Mersennen luku. Kirjeenvaihdossa Goldbachin kanssa jälkimmäinen esitti kuuluisan olettamuksensa minkä tahansa parillisen luvun esittämisestä neljästä alkaen kahden alkuluvun summalla [10] . Todisteita olettamukselle ei ole vielä löydetty. ${\näyttötyyli 1/2+1/3+1/5+1/7+1/11+...}$ $2^{p-1}(2^{p}-1)$

1800-luvun alusta lähtien monien matemaatikoiden huomio on ollut alkulukujen asymptoottisen jakauman ongelma [10] . Legendre ja Gauss ehdottivat itsenäisesti, että alkulukujen tiheys on keskimäärin lähellä arvoa, joka on kääntäen verrannollinen luonnolliseen logaritmiin [11] .

Alkuluvuilla pidettiin pitkään vain vähän käyttöä puhtaan matematiikan ulkopuolella . Tämä muuttui 1970-luvulla julkisen avaimen salauksen käsitteiden tultua käyttöön, jolloin alkuluvut muodostivat perustan varhaisille salausalgoritmeille, kuten RSA [12] .

Luonnollisten lukujen hajottaminen alkulukujen tuloksi

Luonnollisen luvun esittämistä alkulukujen tulona kutsutaan hajotukseksi alkuluvuiksi tai lukutekijöiksi . Tällä hetkellä ei tunneta polynomialgoritmeja tekijöiden laskentaan , vaikka ei ole todistettu, etteikö sellaisia ole olemassa. RSA - salausjärjestelmä ja jotkut muut perustuvat faktorointiongelman oletettuun suureen laskennalliseen monimutkaisuuteen . Faktorisointi polynomikompleksisuudella on teoriassa mahdollista kvanttitietokoneessa käyttäen Shorin algoritmia [13] .

Aritmetiikan peruslause

Aritmeettisen peruslauseen mukaan jokainen luonnollinen luku , joka on suurempi kuin yksi, voidaan esittää alkulukujen tulona ja ainutlaatuisella tavalla tekijöiden järjestykseen asti [14] . Alkuluvut ovat siis luonnollisten lukujen alkeis "rakennuspalikoita". Esimerkiksi:

$23244$	$=2\cdot 2\cdot 3\cdot 13\cdot 149$
	$=2^{2}\cdot 3\cdot 13\cdot 149$ . ( merkitsee neliötä tai toista potenssia .) $2^{2}$ $2$

Kuten tässä esimerkissä näkyy, sama alkujakaja voi esiintyä useita kertoja. Hajoaminen:

n = p 1 p 2 ... p t _

lukua n (äärellisen luvun) alkutekijöihin p 1 , p 2 , … , p t kutsutaan n : n alkutekijöiksi . Aritmetiikan peruslause voidaan muotoilla uudelleen seuraavasti: mikä tahansa jako alkulukuihin on identtinen jakajien järjestykseen asti . Käytännössä useimmille luvuille on olemassa monia yksinkertaisia tekijöiden jakamisalgoritmeja, jotka kaikki antavat saman tuloksen [13] .

Yksikön yksinkertaisuus

Useimmat antiikin kreikkalaiset eivät edes pitäneet lukua, joten he eivät voineet pitää sitä alkulukuna [15] . Keskiajalla ja renessanssilla monet matemaatikot sisällyttivät ensimmäisen alkuluvun [16] . 1700-luvun puolivälissä Christian Goldbach mainittiin ensimmäisenä alkulukuna kuuluisassa kirjeenvaihdossaan Leonhard Eulerin kanssa ; Euler itse ei kuitenkaan pitänyt sitä alkulukuna [17] . 1800-luvulla monet matemaatikot pitivät lukua vielä alkulukuna. Esimerkiksi Derrick Norman Lemairen vuonna 1956 julkaistu luettelo alkuluvuista numeroon alkoi ensimmäisellä alkuluvulla. Sanotaan, että Henri Lebesgue on viimeinen matemaatikko, joka kutsui alkulukua [18] . 1900-luvun alussa matemaatikot alkoivat päästä yhteisymmärrykseen siitä, mikä ei ole alkuluku, vaan pikemminkin muodostaa oman erikoiskategoriansa - "yksi" [16] . $yksi$ $yksi$ $yksi$ $yksi$ $yksi$ $10006721$ $yksi$ $yksi$ $yksi$

Jos sitä pidetään alkulukuna, Eukleideen aritmetiikkaa koskeva peruslause (mainittu edellä) ei päde, kuten artikkelin alussa mainittiin. Esimerkiksi luku voidaan jakaa 3 5 ja 1 3 5 . Jos se olisi alkuluku, näitä kahta vaihtoehtoa pidettäisiin eri tekijöinä ; näin ollen tämän lauseen lausetta olisi muutettava [16] . Samalla tavalla Eratosthenesin seula ei toimisi oikein, jos sitä pidettäisiin yksinkertaisena: seulan modifioitu versio, joka olettaa sen olevan alkuluku, sulkee pois kaikki kertoimet (eli kaikki muut luvut), ja tuottaa vain yhden numeron ulostulossa - . Lisäksi alkuluvuilla on useita ominaisuuksia, joita luvulla ei ole , kuten luvun suhde sitä vastaavaan Euler-identiteettifunktion arvoon tai jakajafunktion summa [2] . $yksi$ $viisitoista$ $yksi$ $viisitoista$ $yksi$ $yksi$ $yksi$ $yksi$ $yksi$

Algoritmit alkulukujen etsimiseen ja tunnistamiseen

Yksinkertaisia tapoja löytää alkulukuluettelo johonkin arvoon asti antaa Eratosthenesin seula , Sundaramin seula ja Atkinin seula [19] .

Käytännössä alkulukuluettelon hankkimisen sijaan on kuitenkin usein tarpeen tarkistaa, onko tietty luku alkuluku. Algoritmeja, jotka ratkaisevat tämän ongelman, kutsutaan primaliteettitesteiksi . Polynomisia primaalisuustestejä on monia , mutta useimmat niistä ovat todennäköisyystestejä (esimerkiksi Miller-Rabinin testi ) ja niitä käytetään kryptografian tarpeisiin [20] . Vuonna 2002 todettiin, että yleinen primaalisuusongelma on polynomisesti ratkaistava, mutta ehdotetulla deterministisellä Agrawal-Kayal-Saksena -testillä on melko suuri laskennallinen monimutkaisuus , mikä vaikeuttaa sen soveltamista käytännössä [21] .

Joillekin lukuluokille on olemassa erityisiä tehokkaita primaalisuustestejä (katso alla).

Yksinkertaisuustesti

Primaalisuustesti (tai primaalitesti) on algoritmi , joka ottaa luvun syötteeksi sallii joko olla vahvistamatta oletusta luvun koostumuksesta tai vahvistaa sen primaalisuuden tarkasti. Toisessa tapauksessa sitä kutsutaan todelliseksi primaalisuustestiksi. Primaalisuustestin tehtävä kuuluu kompleksisuusluokkaan P , eli sen ratkaisemiseen tarvittavien algoritmien ajoaika riippuu polynomiaalisesti syötetietojen koosta, mikä todistettiin vuonna 2002 [22] . Polynomialgoritmin syntymistä ennusti polynomisten ensisijaisuusvarmenteiden olemassaolo ja sen seurauksena se, että luvun primaalisuuden tarkistamisen ongelma kuului samanaikaisesti NP- ja co-NP- luokkiin .

Olemassa olevat algoritmit luvun primaalisuuden testaamiseksi voidaan jakaa kahteen luokkaan: todellisen primaalisuuden testit ja todennäköisyyspohjaisuustestit. Tositestien laskelmien tulos on aina luvun yksinkertaisuus tai koostumus. Todennäköisyystesti osoittaa, onko luku alkuluku jollain todennäköisyydellä. Lukuja, jotka täyttävät todennäköisyyspohjaisen primaalisuustestin, mutta ovat yhdistelmälukuja, kutsutaan pseudoalkuluvuiksi [23] . Yksi esimerkki tällaisista luvuista ovat Carmichael-luvut [24] .

Yksi esimerkki todellisista primaalisuustesteistä on Luc - Lehmerin testi Mersennen numeroille . Tämän testin ilmeinen haittapuoli on, että se koskee vain tietyntyyppisiä lukuja. Muita esimerkkejä ovat ne, jotka perustuvat Fermatin pieneen lauseeseen [25]

Pepinin testi Fermat - luvuille
Protin lause Protin luvuille
Agrawal-Kayala-Saxene testi , ensimmäinen universaali, polynominen, deterministinen ja ehdoton primaalisuustesti.
Luc-Lehmer-Riesel testi

Yhtä hyvin kuin:

jakajan iterointimenetelmä
Wilsonin lause
Pocklingtonin kriteeri
Millerin testi
Adleman-Pomerans-Rumeli testi , parannettu [26] Cohenin ja Lenstroyn toimesta
Primaalisuustesti elliptisiä käyriä käyttäen .

Todennäköisyyspohjaiset primaalisuustestit sisältävät:

Suuret alkuluvut

Useiden vuosisatojen ajan "suurien" alkulukujen etsiminen on kiinnostanut matemaatikoita. Viime vuosikymmeninä nämä tutkimukset ovat saaneet käytännön merkitystä, koska tällaisia numeroita on käytetty useissa salausalgoritmeissa, kuten RSA :ssa [12] .

1700-luvulla Marin Mersenne ehdotti, että muodon luvut ovat alkulukuja (jos n ≤ 257) vain n :lle , joka on yhtä suuri kuin 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 ja 257 [11 ] . Oletuksen oikeellisuuden tarkistaminen oli paljon tuon ajan kykyjen yläpuolella. Vasta 1900-luvulla havaittiin, että hypoteesi oli väärä ja luultavasti tehty "sokeasti", koska Mersenne ei ottanut huomioon kolmea tapausta ( n = 61, 89 ja 107); lisäksi kävi ilmi, että n = 67 ja n = 257 vastaavat luvut ovat yhdistettyjä [11] . $2^{n}-1$

Vuonna 1876 Eduard Lucas osoitti, että M 127 (39-numeroinen luku) on alkuluku, se oli suurin tunnettu alkuluku vuoteen 1951 asti, jolloin löydettiin (44 numeroa) ja vähän myöhemmin (79 numerosta) - viimeinen alkuluku, joka löydettiin elektronisella laskimella. Siitä lähtien kaikki myöhemmät suuret alkuluvut on löydetty tietokoneella: vuodesta 1952 (jolloin SWAC osoitti M 521 :n alkuluvuksi) vuoteen 1996 asti ne löydettiin supertietokoneella , ja kaikki olivat Mersennen alkulukuja (löytyi Luc-Lehmerin testillä , erityinen algoritmi tällaisille numeroille), lukuun ottamatta lukua , joka oli ennätys vuosina 1989-1992 [27] . ${\frac {2^{148}+1}{17}}$ $180*(2^{127}-1)^{2}+1$ $391581*2^{216193}-1$

Algoritmit alkulukujen saamiseksi

Jotkut matematiikan ongelmat tekijöihin jakamista vaativat sarjan satunnaisesti valittuja erittäin suuria alkulukuja. Algoritmi niiden saamiseksi Bertrandin postulaatin perusteella (Jokaiselle luonnolliselle luvulle n ≥ 2, välissä n < p < 2 n on alkuluku p .) [28] :

Algoritmi:

Syöttö : luonnollinen luku $N$
Ratkaisu (etsi satunnaista alkulukua P)
1. $P\gets$ Funktio , jolla generoidaan mielivaltainen luonnollinen luku segmentille $[N,2N]$
2. Jos komposiitti, niin $P$
  1. $P\vasen \,P+1$
  2. Jos sitten $P = 2N$
    1. $P\leftarrow \,N$
3. Palauttaa " - satunnainen alkuluku" $P$

Aikaa ongelman ratkaisemiseen tällä algoritmilla ei ole määritelty, mutta on suuri todennäköisyys, että se on aina polynomi, kunhan alkulukuja on tarpeeksi ja ne jakautuvat enemmän tai vähemmän tasaisesti . Yksinkertaisille satunnaisluvuille nämä ehdot täyttyvät [21] .

Tehokkain tapa muodostaa alkulukuja on hieman muunnettu Fermatin pieni lause [26] .

Olkoon N, S parittomia luonnollisia lukuja, N-1 = S*R, ja jokaiselle S:n alkujakajalle q on sellainen kokonaisluku , $a$

$a^{N-1}=1{\pmod {N))$ , $\gcd(a^{{\frac {N-1}{q}}-1},n)=1$

Silloin jokainen N:n alkujakaja p täyttää kongruenssin

$p=1{\pmod {2S))$

Seuraus. Jos Fermat'n lauseen ehdot täyttyvät , niin N on alkuluku [26] . $R\leqslant 4S+2$

Osoitetaan nyt, kuinka viimeisen lauseen avulla voidaan muodostaa oleellisesti suurempi alkuluku , kun otetaan huomioon suuri alkuluku . Tätä varten valitsemme väliltä satunnaisesti parillisen luvun ja asetamme . Sitten tarkistamme luvun pienten alkulukujen puuttumisen jakamalla sen pienillä alkuluvuilla; Testataan useita kertoja Rabinin algoritmilla. Jos samaan aikaan käy ilmi, että kyseessä on yhdistelmäluku , sinun tulee valita uusi arvo ja toistaa laskelmat uudelleen. Tätä tulee tehdä, kunnes löytyy luku N, joka on läpäissyt Rabinin algoritmin testin riittävän monta kertaa. Tässä tapauksessa on toivoa, että kyseessä on alkuluku, ja alkuluku pitäisi yrittää todistaa alkulukutesteillä [26] . $S$ $N$ $R$ $R\leqslant 4S+2$ $N=SR+1$ $N$ $N$ $N$ $R$ $N$

Alkulukujen ääretön

Alkulukuja on äärettömän monta . Tätä väitettä kutsutaan Eukleideen lauseeksi antiikin kreikkalaisen matemaatikon Eukleideen mukaan, koska ensimmäinen tunnettu todiste tälle väitteelle on katsottu hänelle. Alkulukujen äärettömyydelle tunnetaan monia muitakin todisteita, mukaan lukien Eulerin analyyttinen todistus , Goldbachin todistus Fermat-luvuilla [29] , Furstenbergin todistus yleistä topologiaa käyttäen ja Kummerin elegantti todistus .

Suurin tunnettu alkuluku

Tietueita on pidetty pitkään, mikä merkitsee suurimmat tuolloin tunnetut alkuluvut [30] . Euler asetti yhden ennätyksistä kerrallaan löydettyään alkuluvun 2 31 − 1 = 2 147 483 647 .

Suurin tunnettu alkuluku tammikuussa 2019 on Mersennen luku M 82 589 933 = 2 82 589 933 − 1 . Se sisältää 24 862 048 desimaalinumeroa ; tämän määrän tallentavassa kirjassa olisi noin yhdeksäntuhatta sivua. Se löydettiin 7. joulukuuta 2018 osana GIMPS :n hajautettua Mersennen alkulukujen hakua . Edellinen suurin tunnettu alkuluku, joka löydettiin joulukuussa 2017, oli 1 612 623 merkkiä vähemmän [31] .

Mersennen luvut eroavat suotuisasti muista tehokkaan primaalisuustestin , Luc-Lehmerin testin, ansiosta . Hänen ansiostaan Mersennen alkuluvut ovat pitkään pitäneet ennätystä suurimpana tunnettuna alkulukuna.

Yli 100 000 000 ja 1 000 000 000 desimaalin alkulukujen löytämisestä EFF myönsi [32] 150 000 dollarin ja 250 000 dollarin rahapalkintoja [33] . EKTR on aiemmin jakanut palkintoja 1 000 000 ja 10 000 000 desimaalin alkulukujen löytämisestä.

Erikoistyyppiset alkuluvut

On olemassa useita lukuja, joiden primaalisuus voidaan määrittää tehokkaasti käyttämällä erikoisalgoritmeja.

Mersennen luvut ovat muotoa , jossa n on luonnollinen luku [34] . Lisäksi Mersennen luku voi olla alkuluku vain, jos n on alkuluku. Kuten edellä todettiin, tehokas primaalisuustesti on Luc-Lehmer-testi [35] . $M_{n}=2^{n}-1$
Fermat-luvut ovat muotoa , jossa n on ei-negatiivinen kokonaisluku [36] . Tehokas primaalisuustesti on Pepinin testi . Helmikuusta 2015 lähtien tiedetään vain 5 Fermat-alkulukua ( n = 0, 1, 2, 3, 4), seuraavat kaksikymmentäkahdeksan Fermat-alkulukua (ja mukaan lukien) osoittautuivat yhdistetyiksi [37] , mutta ei ole todistettu, että muut alustavat Farm no [38] . $F_{n}=2^{2^{n}}+1$ $F_{32}$
Woodall-luvut ovat muotoa [39] . Tehokas primaalisuustesti on Lucas-Lehmer-Riesel-testi [40] . $W_{n}=n\cdot 2^{n}-1$
Cullen-luvut ovat muotoa [41] [42] . $C_{n}=n\cpiste 2^{n}+1$
Proth-luvut ovat muotoa , jossa k on pariton ja [43] . Tehokas primaalisuustesti Proth- luvuille on Brillhart -Lehmer-Selfridge-testi [ 44 ] . Cullen-luvut ja Fermat-luvut ovat Proth-lukujen erikoistapaus ( k = n ja k = 1, vastaavasti ) [45] . $P=k\cdot 2^{n}+1$ $2^{n}>k$ $n=2^{m}$
Mills-luvut ovat numeroita, joiden muoto on Mills-vakio [46] . $P_{n}=[A^{3^{n}}],$ $A$

Määritettyjen tyyppien alkulukujen etsimiseen käytetään tällä hetkellä hajautettuja laskentaprojekteja GIMPS , PrimeGrid , Ramsey@Home , Seventeen tai Bust , Riesel Sieve , Wieferich@Home .

Jotkut ominaisuudet

Jos p on alkuluku ja p jakaa ab :n , niin p jakaa a:n tai b :n . Todisteen tästä tosiasiasta antoi Euclid, ja se tunnetaan nimellä Euklides Lemma [7] [47] . Sitä käytetään aritmeettisen peruslauseen todistuksessa .
Jäännösrengas on kenttä, jos ja vain jos se on yksinkertainen [48] . $\mathbb {Z} _{n}$ $n$
Kunkin kentän ominaisuus on nolla tai alkuluku [48] .
Jos on alkuluku ja luonnollinen, niin se on jaollinen ( Fermatin pieni lause ) [49] . $s$ $a$ $a^{p}-a$ $s$
Jos on äärellinen ryhmä, jonka järjestys on jaollinen luvulla , niin se sisältää järjestyselementin ( Cauchyn lause ) [50] . $G$ $|G|$ $s$ $G$ $s$
Jos on äärellinen ryhmä ja on suurin jakaja , niin sillä on järjestyksen aliryhmä , jota kutsutaan Sylow-aliryhmäksi , ja lisäksi Sylow-aliryhmien lukumäärä on yhtä suuri jollekin kokonaisluvulle ( Sylow'n lause ) [51] . $G$ $p^{n}$ $s$ $|G|$ $G$ $p^{n}$ $pk+1$ $k$
Luonnollinen on alkuluku silloin ja vain jos se on jaollinen ( Wilsonin lause ) [52] . $p>1$ $(p-1)!+1$ $s$
Jos on luonnollinen luku, niin on olemassa sellainen alkuluku , että ( Bertrandin postulaatti ) [53] . $n>1$ $s$ $n<p<2n$
Käänteislukusarja divergoi [10] . Lisäksi klo $x\to \infty$ $\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x.$
Mikä tahansa muodon aritmeettinen progressio , jossa on yhteislukuja , sisältää äärettömän monta alkulukua ( Dirichlet-lause alkuluvuista aritmeettisessa progressiossa ) [54] . $a,a+q,a+2q,a+3q,...$ $a,q>1$
Mikä tahansa alkuluku, joka on suurempi kuin 3, voidaan esittää muodossa tai , jossa on jokin luonnollinen luku. Näin ollen, jos ero useiden peräkkäisten alkulukujen välillä (kun k>1) on sama, se on välttämättä luvun 6 kerrannainen - esimerkiksi: 251-257-263-269; 199-211-223; 20183-20201-20219. $6k+1$ $6k-1$ $k$
Jos on alkuluku, niin se on luvun 24 kerrannainen (pätee myös kaikille parittomille luvuille, jotka eivät jao kolmella) [55] . $p>3$ $p^{2}-1$
Green-Tao -lause . On olemassa mielivaltaisen pitkiä äärellisiä aritmeettisia progressioita, jotka koostuvat alkuluvuista [56] .
Mikään alkuluku ei voi näyttää tältä , missä n >2, k >1. Toisin sanoen alkulukua seuraava luku ei voi olla neliö tai suurempi potenssi, jonka kanta on suurempi kuin 2. Tästä seuraa myös, että jos alkuluvun muoto on , niin k on alkuluku (katso Mersennen luvut ) [34 ] . $n^{k}-1$ $2^{k}-1$
Mikään alkuluku ei voi näyttää tältä , missä n >1, k >0. Toisin sanoen alkulukua edeltävä luku ei voi olla kuutio tai suurempi pariton potenssi, jonka kanta on suurempi kuin 1 [57] . $n^{{2k+1}}+1$
Jokainen alkuluku (paitsi muodon numerot ) voidaan esittää kolmen neliön summana [58] . $8n-1$

Sovellukset

Alkuluvut ovat peruskomponentteja monilla matematiikan alueilla .

Aritmeettiset funktiot

Aritmeettisilla funktioilla , nimittäin funktioilla, jotka on määritelty luonnollisten lukujen joukossa ja jotka ottavat arvoja kompleksilukujoukosta, on ratkaiseva rooli lukuteoriassa. Erityisesti tärkeimmät niistä ovat kertofunktiot , eli funktiot , joilla on seuraava ominaisuus: jos pari koostuu koprime-luvuista, yhtäläisyys tapahtuu [59] $f$ $(a, b)$

$f(ab)=f(a)f(b)$

Esimerkkejä kertovista funktioista ovat Euler-funktio , joka yhdistää luvun luonnollisten lukujen määrään, joka on pienempi kuin n, ja koprime sen kanssa ja n: n jakajien lukumäärään [60] . Näiden funktioiden arvo alkuluvun potenssista: $\phi$ $n$

Euler- funktio $\phi$ :

${\displaystyle \phi (p^{m})=p^{m}-p^{m-1))$

Jakajatoiminto :

$\sigma (p^{m})=m+1$

Aritmeettiset funktiot voidaan laskea helposti, kun tiedetään niiden arvot alkulukujen potenssien osalta [59] . Itse asiassa luonnollisen luvun n kertoimesta

$n=p_{1}^{q_{1}}\cdot ...\cdot p_{a}^{q_{a}}$

meillä on se

$f(n)=f(p_{1}^{q_{1)))\cdot ...\cdot f(p_{a}^{q_{a)))$

ja siksi, palataen laskentatehtävään, käy ilmi, että on yleensä helpompi laskea jokaisesta alkujakajan potenssista kuin laskea yleisen kaavan [61] avulla . $f(n)$ $f$ $f$

Esimerkiksi Euler-funktion arvon selvittämiseksi arvosta n = 450 = 2 × 3 2 × 5 2 riittää laskeminen $\phi$

$\phi (450)=\phi (2)\cdot \phi (3^{2})\cdot \phi (5^{2})=(2-1)\cdot (9-3)\ cdot(25-5)=120$

Modulaarinen aritmetiikka

Modulaarisessa aritmetiikassa alkuluvuilla on erittäin tärkeä rooli: jäännösrengas on kenttä silloin ja vain, jos n on alkuluku [48] . Myös primitiivisen rengasjuuren olemassaolo on sidottu alkulukuihin: se on olemassa vain, jos n on alkuluku, 1, 2, 4 tai luku muodossa , jossa p on pariton. $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$ $p^{n}\circ 2p^{n}$

Yksi modulaarisen aritmeetiikan tärkeimmistä lauseista on Fermatin pieni lause [52] . Tämä lause sanoo, että mille tahansa alkuluvulle p ja mille tahansa luonnolliselle luvulle a meillä on:

$a^{p}\equiv a{\pmod {p))$

tai mille tahansa alkuluvulle p ja mikä tahansa luonnollinen a, joka ei ole jaollinen p :llä ,

$a^{p-1}\equiv 1{\pmod {p))$

Tämän ominaisuuden avulla voidaan tarkistaa, onko luku ei alkuluku. Itse asiassa, jos n on sellainen, että:

$a^{n}\not \equiv a{\pmod {n))$

jollekin luonnolliselle a , niin n ei voi olla yksinkertainen [52] . Tällä ominaisuudella ei kuitenkaan voida testata, onko luku alkuluku: on joitakin lukuja, joita kutsutaan Carmichael-luvuiksi (pienin on 561), joille tämä ei pidä paikkaansa. Carmichael-luku on yhdistelmäluku , joka on pseudoalkuluku jokaisessa n:n b-kantaluvussa. Vuonna 1994 William Robert Alford, Andrew Granville ja Carl Pomerance osoittivat, että tällaisia lukuja on äärettömän paljon [62] .

Ryhmäteoria

Alkuluvuilla on myös keskeinen rooli algebrassa . Ryhmäteoriassa ryhmää , jossa jokainen alkio on alkuluvun p potenssi, kutsutaan p-ryhmäksi [63] . P-ryhmä on äärellinen silloin ja vain, jos ryhmän järjestys (sen alkioiden lukumäärä) on p:n potenssi. Esimerkki äärettömästä p-ryhmästä on Pruferin p -ryhmä [64] . Tiedetään, että p -ryhmillä on ei-triviaali keskus, joten ne eivät voi olla yksinkertaisia (paitsi ryhmä, jossa on p - elementtejä); jos ryhmä on äärellinen, lisäksi kaikki normaalit alaryhmät leikkaavat keskustan ei-triviaalilla tavalla.

Esimerkki tällaisista ryhmistä on syklinen kertolaskuryhmä alkuluvun modulo [ 65 ] .

Kaikki p-luokan ryhmät ovat syklisiä ja siksi abelinlaisia ; jokainen luokan p 2 ryhmä on myös Abelin . Lisäksi mikä tahansa äärellinen Abelin ryhmä on isomorfinen äärellisen määrän syklisten p-ryhmien suoralle tulolle.

Cauchyn lause sanoo , että jos äärellisen ryhmän G kertaluku on jaollinen alkuluvulla p, niin G sisältää kertaluvun p alkioita. Tämä lause on yleistetty Sylow'n lauseilla [50] .

Julkisen avaimen salausjärjestelmä

Jotkut julkisen avaimen salausalgoritmit, kuten RSA ja Diffie-Hellman-avaimenvaihto , perustuvat suuriin alkulukuihin (tyypillisesti 1024-2048 bittiä). RSA luottaa siihen oletukseen, että on paljon helpompaa (eli tehokkaampaa) suorittaa kahden (suuri) luvun x ja y kertolasku kuin laskea koprime x ja y , jos vain niiden tulo tunnetaan . Diffie-Hellman-avainten vaihto perustuu siihen, että eksponentiomoduloinnille on olemassa tehokkaita algoritmeja ja diskreetin logaritmin käänteistä toimintaa pidetään vaikeana [66] [67] . $x\cdot y$

rsa

Suurien lukujen tekijöihin laskemisen vaikeus johti ensimmäisen tehokkaan julkisen avaimen salausmenetelmän , RSA :n, kehittämiseen [68] . Tässä salausjärjestelmässä henkilö, jonka on määrä vastaanottaa salattu viesti, muodostaa avaimen: valitaan kaksi erilaista satunnaista alkulukua ja tietty koko (käytetään yleensä 1024- tai 2048- bittisiä lukuja). Lisäksi heidän tuotteensa lasketaan , kutsutaan moduuliksi . Euler-funktion arvo lasketaan luvusta : . Valitaan kokonaisluku ( ), joka vastaa alkulukua funktion arvon kanssa . Yleensä pienet alkuluvut otetaan sellaisinaan (esimerkiksi Fermat -alkuluvut ). Lukua kutsutaan julkiseksi eksponenttiksi . _ _ Luku lasketaan , jota kutsutaan salaisen eksponentin kertoimella käänteiseksi luvulle e modulo . Pari on julkaistu julkisena RSA- avaimena ( RSA public key ) . Pari toimii RSA : n yksityisenä avaimena , ja se pidetään salassa [12] . $s$ $q$ $n=p*q$ $n$ $\phi (n)=(p-1)(q-1)$ $e$ $1<e<\phi (n)$ $\phi(n)$ $e$ $e$ $d$ $\phi(n)$ ${\näyttötyyli \{e,n\))$ $\{d,\phi (n)\}$

Teoreettisesti on mahdollista johtaa yksityinen avain julkisesta tiedosta: tämä vaatii tällä hetkellä lukukerrointa , mikä tekee turvallisen viestin lähettämisen, jos alkuluvut täyttävät tietyt ehdot ja ovat "riittävän suuria". Vielä ei tiedetä, onko olemassa tehokkaita menetelmiä viestin salauksen purkamiseen, joihin ei liity suoraa faktorointihyökkäystä , mutta on osoitettu, että huono julkisen avaimen valinta voi tehdä järjestelmästä alttiimman tällaisille hyökkäyksille [69] . $n$ $n$

Vuonna 1991 RSA Security julkaisi listan semiprime -suorituksista ja tarjosi rahapalkintoja joidenkin niistä huomioon ottamisesta todistaakseen menetelmän turvallisuuden ja rohkaistakseen tutkimusta tällä alueella: aloite nimeltä Challenge RSA Factoring [70] . Vuosien varrella osa näistä luvuista on hajotettu, ja toisten osalta tekijöiden jakautumisongelma on edelleen avoin; kilpailu kuitenkin päättyi vuonna 2007 [70] .

Kaavat alkulukujen löytämiseksi

Eri aikoina on yritetty osoittaa lauseketta, jonka arvot siihen sisältyvien muuttujien eri arvoille olisivat alkulukuja [54] . L. Euler osoitti polynomin , joka ottaa alkuarvot arvoille n = 0, 1, 2, ..., 40 . Kuitenkin, jos n = 41 , polynomin arvo on yhdistelmäluku. Voidaan todistaa, että yhdessä muuttujassa n ei ole polynomia, joka ottaisi alkuarvot kaikille kokonaisluvuille n [54] . P. Fermat ehdotti, että kaikki luvut muodossa 2 2 k + 1 ovat yksinkertaisia; Euler kuitenkin kumosi tämän olettamuksen osoittamalla, että luku 2 2 5 + 1 = 4 294 967 297 on yhdistelmä [54] . $\textstyle n^{2}-n+41,$

Siitä huolimatta on polynomeja, joiden positiivisten arvojen joukko muuttujien ei-negatiivisille arvoille osuu yhteen alkulukujen joukon kanssa. Yksi esimerkki on polynomi

{\begin{aligned}{\bigl (}k+2{\bigr )}{\bigl \{}1&-{\bigl [}wz+h+jq{\bigr ]}^{2}- {\bigl [}(gk+2g+k+1)(h+j)+hz{\bigr ]}^{2}-{\bigl [}2n+p+q+ze{\bigr ]}^{ 2}\\&-{\bigl [}16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}{\bigr ]}^{ 2}-{\bigl [}e^{3}(e+2)(a+1)^{2}+1-o^{2}{\bigr ]}^{2}-{\bigl [} (a^{2}-1)y^{2}+1-x^{2}{\bigr ]}^{2}\\&-{\bigl [}16r^{2}y^{4} (a^{2}-1)+1-u^{2}{\bigr ]}^{2}-{\bigl [}((a+u^{2}(u^{2}-a) )^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}{\bigr ]}^{2}-{\bigl [}n+l+vy{ \bigr ]}^{2}\\&-{\bigl [}(a^{2}-1)l^{2}+1-m^{2}{\bigr ]}^{2}-{ \bigl [}ai+k+1-li{\bigr ]}^{2}-{\bigl [}p+l(an-1)+b(2an+2a-n^{2}-2n-2 )-m{\bigr ]}^{2}\\&-{\bigl [}q+y(ap-1)+s(2ap+2a-p^{2}-2p-2)-x{\ isompi ]}^{2}-{\bigl [}z+pl(ap)+t(2ap-p^{2}-1)-pm{\bigr ]}^{2}{\bigr \}}\ loppu{tasattu}}

sisältää 26 muuttujaa ja jonka aste on 25. Pienin aste tämän tyyppisille tunnetuille polynomeille on 5 42 muuttujalla; pienin määrä muuttujia on 10 asteella noin 1,6·10 45 [71] [72] . Tämä tulos on Juri Matiyasevitšin todistaman minkä tahansa numeroitavan joukon diofantiiniominaisuuden erikoistapaus .

Mielenkiintoista on, että yllä oleva polynomi, joka tuottaa alkulukuja, itse muuttuu kertoimella. Huomaa, että tämän polynomin toinen tekijä (hakasulkeissa) on muotoa: yksi miinus neliöiden summa. Näin ollen polynomi voi saada positiivisia arvoja (positiivisille arvoille ) vain, jos jokainen näistä neliöistä (eli jokainen polynomi hakasulkeissa) on yhtä suuri kuin nolla. Tässä tapauksessa suluissa oleva lauseke on yhtä suuri kuin 1 [73] . $k$

Avoimet kysymykset

Alkuluvuista on edelleen monia avoimia kysymyksiä , joista tunnetuimmat esitti Edmund Landau vuonna 1912 Fifth International Mathematical Congressissa [74] :

Goldbachin ongelma ( Landaun ensimmäinen tehtävä ): onko totta, että jokainen parillinen luku, joka on suurempi kuin kaksi, voidaan esittää kahden alkuluvun summana?
Landaun toinen ongelma : onko olemassa ääretön joukko " yksinkertaisia kaksosia " — alkulukupareja, joiden ero on 2 [54] ? Vuonna 2013 matemaatikko Zhang Yitang New Hampshiren yliopistosta [75] [76] osoitti, että alkulukupareja on äärettömän monta, joiden välinen etäisyys ei ylitä 70 miljoonaa. Myöhemmin James Maynard paransi tulosta 600:aan. Vuonna 2014 Terence Taon johtama Polymath -projekti paransi jälkimmäistä menetelmää jonkin verran korvaamalla etäisyysarvion 246:lla.
Legendren arvelu ( Landaun kolmas ongelma ): onko totta, että kaikilla luonnollisilla luvuilla välillä ja on aina alkuluku [77] ? $n$ $n^{2}$ $(n+1)^2$
Landaun neljäs ongelma : onko muodon alkulukujen joukko ääretön , missä on luonnollinen luku [54] ? $n^{2}+1$ $n$

Avoin ongelma on myös äärettömän määrän alkulukuja monissa kokonaislukujonoissa, mukaan lukien Mersennen luvut [54] , Fibonacci-luvut , Fermat -luvut jne.

Muunnelmia ja yleistyksiä

Redusoitumattomat ja alkuelementit

Artikkelin alussa annettiin alkuluvun määritelmä: luonnollista lukua kutsutaan alkuluvuksi, jos sillä on täsmälleen kaksi jakajaa - yksi ja itse luku. Samanlainen käsite voidaan ottaa käyttöön muissa algebrallisissa rakenteissa; useimmiten harkitaan kommutatiivisia renkaita ilman nollajakajia ( eheysalueita ) [78] [79] . Tällaisilla renkailla voi kuitenkin olla ykseyden jakajia , jotka muodostavat kertovan ryhmän . Esimerkiksi kokonaislukujen renkaassa on kaksi yksikön jakajaa: ja Siksi kaikilla kokonaisluvuilla, paitsi yksikön jakajilla, ei ole kahta, vaan vähintään neljä jakajaa; esimerkiksi luvulla 7 on jakaja.Tämä tarkoittaa, että alkuluvun käsitteen yleistyksen tulee perustua sen muihin ominaisuuksiin. $+1$ $-yksi.$ $1;7;-1;-7.$

Alkuluvun analogi eheysalueelle on redusoitumaton elementti . joka määritellään seuraavasti [80] .

Nollasta poikkeavaa eheysalueen alkiota kutsutaan redusoitumattomaksi (joskus hajoamattomaksi ), jos se ei ole yksikön jakaja ja tasa-arvosta seuraa, että tai on yksikön jakaja. $s$ $p=ab$ $a$ $b$

Kokonaisluvuille tämä määritelmä tarkoittaa, että pelkistymättömät alkiot ovat luonnollisia alkulukuja sekä niiden vastakohtia.

Määritelmästä seuraa, että pelkistymättömän elementin jakajien joukko koostuu kahdesta osasta: kaikista yksikön jakajista ja tuloksista kaikilla yksikön jakajilla (näitä tuloja kutsutaan elementteihin assosioituneiksi ). Eli pelkistymättömän jakajien lukumäärä , jos se on äärellinen, on kaksi kertaa renkaan yksikön jakajien määrä. $s$ $s$ $s$ $p,$

Erittäin tärkeä on aritmeettisen päälauseen analogi , joka yleistetyssä muodossa on muotoiltu seuraavasti [81] :

Rengasta kutsutaan faktoriaaliseksi , jos jokainen siinä oleva nollasta poikkeava elementti, joka ei ole yksikön jakaja, voidaan esittää pelkistymättömien elementtien tulona, ja tämä esitys on ainutlaatuinen tekijöiden permutaatioon ja niiden assosiaatioon asti (kertominen yksikön jakajilla). ).

Jokainen eheysalue ei ole tekijä, katso vastaesimerkki . Euklidinen rengas on aina tekijä [82] .

Alkuluvun käsitteelle on olemassa toinen, kapeampi yleistys, jota kutsutaan alkuelementiksi [80] .

Eheysalueen nollasta poikkeavaa alkiota kutsutaan yksinkertaiseksi , jos se ei ole yksikköjakaja ja tulo voi olla jaollinen vain, jos ainakin yksi alkioista tai on jaollinen . $s$ $ab$ $s$ $a$ $b$ $s$

Yksinkertainen elementti on aina redusoitumaton. Todellakin, jos elementti on yksinkertainen ja sitten yksinkertaisen elementin määritelmän mukaan yksi tekijöistä, olkoon se jaollinen eli Sitten tai vähennettäessä (eheysalueella nollasta poikkeavan tekijän pelkistys on aina mahdollista) : eli on yhtenäisyyden jakaja. ■ $s$ $p=ab,$ $a,$ $p,$ $a=pq.$ $p=ab=pqb$ $s$ $1=qb,$ $b$

Päinvastoin ei yleensä pidä paikkaansa; pelkistymätön elementti ei välttämättä ole yksinkertainen, jos rengas ei ole tekijä. Esimerkki [83] : Tarkastellaan numerorengasta, jonka muoto on jossa ovat kokonaisluvut. Siinä oleva luku 3 on redusoitumaton, koska siinä on vain 4 jakajaa: . Se ei kuitenkaan ole yksinkertainen elementti, kuten tasa-arvo osoittaa: $a+b{\sqrt {5}}i,$ $a,b$ ${\näyttötyyli 3,1,-3,-1}$

\left(2+{\sqrt {5}}i\right)\left(2-{\sqrt {5}}i\right)=9

Numero 3 jakaa tasa-arvon oikean puolen, mutta ei jaa mitään tekijöitä. Tästä tosiasiasta voimme päätellä, että kyseinen rengas ei ole tekijä; ja todellakin, yhtäläisyys osoittaa, että tekijöiden jakaminen redusoitumattomiksi tekijöiksi tässä renkaassa ei ole ainutlaatuinen. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$

Esimerkkejä

Kokonaislukujen rengas on tekijä. Siinä, kuten edellä mainittiin, on kaksi yksikköjakajaa.

Gaussin kokonaisluvut

Gaussin lukujen rengas koostuu kompleksiluvuista , jotka ovat muotoa missä ovat kokonaislukuja. Uniteetilla on neljä jakajaa: Tämä rengas on tekijä, redusoitumattomat alkiot ovat tavallisten alkulukujen ja "yksinkertaisten Gaussien" (esimerkiksi ) murto-osa. Katso Gaussin lukujen primaalisuuskriteeri . $a+bi,$ $a,b$ $1;-1;i;-i.$ $1+i$

Esimerkki luvun 2 hajotuksesta, joka ei ole yksinkertainen Gaussin lukujen renkaassa: - hajotuksen epäyksilöllisyys on tässä ilmeinen, koska se liittyy yhtälön mukaan: $2=(1+i)(1-i)=i(1-i)(1-i)$ $1-i$ $1+i$ ${\näyttötyyli 1-i=(-i)(1+i).}$

Eisensteinin kokonaisluvut

Kokonaislukujen Eisenstein- rengas koostuu seuraavan muodon kompleksiluvuista [84] : $\mathbb {Z} [\omega ]$

z=a+b\omega ,

missä ovat kokonaisluvut, ( ykseyden kuutiojuuri ),

a,b

\omega ={\frac {1}{2}}(-1+i{\sqrt {3}})=e^{2\pi i/3}

Tällä renkaalla on kuusi yksikköjakajaa: (±1, ±ω, ±ω 2 ), se on euklidinen ja siksi tekijällinen. Renkaan pelkistymättömiä elementtejä (ne ovat myös yksinkertaisia elementtejä) kutsutaan Eisensteinin alkuluvuiksi.

Ensiluokkaisuuskriteeri : Eisensteinin kokonaisluku on Eisensteinin alkuluku, jos ja vain jos yksi seuraavista toisensa poissulkevista ehdoista täyttyy: $z=a+b\omega$

$z$ liittyy muodon luonnolliseen alkulukuun $3n-1.$
${\displaystyle |z|^{2}=a^{2}-ab+b^{2))$ (normi ) on muodon tai luonnollinen alkuluku . $z$ $3n$ $3n+1$

Tämä tarkoittaa, että minkä tahansa kokonaisluvun Eisenstein-luvun normi on joko luonnollinen alkuluku tai luonnollisen alkuluvun neliö [84] .

Eisensteinin alkulukuihin liittyvät tai kompleksikonjugaattiluvut ovat myös Eisensteinin alkulukuja.

Polynomien rengas

Algebrassa suuri merkitys on polynomirenkaalla, jonka muodostavat polynomit , joiden kertoimet ovat tietystä kentästä.Yksikkön jakajat ovat tässä nollasta poikkeavia vakioita (nolla-asteen polynomeina). Polynomirengas on euklidinen ja siksi faktoriaalinen. Jos otamme reaalilukujen kentän kenttään , niin kaikki 1. asteen polynomit ja ne 2. asteen polynomit, joilla ei ole todellisia juuria (eli niiden erottaja on negatiivinen) , ovat redusoitumattomia [85] . $K[x]$ $K.$ $K$

Katso myös

Muistiinpanot

↑ 1 2 3 Alkuluku // Matemaattinen tietosanakirja (5 osassa) . - M . : Neuvostoliiton tietosanakirja , 1977. - T. 4.
↑ 1 2 " Argumentit 1:n ensisijaisuuden puolesta ja vastaan Arkistoitu 24. helmikuuta 2021 Wayback Machinessa " .
↑ Sekvenssi A000040 OEIS : ssä . Katso myös alkulukuluettelo
↑ Gardner, Martin . Penrose-laatoista vahvoihin salakirjoihin = Penrose-laatat trapdoor-salauksiin / per. englannista. Yu. A. Danilova. - M . : [[Mir (kustantaja) |]], 1993. - 416 s. - 10 000 kappaletta. — ISBN 5-03-001991-X .
↑ (ranska) Préhistoire de la géométrie: le problème des sources (PDF) (linkki ei saatavilla) . Site de l'IREM de La Reunion. Voir aussi "Les fables d'Ishango, ou l'irresistible tentation de la mathématique-fiction" Arkistoitu 22. joulukuuta 2017 Wayback Machineen , analysoi par O. Keller sur Bibnum
↑ Egyptin yksikkömurtoluvut // Matematiikkasivut. Arkistoitu alkuperäisestä 1. huhtikuuta 2016.
↑ 1 2 Rybnikov K. Euclidin "Alkujen" venäläiset laitokset // Matemaattisten tieteiden edistysaskeleet . - Venäjän tiedeakatemia , 1941. - Nro 9 . - S. 318-321 . (Venäjän kieli)
↑ John J. O'Connor, Edmund F. Robertson. Alkuluvut (englanniksi) . MacTutor .
↑ Luettelo tunnetuista Mersennen alkuluvuista . Upea Internet Mersenne Prime Search . Arkistoitu alkuperäisestä 15. maaliskuuta 2016. (määrätön)
↑ 1 2 3 Apostol, Tom M. Johdatus analyyttiseen lukuteoriaan . - New York: Springer-Verlag, 1976. - xii, 338 sivua s. — ISBN 0387901639 . Arkistoitu 28. huhtikuuta 2020 Wayback Machinessa
↑ 1 2 3 Du Sautoy, Marcus. L'enigma dei numeri primi . - Milano: Rizzoli, 2005. - 606 s. Kanssa. — ISBN 8817008435 .
↑ 1 2 3 Menezes, AJ (Alfred J.), 1965-. Sovellettavan kryptografian käsikirja . - Boca Raton: CRC Press, 1997. - xxviii, 780 sivua s. — ISBN 9780849385230 .
↑ 1 2 Ishmukhametov Sh. T. Luonnollisten lukujen faktorointimenetelmät: oppikirja // Kazan: Kazan University. - 2011. - S. 190 .
↑ Dudley, Underwood (1978), Elementary number theory (2. painos ) , WH Freeman and Co., ISBN 978-0-7167-0076-0 , Osa 2, Lause 2
↑ Katso esimerkiksi David E. Joycen kommentti Elements (Euclid) , Book VII, määritelmät 1 ja 2 Arkistoitu 5. elokuuta 2011 Wayback Machinessa .
↑ 1 2 3 Miksi numero yksi ei ole alkuluku? (Prime Pagesin usein kysyttyjen kysymysten luettelosta), kirjoittanut Chris K. Caldwell. Arkistoitu 19. huhtikuuta 2015 Wayback Machineen
↑ Katso esimerkiksi: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160-188. Variae-havainnot circa series infinitas, Lause 19, s.187. Arkistoitu 5. lokakuuta 2013 Wayback Machinessa
↑ Derbyshire, John (2003), Alkulukulause, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics , Washington, DC: Joseph Henry Press, s. 33, ISBN 978-0-309-08549-6 , OCLC 249210614
↑ David Gries, Jayadev Misra. Lineaarinen seula-algoritmi alkulukujen löytämiseen. – 1978.
↑ Knuth, Donald Ervin, 1938-. Tietokoneohjelmoinnin taito . - Reading, Mass.: Addison-Wesley Pub. Co, ©1973-©1981. - 4 osaa s. — ISBN 0201896842 . Arkistoitu 15. kesäkuuta 2020 Wayback Machinessa
↑ 1 2 Vasilenko, ON (Oleg Nikolaevich). Teoretiko-chislovye algoritmi v kriptografii . — Moskova: MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡, 2006. — 333 sivua s. — ISBN 5940571034 .
↑ B. Schneier. Sovellettu kryptografia. - S. 296-300.
↑ Kormen T., Leiser Ch . Algorithms. Rakentaminen ja analyysi. - M .: MTSNMO, 2002. - S. 765-772.
↑ Crandall R., Pomerance C. Alkuluvut : laskennallinen näkökulma. - Springer, 2005.
↑ Johdatus algoritmeihin . – 2. painos - Cambridge, Mass.: MIT Press, 2001. - xxi, 1180 sivua s. — ISBN 0262032937 . Arkistoitu 29. tammikuuta 2010 Wayback Machinessa
↑ 1 2 3 4 Nesterenko Yu. V. Johdatus kryptografiaan. - Peter, 2001. - 288 s.
↑ Chris Caldwell. Suurin tunnettu ensisijainen vuosimalli: Lyhyt historia (englanniksi) . Prime-sivut . Haettu 8. maaliskuuta 2010. Arkistoitu alkuperäisestä 19. elokuuta 2013.
↑ Jitsuro Nagura. Vähintään yhden alkuluvun sisältävällä välillä (EN) // Proceedings of the Japan Academy. - 1952. - T. 28 , no. 4 . - S. 177-181 . — ISSN 0021-4280 . - doi : 10.3792/pja/1195570997 . Arkistoitu alkuperäisestä 17. marraskuuta 2017.
↑ Kirje arkistoitu 11. kesäkuuta 2015 Wayback Machinessa latinaksi Goldbachista Euleriin , heinäkuu 1730.
↑ Alkulukujen tietueet vuosien mukaan . Haettu 8. maaliskuuta 2010. Arkistoitu alkuperäisestä 19. elokuuta 2013. (määrätön)
↑ Starr, Michelle . Tähän mennessä suurin alkuluku on löydetty ja se vahingoittaa aivojamme , ScienceAlert . Arkistoitu alkuperäisestä 6. tammikuuta 2018. Haettu 6. tammikuuta 2018.
↑ EFF Cooperative Computing Awards arkistoitu 9. marraskuuta 2008 Wayback Machinessa
↑ Julia Rudy. Yhdysvaltalainen professori on määrittänyt suurimman alkuluvun . Vesti.Ru (7. helmikuuta 2013). Haettu 25. helmikuuta 2018. Arkistoitu alkuperäisestä 26. helmikuuta 2018. (määrätön)
↑ 1 2 Sekvenssi A001348 OEIS : ssä
↑ OEIS - sekvenssi A000668 : Mersennen alkuluku
↑ Sekvenssi A000215 OEIS : ssä
↑ Keller, Wilfrid (15. helmikuuta 2015), Fermat-lukujen päätekijät , < http://www.prothsearch.net/fermat.html#Summary > . Haettu 1. maaliskuuta 2016. Arkistoitu 10. helmikuuta 2016 Wayback Machinessa
↑ Violant-y-Holtz, Albert. Maatilan mysteeri. Kolmen vuosisadan haaste matematiikalle. - M .: De Agostini, 2014. - S. 78. - 151 s. — (Matematiikan maailma: 45 nidettä, osa 9). — ISBN 978-5-9774-0625-3 .
↑ OEIS - sekvenssi A003261 _
↑ OEIS - sekvenssi A050918 : Woodall - alkuluvut
↑ OEIS - sekvenssi A002064 _
↑ OEIS - sekvenssi A050920 : Cullen - alkuluvut
↑ OEIS - sekvenssi A080075 _
↑ John Brillhart ; Derrick Henry Lehmer ; John Selfridge . 2^m ± 1:n uudet primaalisuuskriteerit ja faktorisaatiot // Laskennan matematiikka : päiväkirja. - 1975. - huhtikuu ( osa 29 ). - s. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
↑ OEIS - sekvenssi A080076 : Proth - alkuluvut
↑ Caldwell, Chris K. & Cheng, Yuanyou (2005), Determining Mills' Constant and a Note on Honaker's Problem , Journal of Integer Sequences , osa 8 (5.4.1) , < http://www.cs.uwaterloo.ca /journals/JIS/VOL8/Caldwell/caldwell78.html > Arkistoitu 5. kesäkuuta 2011 Wayback Machinessa
↑ Dudley, Underwood (1978), Elementary number theory (2. painos ) , W.H. Freeman and Co., ISBN 978-0-7167-0076-0 , Osa 2, Lemma 5
↑ 1 2 3 Stepanov S. A. Vertailut . - M . : "Tieto", 1975. - 64 s.
↑ Vinberg, 2008 , s. 43.
↑ 1 2 Kurosh A. G. Ryhmien teoria. 3. painos, M.: Nauka, 1967.
↑ A. I. Kostrikin. Johdatus algebraan, osa III. Moskova: Fizmatlit, 2001.
↑ 1 2 3 Vinogradov I. M. Lukuteorian perusteet . - 5. painos - M. - L .: Gostekhizdat, 1952.
↑ Chris Caldwell, Bertrandin postulaatti Arkistoitu 22. joulukuuta 2017 Wayback Machine at Prime Pages -sanastossa.
↑ 1 2 3 4 5 6 7 Nuoren matemaatikon tietosanakirja, 1985 .
↑ Todistus . Pariton luku p , joka ei ole 3:n kerrannainen, on yhtä suuri kuin 1 tai 2 mod 3 ja on yhtä suuri kuin 1, 3, 5 tai 7 mod 8. Kun tämä neliöitetään, saadaan 1 mod 3 ja 1 mod 8. Vähentämällä 1 saadaan 0 modia modulo 3 ja 0 modulo 8. Siksi 3:n kerrannainen ja 8:n kerrannainen; joten se on 24:n kerrannainen $p^{2}-1$
↑ Weisstein, Eric W. Green-Tao -lause Wolfram MathWorld -verkkosivustolla .
↑ Nämä 2 ominaisuutta seuraavat suoraan asteiden summan ja eron laajennuskaavoista
↑ Encyclopedic Dictionary of a Young Mathematicians, 1985 , s. 332.
↑ 1 2 Graham, Ronald L. (1935-). Konkretnaâ matematika : osnovanie informatiki . - Moskova: Kustantaja "Mir", 1998. - 703, [1] s. Kanssa. — ISBN 5030017933 .
↑ Sandifer, Charles Edward, 1951-. Leonhard Eulerin varhainen matematiikka . — Washington, DC: Mathematical Association of America, 2007. — xix, 391 sivua s. — ISBN 0883855593 .
↑ WR Alford, Andrew Granville, Carl Pomerance. Carmichael-lukuja on äärettömän monta // Matematiikan Annals. - 1994. - T. 139 , no. 3 . - S. 703-722 . - doi : 10.2307/2118576 . Arkistoitu alkuperäisestä 26. helmikuuta 2019.
↑ Charles C. Sims. Luettelo p-ryhmistä // Proceedings of the London Mathematical Society. - 1.1.1965. — Voi. s3-15 , iss. 1 . - s. 151-166 . — ISSN 1460-244X . - doi : 10.1112/plms/s3-15.1.151 . Arkistoitu alkuperäisestä 23. joulukuuta 2017.
↑ Jacobson, Nathan, 1910-1999. Perusalgebra . — 2. painos, Dover toim. - Mineola, NY: Dover Publications, 2009. - 2 osaa s. — ISBN 9780486471877 .
↑ Sagalovich Yu.L. Johdatus algebrallisiin koodeihin . - 2011. - 302 s. Arkistoitu 25. joulukuuta 2017 Wayback Machineen
↑ Ferguson, Niels. käytännöllinen kryptografia . - New York: Wiley, 2003. - xx, 410 sivua s. — ISBN 0471223573 . Arkistoitu 10. kesäkuuta 2009 Wayback Machinessa
↑ W. Diffie, M. Hellman. Uusia ohjeita kryptografiassa // IEEE Transactions on Information Theory. - Marraskuu 1976. - T. 22 , no. 6 . - S. 644-654 . — ISSN 0018-9448 . - doi : 10.1109/tit.1976.1055638 . Arkistoitu alkuperäisestä 28. joulukuuta 2017.
↑ Bakhtiari, Maarof, 2012 , s. 175.
↑ Boneh D. Kaksikymmentä vuotta hyökkäyksiä RSA:n salausjärjestelmää vastaan // Notices Amer . Matematiikka. soc. / F. Morgan - AMS , 1999. - Voi. 46, Iss. 2. - s. 203-213. — ISSN 0002-9920 ; 1088-9477
↑ 1 2 RSA Laboratories, RSA Factoring Challenge arkistoitu {{{2}}}. . Julkaistu 18. toukokuuta 2007.
↑ Jones JP, Sato D., Wada H., Wiens D. Alkulukujoukon diofantiiniesitys // Amer . Matematiikka. ma : päiväkirja. - 1976. - Voi. 83 , no. 6 . - s. 449-464 . Arkistoitu alkuperäisestä 31. maaliskuuta 2010.
↑ Juri Matiyasevitš, Diofantiiniyhtälöt 2000-luvulla (pääsemätön linkki)
↑ Matijasevicin polynomi Arkistoitu 6. elokuuta 2010 Wayback Machinessa . Pääsanasto.
↑ Weisstein , Eric W. Landaun ongelmat Wolfram MathWorld -verkkosivustolla .
↑ Tuntematon matemaatikko tekee läpimurron kaksoisalkulukuteoriassa . Käyttöpäivä: 20. toukokuuta 2013. Arkistoitu alkuperäisestä 7. kesäkuuta 2013. (määrätön)
↑ Rajalliset aukot alkulukujen välillä . Haettu 21. toukokuuta 2013. Arkistoitu alkuperäisestä 18. toukokuuta 2013. (määrätön)
↑ Weisstein, Eric W. Legendren hypoteesi (englanniksi) Wolfram MathWorld -verkkosivustolla .
↑ Yleistys mielivaltaisiin puoliryhmiin , katso Kuroshin kirja.
↑ Van der Waerden, 2004 , s. 75.
↑ 1 2 Kurosh, 1973 , s. 82-83.
↑ Leng, 1967 , s. 89.
↑ Van der Waerden, 2004 , s. 77-78.
↑ William W. Adams, Larry Joel Goldstein (1976), Johdanto numeroteoriaan, s. 250, Prentice-Hall, Inc., ISBN 0-13-491282-9
↑ 1 2 Eisensteinin kokonaisluku -- MathWorldistä . Haettu 23. joulukuuta 2017. Arkistoitu alkuperäisestä 15. joulukuuta 2020. (määrätön)
↑ Vinberg E. B. Polynomien algebra. - M . : Koulutus, 1980. - S. 122-124. — 176 s.

Kirjallisuus

Van der Waerden . Algebra. Määritelmät, lauseet, kaavat. - Pietari. : Lan, 2004. - 624 s. — ISBN 5-8114-0552-9 .
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Vinberg EB Fermat'n pieni lause ja sen yleistykset // Matem. valaistuminen - M . : MTSNMO :n kustantaja , 2008. - T. 12. - S. 43-53.
Galperin G. Alkuluvuista // Kvant . - Nro 4 . - S. 9-14.38 .
Henry S. Warren, Jr. Luku 16. Alkulukujen kaavat // Algoritmisia temppuja ohjelmoijille = Hacker's Delight. - M. : "Williams", 2007. - 288 s. — ISBN 0-201-91465-4 .
Karpushina N. Palindromit ja "siirtäjät" alkulukujen joukossa // Tiede ja elämä . - 2010. - Nro 5 . (Venäjän kieli)
Kordemsky B. A. Matemaattinen nerokkuus . - M .: GIFML, 1958. - 576 s.
Kormen T., Leiser C. Luku 33.8. Numeroiden tarkistaminen yksinkertaisuuden vuoksi // Algoritmit. Rakentaminen ja analyysi . - M .: MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R. , Pomerance K. Alkuluvut . Kryptografiset ja laskennalliset näkökohdat = alkuluvut: laskennallinen näkökulma. — M. : URSS , Librocom, 2011. — 664 s. - ISBN 978-5-397-02060-2 .
Kurosh A. G. . Luennot yleisalgebrasta. - 2. painos - Nauka, 1973.
Leng S. Algebra. - M .: Mir, 1967.
Matiyasevitš Yu . Alkulukujen kaavat // Kvant . - 1975. - Nro 5 . - S. 5-13 .
Nesterenko Yu. V. Lukuteorian algoritmiset ongelmat // Johdatus kryptografiaan / Toimittanut V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 .
Zager D. Ensimmäiset 50 miljoonaa alkulukua // Advances in Mathematical Sciences . - Venäjän tiedeakatemia , 1984. - T. 39 , nro 6 (240) . - S. 175-190 . (Venäjän kieli)
Cheryomushkin A. V. Luennot aritmeettisista algoritmeista kryptografiassa . - M. : MTSNMO , 2002. - 104 s. - 2000 kappaletta. — ISBN 5-94057-060-7 . Arkistoitu alkuperäisestä 31. toukokuuta 2013. .
Alkuluku // Nuoren matemaatikon tietosanakirja / Comp. A.P. Savin. - M . : Pedagogia , 1985. - S. 262 -263. — 352 s.
Enrique Gracien. Yksinkertaiset numerot. Pitkä tie äärettömyyteen. - De Agostini, 2014. - T. 3. - 148 s. — (Matematiikan maailma). - ISBN 978-5-9774-0682-6 . - ISBN 978-5-9774-0637-6 .
Bakhtiari M. , Maarof M. A. Serious Security Weakness in RSA Cryptosystem (englanniksi) // IJCSI - 2012. - Vol. 9, Iss. 1, nro 3. - P. 175-178. — ISSN 1694-0814 ; 1694-0784
Crandall R., Pomerance C. Luku 3. Primesien ja komposiittien tunnistaminen. Luku 4. "Primaalisuuden todistaminen" // Alkuluvut : Laskennallinen näkökulma . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .

Linkit

Knop K. Yksinkertaisuuden tavoittelussa .
Prime Pages on tietokanta suurimmista tunnetuista alkuluvuista .
Alku- ja täydellisten lukujen geometria (espanja) .
Visualisointiskripti
Prime Finders -foorumi .

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNF : 11932592t GND : 4047263-2 J9U : 987007538747905171 LCCN : sh85093218 LNB : 000232578 NDL : 00571462 NKC : ph139050

Numeeriset järjestelmät
Laskettavat sarjat	Luonnolliset luvut ( ) $\scriptstyle \mathbb {N}$ Kokonaisluvut ( ) $\scriptstyle \mathbb {Z}$ Järkevä ( ) $\scriptstyle \mathbb {Q}$ Algebrallinen ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Jaksot Laskettavissa Aritmeettinen
Reaaliluvut ja niiden laajennukset	Todellinen ( ) $\scriptstyle \mathbb {R}$ Monimutkainen ( ) $\scriptstyle \mathbb {C}$ Quaternions ( ) $\scriptstyle \mathbb {H}$ Cayleyn numerot (oktaavit, oktoniot) ( ) $\scriptstyle \mathbb {O}$ Sedenions ( ) $\scriptstyle \mathbb {S}$ Vaihtoehdot Kaksinkertainen Hyperkompleksi Superrealistinen Hypermateriaali surrealistinen
Numeeriset laajennustyökalut	Cayley-Dixonin menettely Frobenius-lause Hurwitzin lause
Muut numerojärjestelmät	kardinaaliluvut Järjestysluvut (transfinite, ordinaals) p-adic Yliluonnollisia lukuja intervallinumerot
Katso myös	kaksoisnumerot Irrationaalisia lukuja transsendenttiset numerot numerosäde Biquaternion

Numerot jakautuvuusominaisuuksien mukaan
Yleistä tietoa	Kokonaislukujen faktorointi Jaettavuus yhtenäinen jakaja Jakajatoiminto alkuluku Aritmetiikan peruslause Aritmeettinen luku
Faktorisointilomakkeet	alkuluku Yhdistelmänumero Semiprime suorakaiteen muotoinen numero Sphenic numero Neliötön luku Täysi moninkertainen Täydellinen tutkinto Akilleuksen numero sileä numero Tavallinen numero karkea luku epätavallinen määrä
Rajoitettujen jakajien kanssa	täydellinen numero Hieman riittämättömät määrät Hieman tarpeettomia numeroita Monitoiminen luku Hemitäydelliset luvut hypertäydellinen luku super täydellinen numero yhtenäinen alkuluku puolitäydellinen luku pararytminen numero Erdős-Nicolas numero
Lukuja, joissa on monia jakajia	Ylimääräiset numerot Primitiiviset ylimääräiset numerot Erittäin tarpeettomia numeroita Super Redundant Numbers Todella tarpeettomia lukuja superkomposiittiluku Erittäin superkomposiittiluku outo numero
Liittyy alikvoottisekvensseihin _	pyhä numero ystävällisiä numeroita julkisia numeroita Melko ystävällisiä numeroita
muu	Ei tarpeeksi numeroita kaverin numerot sublimoituja numeroita Malmi numerot nöyrä numero Samat numerot ekstravagantti numero