Prvočíslo

Prvočíslo je přirozené číslo, které má přesně dva odlišné přirozené dělitele . Jinými slovy, přirozené číslo je prvočíslo, pokud je odlišné a beze zbytku dělitelné pouze samo sebou [1] . $p$ $jeden$ $jeden$ $p$

Příklad: číslo je prvočíslo (dělitelné a ), ale není prvočíslo, protože kromě a je dělitelné - má tři přirozené dělitele. $2$ $jeden$ $2$ $čtyři$ $jeden$ $čtyři$ $2$

Studium vlastností prvočísel se zabývá teorií čísel a hlavní teorém aritmetiky v ní určuje jejich ústřední roli: každé překročení celého čísla je buď prvočíslo, nebo může být vyjádřeno jako součin prvočísel, a takové znázornění je unikátní až do pořadí faktorů [1] . Jednotka se neoznačuje jako prvočísla, protože jinak se zadaný expanze stává nejednoznačným [2] : . $jeden$ $x=1\cdot x=1\cdot 1\cdot x=1\cdot 1\cdot ...\cdot 1\cdot x$

Přirozená čísla lze rozdělit do tří tříd: jedna (má jednoho přirozeného dělitele), prvočíslo (má dva přirozené dělitele), složené číslo (má více než dva přirozené dělitele) [1] . Existuje nekonečně mnoho prvočísel a složených čísel.

Posloupnost prvočísel začíná takto:

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

Existují různé algoritmy pro kontrolu, zda je číslo prvočíslo. Například známá metoda počítání dělitelů je v porovnání s jinými primitivní a pomalá.

Prvočísla jsou široce používána v matematice a příbuzných vědách. Mnoho algoritmů informačních technologií , jako jsou asymetrické kryptosystémy , používá faktorizační vlastnosti celých čísel [4] .

Mnoho problémů týkajících se prvočísel zůstává otevřených .

Tam jsou zobecnění představy o prvočísle pro libovolné prsteny a jiné algebraické struktury .

Historie

Není známo, kdy byl pojem prvočísla definován, ale první důkazy pocházejí ze staršího paleolitu, což potvrzuje kost Ishango [5] .

V dochovaných záznamech staroegyptských matematiků existují náznaky, že měli nějaké představy o prvočíslech: například Rhindův papyrus , pocházející z druhého tisíciletí před naším letopočtem, obsahuje tabulku poměrů čísla 2 k , reprezentované součet tří nebo čtyř egyptských zlomků s jednotkou v čitateli a různými jmenovateli. Expanze zlomků, jejichž jmenovatelé mají společného dělitele, jsou podobná, takže Egypťané alespoň znali rozdíl mezi prvočíslem a složeným číslem [6] . $n$

Nejčasnější studie prvočísel, které se k nám dostaly, jsou zásluhou matematiků starověkého Řecka . Vynalezli Eratosthenovo síto , algoritmus pro postupné hledání všech prvočísel od 1 do . Publikováno přibližně v roce 300 př . nl, Euclid 's Elements obsahuje důležité věty o prvočíslech, včetně nekonečna jejich množiny, Euklidova lemmatu a základní věty aritmetiky [7] . $n$

Až do 17. století se v oblasti prvočísel neobjevily žádné významné nové práce [8] . V 1640, Pierre de Fermat formuloval Fermatův malý teorém , pak dokázal Leibniz a Euler , a dva-součet čtverce teorém , a také se domníval, že všechna čísla formy jsou prvočísla, a dokonce dokázal toto až . Ale již pro další Fermatovo číslo Euler prokázal dělitelnost . Nová prvočísla ve Fermatově posloupnosti nebyla dosud nalezena. Ve stejné době francouzský mnich Marin Mersenne zjistil, že posloupnost , kde je prvočíslo, dává také prvočíslo [9] ( Mersennova čísla ). $2^{{2^{n}}}+1$ $n=4$ $2^{2^{5}}+1$ $641$ $2^{p}-1$ $p$

Eulerova práce v teorii čísel obsahovala mnoho informací o prvočíslech. Ukázal, že nekonečná číselná řada je divergentní. V roce 1747 dokázal, že i dokonalá čísla jsou hodnotami posloupnosti , kde faktorem je Mersennovo číslo. V jeho korespondenci s Goldbach , latter říkal jeho slavný dohad o reprezentaci nějakého sudého čísla, začínat od čtyři, součtem dvou připraví [10] . Důkaz domněnky se zatím nenašel. $1/2+1/3+1/5+1/7+1/11+...$ $2^{p-1}(2^{p}-1)$

Od počátku 19. století zaměstnával pozornost mnoha matematiků problém asymptotického rozdělení prvočísel [10] . Legendre a Gauss nezávisle navrhli, že hustota prvočísel je v průměru blízká hodnotě, která je nepřímo úměrná přirozenému logaritmu [11] .

Po dlouhou dobu byla prvočísla považována za málo užitečná mimo čistou matematiku . To se změnilo v 70. letech s příchodem konceptů kryptografie veřejného klíče , ve kterých prvočísla tvořila základ raných šifrovacích algoritmů, jako je RSA [12] .

Rozklad přirozených čísel na součin prvočísel

Reprezentace přirozeného čísla jako součinu prvočísel se nazývá rozklad na prvočísla nebo rozklad čísel . V současné době nejsou známy žádné polynomiální algoritmy pro faktorování čísel, i když nebylo prokázáno, že takové algoritmy neexistují. Kryptosystém RSA a některé další jsou založeny na předpokládané vysoké výpočetní složitosti problému faktorizace. Faktorizace s polynomiální složitostí je teoreticky možná na kvantovém počítači pomocí Shorova algoritmu [13] .

Základní věta aritmetiky

Základní teorém aritmetiky říká, že každé přirozené číslo větší než jedna může být reprezentováno jako součin prvočísel, a to jedinečným způsobem, až do pořadí faktorů [14] . Prvočísla jsou tedy základními „stavebními kameny“ přirozených čísel. Například:

$23244$	$=2\cdot 2\cdot 3\cdot 13\cdot 149$
	$=2^{2}\cdot 3\cdot 13\cdot 149$ . ( označuje druhou mocninu nebo druhou mocninu .) $2^{2}$ $2$

Jak je ukázáno v tomto příkladu, stejný prvočíslo se může objevit vícekrát. Rozklad:

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

číslo n na (konečné číslo) prvočinitele p 1 , p 2 , … , p t nazýváme prvočíselným rozkladem n . Základní větu aritmetiky lze přeformulovat takto: jakýkoli rozklad na prvočísla bude totožný až do řádu dělitelů . V praxi pro většinu čísel existuje mnoho jednoduchých faktorizačních algoritmů, z nichž všechny dávají stejný výsledek [13] .

Jednoduchost jednotky

Většina starověkých Řeků ani neuvažovala o čísle, takže ho nemohli považovat za prvočíslo [15] . Středověkem a renesancí bylo mnoho matematiků uváděno jako první prvočíslo [16] . V polovině 18. století byl Christian Goldbach uveden jako první prvočíslo ve své slavné korespondenci s Leonhardem Eulerem ; Euler sám to však za prvočíslo nepovažoval [17] . V 19. století mnozí matematici ještě považovali číslo za prvočíslo. Například seznam prvočísel Derricka Normana Lemairea , přetištěný v roce 1956, začal jako první prvočíslo. Říká se, že Henri Lebesgue je posledním matematikem, který nazval prvočíslo [18] . Počátkem 20. století začali matematici docházet ke konsenzu o tom, co není prvočíslo, ale spíše tvoří svou vlastní speciální kategorii – „jedničku“ [16] . $jeden$ $jeden$ $jeden$ $jeden$ $jeden$ $10006721$ $jeden$ $jeden$ $jeden$

Pokud je považováno za prvočíslo, pak Euklidova základní věta o aritmetice (zmíněná výše) nebude platit, jak bylo uvedeno na začátku článku. Číslo lze například rozložit na 3 5 a 1 3 5 . Jestliže to bylo prvočíslo, tyto dvě možnosti by byly považovány za různé faktorizace ; následně by se muselo změnit tvrzení této věty [16] . Stejně tak by Eratosthenovo síto nefungovalo správně, kdyby bylo považováno za jednoduché: upravená verze síta, která předpokládá, že jde o prvočíslo, vylučuje všechny faktory, které jsou násobky (tedy všechna ostatní čísla), a na výstupu vytvoří pouze jedno číslo - . Navíc prvočísla mají několik vlastností, které číslo nemá , jako je poměr čísla k jeho odpovídající hodnotě Eulerovy identity nebo součet funkce dělitele [2] . $jeden$ $patnáct$ $jeden$ $patnáct$ $jeden$ $jeden$ $jeden$ $jeden$ $jeden$

Algoritmy pro vyhledávání a rozpoznávání prvočísel

Jednoduché způsoby, jak najít počáteční seznam prvočísel až do určité hodnoty, poskytují síto Eratosthenes , síto Sundaram a síto Atkin [19] .

V praxi je však často nutné místo získání seznamu prvočísel ověřit, zda je dané číslo prvočíslo. Algoritmy, které řeší tento problém, se nazývají testy primality . Existuje mnoho testů polynomiální primality , ale většina z nich je pravděpodobnostních (například Miller-Rabinův test ) a používá se pro potřeby kryptografie [20] . V roce 2002 bylo prokázáno, že obecný problém primálnosti je polynomiálně řešitelný, ale navrhovaný deterministický Agrawal-Kayal-Saksena test má poměrně velkou výpočetní náročnost , což ztěžuje jeho aplikaci v praxi [21] .

Pro některé třídy čísel existují specializované účinné testy prvočíselnosti (viz níže).

Test jednoduchosti

Test primality (neboli test primality) je algoritmus , který po přijetí čísla jako vstupu umožňuje buď nepotvrdit předpoklad o složení čísla, nebo přesně potvrdit jeho primálnost. Ve druhém případě se to nazývá test opravdové primality. Úloha testu primality patří do třídy složitosti P , to znamená, že doba běhu algoritmů pro její řešení závisí polynomiálně na velikosti vstupních dat, což bylo prokázáno v roce 2002 [22] . Vznik polynomiálního algoritmu předpovídala existence certifikátů polynomiální primality a v důsledku toho skutečnost, že problém kontroly primality čísla patřil současně do tříd NP a co-NP .

Stávající algoritmy pro testování čísla na primálnost lze rozdělit do dvou kategorií: testy skutečné primality a testy pravděpodobnosti primality. Výsledkem výpočtů pravdivých testů je vždy fakt jednoduchosti nebo složení čísla. Pravděpodobnostní test ukazuje, zda je číslo s určitou pravděpodobností prvočíslo. Čísla, která splňují test pravděpodobnosti prvočíselnosti, ale jsou složená, se nazývají pseudoprima [23] . Jedním příkladem takových čísel jsou Carmichaelova čísla [24] .

Jedním příkladem opravdových testů primálnosti je Luc-Lehmerův test pro Mersennova čísla . Zjevnou nevýhodou tohoto testu je, že se vztahuje pouze na určité druhy čísel. Mezi další příklady patří příklady založené na Fermatově Malé větě [25]

Pepinův test na Fermatova čísla
Protova věta pro Protova čísla
Agrawal-Kayala-Saxene test , první univerzální, polynomiální, deterministický a nepodmíněný test primality.
Luc-Lehmer-Rieselův test

Stejně jako:

metoda iterace děliče
Wilsonova věta
Pocklingtonovo kritérium
Millerův test
Adleman-Pomerans-Rumeli test , vylepšený [26] Cohenem a Lenstroyem
Test primality pomocí eliptických křivek .

Pravděpodobnostní testy primality zahrnují:

Velká prvočísla

Po mnoho staletí bylo hledání „velkých“ prvočísel v zájmu matematiků. V posledních desetiletích získaly tyto studie praktický význam díky použití takových čísel v řadě šifrovacích algoritmů, jako je RSA [12] .

V sedmnáctém století Marin Mersenne navrhl, že čísla ve tvaru jsou prvočísla (pro n ≤ 257) pouze pro n rovné 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 a 257 [11 ] . Ověření správnosti předpokladu bylo hodně nad tehdejší možnosti. Teprve ve 20. století bylo zjištěno, že hypotéza byla nepravdivá a pravděpodobně učiněna „naslepo“, protože Mersenne nevzal v úvahu tři případy (pro n = 61, 89 a 107); navíc se ukázalo, že čísla odpovídající n = 67 an = 257 jsou složená [11] . $2^{n}-1$

V roce 1876 Eduard Lucas dokázal, že M 127 (39místné číslo) je prvočíslo, zůstalo největším známým prvočíslem až do roku 1951, kdy bylo nalezeno (44 číslic) a o něco později (ze 79 číslic) - poslední prvočíslo, které bylo nalezeno pomocí elektronické kalkulačky. Od té doby byla všechna následující velká prvočísla objevena počítačem: od roku 1952 (kdy SWAC ukázal, že M 521 je prvočíslo), do roku 1996 je našel superpočítač a všechna byla Mersennova prvočísla (nalezeno pomocí Luc-Lehmerova testu , a specifický algoritmus pro taková čísla), kromě čísla , které bylo rekordní v letech 1989 až 1992 [27] . ${\frac {2^{148}+1}{17}}$ $180*(2^{127}-1)^{2}+1$ $391581*2^{216193}-1$

Algoritmy pro získávání prvočísel

Některé problémy v matematice používající faktorizaci vyžadují sérii velmi velkých prvočísel vybraných náhodně. Algoritmus pro jejich získání, založený na postulátu Bertranda (Pro libovolné přirozené číslo n ≥ 2 existuje prvočíslo p v intervalu n < p < 2 n .) [28] :

Algoritmus:

Vstup : přirozené číslo $N$
Řešení (hledejte náhodné prvočíslo P)
1. $P\gets$ Funkce generování libovolného přirozeného čísla na segmentu $[N,2N]$
2. Pokud kompozitní, pak $P$
  1. $P\leftarrow \,P+1$
  2. Pokud pak $P=2N$
    1. $P\leftarrow \,N$
3. Návrat " - náhodné prvočíslo" $P$

Doba řešení problému tímto algoritmem není definována, ale je vysoká pravděpodobnost, že je vždy polynomiální, pokud je dostatek prvočísel a jsou víceméně rovnoměrně rozložena . Pro jednoduchá náhodná čísla jsou tyto podmínky splněny [21] .

Nejúčinnějším prostředkem pro konstrukci prvočísel je mírně upravená Fermatova malá věta [26] .

Nechť N, S jsou lichá přirozená čísla, N-1 = S*R a pro každého prvočíselného dělitele q čísla S existuje celé číslo takové, $A$

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

Potom každý prvočísel p z N splňuje kongruenci

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

Následek. Pokud jsou splněny podmínky Fermatovy věty a jsou splněny , pak N je prvočíslo [26] . $R\leqslant 4S+2$

Ukažme si nyní, jak lze s pomocí posledního tvrzení za daného velkého prvočísla sestrojit podstatně větší prvočíslo . K tomu náhodně vybereme sudé číslo na intervalu a nastavíme . Potom číslo zkontrolujeme na nepřítomnost malých prvočísel dělením malými prvočísly; Otestujme několikrát pomocí Rabinova algoritmu. Pokud se zároveň ukáže, že se jedná o složené číslo, měli byste zvolit novou hodnotu a zopakovat výpočty znovu. To by mělo být provedeno, dokud nebude nalezeno číslo N, které prošlo testem Rabinova algoritmu dostatečně často. V tomto případě existuje naděje, že jde o prvočíslo, a je třeba se pokusit prvočíslost dokázat pomocí testů prvočíslosti [26] . $S$ $N$ $R$ $R\leqslant 4S+2$ $N=SR+1$ $N$ $N$ $N$ $R$ $N$

Nekonečno prvočísel

Existuje nekonečně mnoho prvočísel . Toto tvrzení je označováno jako Euklidova věta podle starověkého řeckého matematika Euklida , protože je mu připisován první známý důkaz tohoto tvrzení. Je známo mnohem více důkazů pro nekonečno prvočísel, včetně Eulerova analytického důkazu , Goldbachova důkazu pomocí Fermatových čísel [29] , Furstenbergova důkazu pomocí obecné topologie a Kummerova elegantního důkazu .

Největší známé prvočíslo

Dlouho se vedou záznamy, které označují největší v té době známá prvočísla [30] . Jeden z rekordů svého času vytvořil Euler , když našel prvočíslo 2 31 − 1 = 2 147 483 647 .

Největší známé prvočíslo k lednu 2019 je Mersennovo číslo M 82 589 933 = 2 82 589 933 − 1 . Obsahuje 24 862 048 desetinných míst ; kniha zaznamenávající toto číslo by měla asi devět tisíc stran. Byl nalezen 7. prosince 2018 jako součást distribuovaného vyhledávání GIMPS pro Mersenne prvočísla . Předchozí největší známé prvočíslo, objevené v prosinci 2017, bylo o 1 612 623 znaků méně [31] .

Mersennova čísla se příznivě liší od zbytku přítomností účinného testu primality : Luc-Lehmerova testu . Mersennova prvočísla díky němu dlouho držela rekord jako největší známá prvočísla.

Za nalezení prvočísel z více než 100 000 000 a 1 000 000 000 desetinných číslic udělil EFF [32] peněžní odměny ve výši 150 000 USD a 250 000 USD [ 33] . EFF již dříve udělil ceny za nalezení prvočísel 1 000 000 a 10 000 000 desetinných míst.

Prvočísla zvláštního druhu

Existuje řada čísel, jejichž primálnost lze efektivně stanovit pomocí specializovaných algoritmů.

Mersennova čísla jsou čísla ve tvaru , kde n je přirozené číslo [34] . Navíc, Mersennovo číslo může být prvočíslo pouze v případě, že n je prvočíslo. Jak bylo uvedeno výše, účinným testem primality je Luc-Lehmerův test [35] . $M_{n}=2^{n}-1$
Fermatova čísla jsou čísla ve tvaru , kde n je nezáporné celé číslo [36] . Účinným testem primality je Pepinův test . K únoru 2015 je známo pouze 5 Fermatových prvočísel (pro n = 0, 1, 2, 3, 4), dalších dvacet osm Fermatových prvočísel (do včetně) se ukázalo být složených [37] , ale nebylo prokázáno, že ostatní prvočísla Farma č . [38] . $F_{n}=2^{2^{n}}+1$ $F_{32}$
Woodallova čísla jsou čísla ve tvaru [39] . Účinným testem primality je Lucas-Lehmer-Riesel test [40] . $W_{n}=n\cdot 2^{n}-1$
Cullen čísla jsou čísla ve tvaru [41] [42] . $C_{n}=n\cdot 2^{n}+1$
Proth čísla jsou čísla ve tvaru , kde k je liché a [43] . Účinným testem primality pro Prothova čísla je Brillhart -Lehmer-Selfridge test [ 44 ] . Cullenova čísla a Fermatova čísla jsou speciálním případem Prothových čísel (pro k = n , respektive pro k = 1 ) [45] . $P=k\cdot 2^{n}+1$ $2^{n}>k$ $n=2^{m}$
Millsova čísla jsou čísla ve tvaru kde je Millsova konstanta [46] . $P_{n}=[A^{3^{n}}],$ $A$

Pro vyhledávání prvočísel určených typů se v současnosti používají distribuované výpočetní projekty GIMPS , PrimeGrid , Ramsey@Home , Seventeen or Bust , Riesel Sieve , Wieferich@Home .

Některé vlastnosti

Jestliže p je prvočíslo a p dělí ab , pak p dělí a nebo b . Důkaz této skutečnosti podal Euklides a je znám jako Euklidovo lemma [7] [47] . Používá se při důkazu základní věty aritmetiky .
Zbytkový kruh je pole právě tehdy, když je jednoduché [48] . $\mathbb {Z} _{n}$ $n$
Charakteristikou každého pole je nula nebo prvočíslo [48] .
Jestliže je prvočíslo a je přirozené, pak je dělitelné ( Fermatova malá věta ) [49] . $p$ $A$ $a^{p}-a$ $p$
Jestliže je konečná grupa, jejíž řád je dělitelný , pak obsahuje prvek řádu ( Cauchyho věta ) [50] . $G$ $|G|$ $p$ $G$ $p$
Jestliže je konečná grupa a je maximální mocninou , která dělí , pak má podgrupu řádu , zvanou Sylowova podgrupa , navíc počet Sylowových podgrup je stejný pro nějaké celé číslo ( Sylowova věta ) [51] . $G$ $p^{n}$ $p$ $|G|$ $G$ $p^{n}$ $pk+1$ $k$
Přirozenost je prvočíslo právě tehdy, když je dělitelná ( Wilsonova věta ) [52] . $p>1$ $(p-1)!+1$ $p$
Jestliže je přirozené číslo, pak existuje prvočíslo takové, že ( Bertrandův postulát ) [53] . $n>1$ $p$ $n<p<2n$
Řada čísel inverzních k prvočíslu diverguje [10] . Navíc v $x\to \infty$ $\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x.$
Jakákoli aritmetická posloupnost tvaru , kde jsou koprimá celá čísla , obsahuje nekonečně mnoho prvočísel ( Dirichletova věta o prvočíslech v aritmetickém postupu ) [54] . $a,a+q,a+2q,a+3q,...$ $a,q>1$
Jakékoli prvočíslo větší než 3 může být reprezentováno jako nebo , kde je nějaké přirozené číslo. Pokud je tedy rozdíl mezi několika po sobě jdoucími prvočísly (pro k>1) stejný, pak je nutně násobkem 6 - například: 251-257-263-269; 199-211-223; 20183-20201-20219. $6 tisíc + 1$ $6k-1$ $k$
Jestliže je prvočíslo, pak je to násobek 24 (platí i pro všechna lichá čísla nedělitelná 3) [55] . $p>3$ $p^{2}-1$
Green-Tao teorém . Existují libovolně dlouhé konečné aritmetické posloupnosti sestávající z prvočísel [56] .
Žádné prvočíslo nemůže vypadat jako , kde n >2, k >1. Jinými slovy, číslo následující za prvočíslem nemůže být druhou mocninou nebo vyšší mocninou se základem větším než 2. Z toho také vyplývá, že pokud má prvočíslo tvar , pak k je prvočíslo (viz Mersennova čísla ) [34 ] . $n^{k}-1$ $2^{k}-1$
Žádné prvočíslo nemůže vypadat jako , kde n >1, k >0. Jinými slovy, číslo předcházející prvočíslu nemůže být krychle nebo vyšší lichá mocnina se základem větším než 1 [57] . $n^{{2k+1}}+1$
Každé prvočíslo (kromě čísel tvaru ) lze reprezentovat jako součet tří čtverců [58] . $8n-1$

Aplikace

Prvočísla jsou základními součástmi v mnoha oblastech matematiky .

Aritmetické funkce

Aritmetické funkce , konkrétně funkce definované na množině přirozených čísel a nabývající hodnot v množině komplexních čísel, hrají v teorii čísel klíčovou roli. Zejména nejdůležitější z nich jsou multiplikativní funkce, to znamená funkce , které mají následující vlastnost: pokud se dvojice skládá z prvočísel, pak nastává rovnost [59] $F$ $(a,b)$

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

Příklady multiplikativních funkcí jsou Eulerova funkce , která sdružuje číslo s počtem přirozených čísel menším než n a je s ním spojeno s prvním a počtem dělitelů n [60] . Hodnota těchto funkcí z mocniny prvočísla: $\phi$ $n$

Eulerova funkce $\phi$ :

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

Funkce děliče :

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

Aritmetické funkce lze snadno vypočítat, když známe hodnoty, které nabývají mocnin prvočísel [59] . Ve skutečnosti z rozkladu přirozeného čísla n

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

to máme

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

a proto, když se vrátíme k problému výpočtu, ukazuje se, že je obvykle jednodušší počítat z každé mocniny prvočíselného dělitele než počítat pomocí obecného vzorce [61] . $f(n)$ $F$ $F$

Například pro zjištění hodnoty Eulerovy funkce z n = 450 = 2 × 3 2 × 5 2 stačí vypočítat $\phi$

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

Modulární aritmetika

V modulární aritmetice hrají prvočísla velmi důležitou roli: prsten zbytku je pole právě tehdy, když n je prvočíslo [48] . Také existence primitivního prstencového kořene je vázána na prvočísla: existuje pouze tehdy, když n je prvočíslo, 1, 2, 4, nebo číslo ve tvaru , kde p je liché. $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$ $p^{n}\circ 2p^{n}$

Jednou z nejdůležitějších vět modulární aritmetiky je Fermatova malá věta [52] . Tato věta říká, že pro libovolné prvočíslo p a libovolné přirozené číslo a máme:

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

nebo pro libovolné prvočíslo p a jakékoli přirozené a nedělitelné p ,

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

Tuto vlastnost lze použít ke kontrole, zda číslo není prvočíslo. Ve skutečnosti, pokud n je takové, že:

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

pro nějaké přirozené a , pak n nemůže být jednoduché [52] . Tuto vlastnost však nelze použít k testování, zda je číslo prvočíslo: existují čísla nazývaná Carmichaelova čísla (nejmenší je 561), pro která to nebude pravda. Carmichaelovo číslo je složené číslo, které je pseudoprvočíslo v každém základním b druhém až n. V roce 1994 William Robert Alford, Andrew Granville a Carl Pomerance ukázali, že takových čísel je nekonečně mnoho [62] .

Teorie grup

Prvočísla také hrají základní roli v algebře . V teorii grup se grupa, ve které je každý prvek mocninou prvočísla p , nazývá p-grupa [63] . P-grupa je konečná právě tehdy, když řád grupy (počet jejích prvků) je mocninou p. Příkladem nekonečné p-grupy je Pruferova p -grupa [64] . Je známo, že p -grupy mají netriviální střed , a proto nemohou být jednoduché (kromě grupy s p prvky); pokud je grupa konečná, navíc všechny normální podgrupy protínají střed netriviálním způsobem.

Příkladem takových grup je cyklická grupa násobení modulo a prvočíslo [65] .

Všechny skupiny řádu p jsou cyklické a proto abelovské ; každá skupina řádu p 2 je také abelovská . Navíc jakákoli konečná abelovská grupa je izomorfní k přímému součinu konečného počtu cyklických p-grup.

Cauchyho věta říká, že je-li řád konečné grupy G dělitelný prvočíslem p, pak G obsahuje prvky řádu p. Tato věta je zobecněna Sylowovými větami [50] .

Šifrovací systém veřejného klíče

Některé kryptografické algoritmy s veřejným klíčem, jako je RSA a Diffie-Hellman key exchange , jsou založeny na velkých prvočíslech (obvykle 1024–2048 bitů). RSA se opírá o předpoklad, že je mnohem snazší (tj. efektivnější) provést násobení dvou (velkých) čísel x a y , než vypočítat koprimá x a y , pokud je znám pouze jejich součin . Výměna klíče Diffie-Hellman je založena na skutečnosti, že existují účinné algoritmy pro umocňování modulo a inverzní operace diskrétního logaritmu je považována za obtížnou [66] [67] . $x\cdot y$

rsa

Obtížnost faktorizace velkých čísel vedla k vývoji první účinné metody kryptografie veřejného klíče , RSA [68] . V tomto kryptografickém systému osoba, která má přijmout zašifrovanou zprávu, vygeneruje klíč: zvolí se dvě různá náhodná prvočísla a daná velikost (obvykle se používají 1024 nebo 2048 bitová čísla). Dále se vypočítá jejich součin , který se nazývá modul . Hodnota Eulerovy funkce se vypočítá z čísla : . Je vybráno celé číslo ( ), které je shodné s hodnotou funkce . Obvykle se jako taková berou malá prvočísla (například Fermatova prvočísla ). Číslo se nazývá veřejný exponent . _ Vypočítá se číslo , nazývané tajný exponent, multiplikativně inverzní k číslu e modulo . Pár je publikován jako veřejný klíč RSA ( veřejný klíč RSA ) . Dvojice hraje roli soukromého klíče RSA a je držena v tajnosti [12] . $p$ $q$ $n=p*q$ $n$ $\phi (n)=(p-1)(q-1)$ $E$ $1<e<\phi (n)$ $\phi(n)$ $E$ $E$ $d$ $\phi(n)$ ${\displaystyle \{e,n\))$ $\{d,\phi (n)\}$

Teoreticky je možné odvodit soukromý klíč z veřejných informací: to v současné době vyžaduje faktorizaci čísel , díky čemuž je bezpečné přenášet zabezpečenou zprávu, pokud prvočísla splňují určité podmínky a jsou „dostatečně velká“. Dosud není známo, zda existují účinné metody pro dešifrování zprávy, které nezahrnují přímý faktorizační útok , ale ukázalo se, že špatný výběr veřejného klíče může učinit systém zranitelnějším vůči takovým útokům [69] . $n$ $n$

V roce 1991 RSA Security zveřejnila seznam semiprimes , nabízející peněžní odměny za faktoring některých z nich, aby prokázala bezpečnost metody a podpořila výzkum v této oblasti: iniciativa nazvaná Challenge RSA Factoring [70] . V průběhu let byla některá z těchto čísel rozložena a u jiných je problém faktorizace stále otevřený; soutěž však skončila v roce 2007 [70] .

Vzorce pro hledání prvočísel

V různých dobách byly činěny pokusy označit výraz, jehož hodnoty pro různé hodnoty proměnných v něm obsažených by byla prvočísla [54] . L. Euler označil polynom , který nabývá prvočíselných hodnot pro n = 0, 1, 2, ..., 40 . Avšak pro n = 41 je hodnota polynomu složené číslo. Lze dokázat, že v jedné proměnné n není žádný polynom , který by nabýval prvočísel pro všechna celá čísla n [54] . P. Fermat navrhl, že všechna čísla tvaru 2 2 k + 1 jsou jednoduchá; Euler však tuto domněnku vyvrátil tím, že dokázal, že číslo 2 2 5 + 1 = 4 294 967 297 je složené [54] . $\textstyle n^{2}-n+41,$

Existují však polynomy, jejichž množina kladných hodnot se pro nezáporné hodnoty proměnných shoduje s množinou prvočísel. Jedním z příkladů je polynom

{\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{\ bigr ]}^{2}-{\bigl [}z+pl(ap)+t(2ap-p^{2}-1)-pm{\bigr ]}^{2}{\bigr \}}\ konec{aligned}}

obsahující 26 proměnných a mající stupeň 25. Nejmenší stupeň pro známé polynomy tohoto typu je 5 se 42 proměnnými; nejmenší počet proměnných je 10 se stupněm asi 1,6·10 45 [71] [72] . Tento výsledek je zvláštním případem diofantinské vlastnosti jakékoli spočetné množiny dokázané Jurijem Matiyasevichem .

Zajímavé je, že výše uvedený polynom, který generuje prvočísla, sám faktorizuje. Všimněte si, že druhý faktor tohoto polynomu (ve složených závorkách) má tvar: jedna mínus součet čtverců. Polynom tedy může nabývat kladných hodnot (pro kladné hodnoty ), pouze pokud je každý z těchto čtverců (to znamená každý polynom v hranatých závorkách) roven nule. V tomto případě bude výraz ve složených závorkách roven 1 [73] . $k$

Otevřené otázky

Stále existuje mnoho otevřených otázek ohledně prvočísel, z nichž nejslavnější byly uvedeny Edmundem Landauem v roce 1912 na pátém mezinárodním matematickém kongresu [74] :

Goldbachův problém ( Landauův první problém ): je pravda, že každé sudé číslo větší než dvě lze reprezentovat jako součet dvou prvočísel?
Druhý Landauův problém : existuje nekonečná množina „ jednoduchých dvojčat “ — dvojic prvočísel, jejichž rozdíl je roven 2 [54] ? V roce 2013 matematik Zhang Yitang z University of New Hampshire [75] [76] dokázal, že existuje nekonečně mnoho dvojic prvočísel, jejichž vzdálenost nepřesahuje 70 milionů. Později James Maynard zlepšil výsledek na 600. V roce 2014 projekt Polymath vedený Terencem Taem tuto druhou metodu poněkud vylepšil tím, že nahradil odhad vzdálenosti 246.
Legendreova domněnka ( třetí Landauův problém ): je pravda, že pro jakékoli přirozené číslo mezi a existuje vždy prvočíslo [77] ? $n$ $n^{2}$ $(n+1)^2$
Čtvrtý Landauův problém : je množina prvočísel tvaru nekonečná , kde je přirozené číslo [54] ? $n^{2}+1$ $n$

Otevřeným problémem je také existence nekonečného počtu prvočísel v mnoha celočíselných posloupnostech, včetně Mersennových čísel [54] , Fibonacciho čísel , Fermatových čísel atd.

Variace a zobecnění

Neredukovatelné a primární prvky

Na začátku článku byla uvedena definice prvočísla: přirozené číslo se nazývá prvočíslo, pokud má právě dva dělitele – jedničku a číslo samotné. Podobný koncept lze zavést v jiných algebraických strukturách; nejčastěji se uvažují komutativní kruhy bez nulových dělitelů ( domény integrity ) [78] [79] . Takové kruhy však mohou mít dělitele jednoty , tvořící multiplikativní skupinu . Například v kruhu celých čísel jsou dva dělitele jednoty: a proto všechna celá čísla, kromě dělitelů jednoty, nemají dva, ale alespoň čtyři dělitele; například číslo 7 má dělitele. To znamená, že zobecnění pojmu prvočíslo musí vycházet z jeho dalších vlastností. $+1$ $-jeden.$ $1;7;-1;-7.$

Analog prvočísla pro oblast integrity je neredukovatelný prvek . který je definován následovně [80] .

Nenulový prvek domény integrity se nazývá neredukovatelný (někdy nerozložitelný ), pokud není dělitelem jednoty a z rovnosti vyplývá, že nebo je dělitelem jednoty. $p$ $p=ab$ $A$ $b$

Pro celá čísla tato definice znamená, že neredukovatelné prvky jsou prvočísla přirozená čísla, stejně jako jejich protiklady.

Z definice vyplývá, že množina dělitelů neredukovatelného prvku se skládá ze dvou částí: všech dělitelů jednoty a součinů všech dělitelů jednoty (těmto součinům se říká asociované s prvky). To znamená, že počet dělitelů neredukovatelného , pokud je konečný, je dvojnásobkem počtu dělitelů jednoty v kruhu. $p$ $p$ $p$ $p,$

Velký význam má analogie hlavní věty aritmetiky , která je ve zobecněné podobě formulována takto [81] :

Prstenec se nazývá faktoriál , jestliže každý nenulový prvek v něm, který není dělitelem jednoty, může být reprezentován jako součin neredukovatelných prvků, a toto zobrazení je jedinečné až do permutace faktorů a jejich asociace (násobení děliteli jednoty ).

Ne každá doména integrity je faktoriální, viz protipříklad . Euklidovský kruh je vždy faktoriál [82] .

Existuje další, užší zobecnění pojmu prvočíslo, nazývané prvočíslo [80] .

Nenulový prvek domény integrity se nazývá jednoduchý , pokud není jednotkovým dělitelem a součin může být dělitelný pouze tehdy, je-li alespoň jeden z prvků nebo je dělitelný . $p$ $ab$ $p$ $A$ $b$ $p$

Primární prvek je vždy neredukovatelný. Pokud je prvek jednoduchý a pak definicí jednoduchého prvku jeden z faktorů, nechť je dělitelný, tj. Pak nebo zmenšením (v oblasti integrity je vždy možné snížení nenulového faktoru) : tedy je dělitelem jednoty. ■ $p$ $p=ab,$ $A,$ $p,$ $a=pq.$ $p=ab=pqb$ $p$ $1=qb,$ $b$

Opak obecně neplatí, neredukovatelný prvek nemusí být jednoduchý, pokud prstenec není faktoriál. Příklad [83] : Uvažujme kruh čísel ve tvaru kde jsou celá čísla. Číslo 3 v něm je neredukovatelné, protože má pouze 4 dělitele: . Nejde však o jednoduchý prvek, o čemž svědčí rovnost: $a+b{\sqrt {5}}i,$ $a,b$ $3,1,-3,-1$

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

Číslo 3 rozděluje pravou stranu rovnosti, ale nedělí žádný z faktorů. Z této skutečnosti můžeme usoudit, že dotyčný prsten není faktoriál; a skutečně, rovnost ukazuje, že rozklad na neredukovatelné faktory v tomto kruhu není jedinečný. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$

Příklady

Okruh celých čísel je faktoriál. Jak bylo uvedeno výše, má dva jednotkové dělitele.

Gaussova celá čísla

Okruh Gaussových čísel se skládá z komplexních čísel ve tvaru , kde jsou celá čísla. Existují čtyři dělitelé jednoty: Tento prstenec je faktoriál, neredukovatelné prvky jsou zlomkem obyčejných prvočísel a „jednoduchých Gaussiánů“ (například ). Viz kritérium prvočíselnosti Gaussova čísla . $a+bi,$ $a,b$ $1;-1;i;-i.$ $1+i$

Příklad rozkladu pro číslo 2, který není v okruhu Gaussových čísel jednoduchý: - nejednoznačnost rozkladu je zde zřejmá, protože je spojeno s , podle rovnosti: $2=(1+i)(1-i)=i(1-i)(1-i)$ $1-i$ $1+i$ $1-i=(-i)(1+i).$

Eisensteinova celá čísla

Eisensteinův kruh celých čísel se skládá z komplexních čísel následujícího tvaru [84] : $\mathbb {Z} [\omega ]$

z=a+b\omega ,

kde jsou celá čísla, ( odmocnina z jednoty ),

a,b

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

Tento prsten má šest jednotkových dělitelů: (±1, ±ω, ±ω 2 ), je euklidovský a tedy faktoriál. Neredukovatelné prvky (jsou to také jednoduché prvky) prstenu se nazývají Eisensteinova prvočísla.

Kritérium prvořadosti : Eisensteinovo celé číslo je Ejzenštejnovým prvočíslem tehdy a pouze tehdy, je-li splněna jedna z následujících vzájemně se vylučujících podmínek: $z=a+b\omega$

$z$ spojené s přirozeným prvočíslem formuláře $3n-1.$
${\displaystyle |z|^{2}=a^{2}-ab+b^{2))$ (norma ) je přirozené prvočíslo tvaru nebo . $z$ $3n$ $3n+1$

To znamená, že normou jakéhokoli celého Eisensteinova čísla je buď prvočíslo přirozené číslo, nebo druhá mocnina prvočísla přirozeného čísla [84] .

Čísla spojená nebo komplexně konjugovaná s Eisensteinovými prvočísly jsou také Eisensteinova prvočísla.

Okruh polynomů

Velký význam v algebře má polynomický okruh tvořený polynomy s koeficienty z určitého oboru , dělitelé jednoty jsou zde nenulové konstanty (jako polynomy nultého stupně). Polynomiální kruh je euklidovský a tedy faktoriální. Vezmeme-li těleso reálných čísel jako těleso , pak všechny polynomy 1. stupně a ty polynomy 2. stupně, které nemají reálné kořeny (to znamená, že jejich diskriminant je záporný) , budou ireducibilní [85] . $K[x]$ $K.$ $K$

Viz také

Poznámky

↑ 1 2 3 Prvočíslo // Matematická encyklopedie (v 5 svazcích) . - M . : Sovětská encyklopedie , 1977. - T. 4.
↑ 1 2 „ Argumenty pro a proti primality 1 Archivováno 24. února 2021 na Wayback Machine “ .
↑ Sekvence A000040 v OEIS . Viz také seznam prvočísel
↑ Gardner, Martin . Od dlaždic Penrose po silné šifry = dlaždice Penrose po šifry Trapdoor / za. z angličtiny. Yu. A. Danilova. - M. : [[Mir (nakladatelství) |]], 1993. - 416 s. — 10 000 výtisků. — ISBN 5-03-001991-X .
↑ (francouzsky) Préhistoire de la géométrie: le problème des sources (PDF) (odkaz není k dispozici) . Místo l'IREM de La Reunion. Voir aussi "Les fables d'Ishango, ou l'irresistible tentation de la mathématique-fiction" Archivováno 22. prosince 2017 na Wayback Machine , analýza par O. Keller sur Bibnum
↑ Egyptské jednotkové zlomky // Mathpages. Archivováno z originálu 1. dubna 2016.
↑ 1 2 Rybnikov K. Ruská vydání Euklidových „Počátků“ // Pokroky v matematických vědách . - Ruská akademie věd , 1941. - č. 9 . - S. 318-321 . (Ruština)
↑ John J. O'Connor, Edmund F. Robertson. Prvočísla (anglicky) . MacTutor .
↑ Seznam známých Mersennových prvočísel . Skvělé internetové vyhledávání Mersenne Prime . Archivováno z originálu 15. března 2016. (neurčitý)
↑ 1 2 3 Apostol, Tom M. Úvod do analytické teorie čísel . - New York: Springer-Verlag, 1976. - xii, 338 stran s. — ISBN 0387901639 . Archivováno 28. dubna 2020 na Wayback Machine
↑ 1 2 3 Du Sautoy, Marcus. Enigma dei numeri primi . - Milano: Rizzoli, 2005. - 606 s. S. — ISBN 8817008435 .
↑ 1 2 3 Menezes, AJ (Alfred J.), 1965-. Příručka aplikované kryptografie . - Boca Raton: CRC Press, 1997. - xxviii, 780 stran s. — ISBN 9780849385230 .
↑ 1 2 Ishmukhametov Sh. T. Metody rozkladu přirozených čísel: učebnice // Kazan: Kazan University. - 2011. - S. 190 .
↑ Dudley, Underwood (1978), Elementární teorie čísel (2. vyd. ) , WH Freeman and Co., ISBN 978-0-7167-0076-0 , oddíl 2, věta 2
↑ Viz například komentář Davida E. Joyce k Elements (Euclid) , Kniha VII, definice 1 a 2 Archivováno 5. srpna 2011 na Wayback Machine .
↑ 1 2 3 Proč jednička není prvočíslo? (ze seznamu často kladených otázek na Prime Pages) od Chrise K. Caldwella. Archivováno 19. dubna 2015 na Wayback Machine
↑ Viz například: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160-188. Variae viewses circa series infinitas, Věta 19, str. 187. Archivováno 5. října 2013 na Wayback Machine
↑ Derbyshire, John (2003), The Prime Number Theorem, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics , Washington, DC: Joseph Henry Press, str. 33, ISBN 978-0-309-08549-6 , OCLC 249210614
↑ David Gries, Jayadev Misra. Algoritmus lineárního síta pro hledání prvočísel. — 1978.
↑ Knuth, Donald Ervin, 1938-. Umění počítačového programování . - Reading, Mass.: Addison-Wesley Pub. Co, ©1973-©1981. - 4 svazky str. — ISBN 0201896842 . Archivováno 15. června 2020 na Wayback Machine
↑ 1 2 Vasilenko, ON (Oleg Nikolajevič). Teoretiko-chislovye algoritmy v kriptografii . — Moskva: MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡, 2006. — 333 stran s. — ISBN 5940571034 .
↑ B. Schneier. Aplikovaná kryptografie. - S. 296-300.
↑ Kormen T., Leiser Ch . Algoritmy. Konstrukce a analýza. - M. : MTSNMO, 2002. - S. 765-772.
↑ Crandall R., Pomerance C. Prvočísla: Výpočetní perspektiva. - Springer, 2005.
↑ Úvod do algoritmů . — 2. vyd. - Cambridge, Mass.: MIT Press, 2001. - xxi, 1180 stran s. — ISBN 0262032937 . Archivováno 29. ledna 2010 na Wayback Machine
↑ 1 2 3 4 Nesterenko Yu.V. Úvod do kryptografie. - Petr, 2001. - 288 s.
↑ Chris Caldwell. Největší známý premiér podle roku: Stručná historie (anglicky) . Hlavní stránky . Získáno 8. března 2010. Archivováno z originálu 19. srpna 2013.
↑ Jitsuro Nagura. Na intervalu obsahujícím alespoň jedno prvočíslo (EN) // Proceedings of the Japan Academy. - 1952. - T. 28 , čís. 4 . - S. 177-181 . — ISSN 0021-4280 . - doi : 10.3792/pja/1195570997 . Archivováno z originálu 17. listopadu 2017.
↑ Dopis archivován 11. června 2015 na Wayback Machine v latině od Goldbacha k Eulerovi, červenec 1730.
↑ Záznamy prvočísel podle roku . Získáno 8. března 2010. Archivováno z originálu 19. srpna 2013. (neurčitý)
↑ Starr, Michelle . Bylo objeveno dosud největší prvočíslo a poškozuje naše mozky , ScienceAlert . Archivováno z originálu 6. ledna 2018. Staženo 6. ledna 2018.
↑ EFF Cooperative Computing Awards Archivováno 9. listopadu 2008 na Wayback Machine
↑ Julia Rudyová. Profesor z USA určil největší prvočíslo . Vesti.Ru (7. února 2013). Staženo 25. února 2018. Archivováno z originálu 26. února 2018. (neurčitý)
↑ 1 2 Sekvence A001348 v OEIS
↑ OEIS sekvence A000668 : Mersennova prvočísla
↑ Sekvence A000215 v OEIS
↑ Keller, Wilfrid (15. února 2015), Prvořadé faktory Fermatových čísel , < http://www.prothsearch.net/fermat.html#Summary > . Získáno 1. března 2016. Archivováno 10. února 2016 na Wayback Machine
↑ Violant-y-Holtz, Albert. Záhada farmy. Tři století trvající výzva k matematice. - M. : De Agostini, 2014. - S. 78. - 151 s. — (Svět matematiky: ve 45 svazcích, svazek 9). — ISBN 978-5-9774-0625-3 .
↑ OEIS sekvence A003261 _
↑ OEIS sekvence A050918 : Woodallova prvočísla
↑ OEIS sekvence A002064 _
↑ OEIS sekvence A050920 : Cullenova prvočísla
↑ OEIS sekvence A080075 _
↑ John Brillhart ; Derrick Henry Lehmer ; John Selfridge . Nová kritéria primality a faktorizace 2^m ± 1 // Matematika počítání : deník. - 1975. - Duben ( 29. díl ). - S. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
↑ OEIS sekvence A080076 : Proth prvočísla
↑ Caldwell, Chris K. & Cheng, Yuanyou (2005), Determining Mills' Constant and a Note on Honaker's Problem , Journal of Integer Sequences vol . 8 (5.4.1) , < http://www.cs.uwaterloo.ca /journals/JIS/VOL8/Caldwell/caldwell78.html > Archivováno 5. června 2011 na Wayback Machine
↑ Dudley, Underwood (1978), Elementární teorie čísel (2. vyd. ) , W. H. Freeman and Co., ISBN 978-0-7167-0076-0 , sekce 2, Lemma 5
↑ 1 2 3 Stepanov S. A. Srovnání . - M. : "Znalosti", 1975. - 64 s.
↑ Vinberg, 2008 , str. 43.
↑ 1 2 Kurosh A. G. Teorie grup. 3. vyd., M.: Nauka, 1967.
↑ A. I. Kostrikin. Úvod do algebry, část III. Moskva: Fizmatlit, 2001.
↑ 1 2 3 Vinogradov I. M. Základy teorie čísel . - 5. vyd. - M. - L .: Gostekhizdat, 1952.
↑ Chris Caldwell, Bertrandův postulát Archivováno 22. prosince 2017 ve slovníku Wayback Machine na Prime Pages .
↑ 1 2 3 4 5 6 7 Encyklopedický slovník mladého matematika, 1985 .
↑ Důkaz . Liché číslo p , které není násobkem 3, se rovná 1 nebo 2 mod 3 a rovná se 1, 3, 5 nebo 7 mod 8. Po umocnění dostaneme 1 mod 3 a 1 mod 8. Odečtením 1 dostaneme 0 mod modulo 3 a 0 modulo 8. Tedy násobek 3 a násobek 8; je tedy násobkem 24 $p^{2}-1$
↑ Weisstein, Eric W. Green-Taoova věta na webu Wolfram MathWorld .
↑ Tyto 2 vlastnosti vyplývají přímo z expanzních vzorců pro součet a rozdíl stupňů
↑ Encyklopedický slovník mladého matematika, 1985 , str. 332.
↑ 1 2 Graham, Ronald L. (1935- ). Konkrétní matematika : osnovanie informací . - Moskva: Nakladatelství "Mir", 1998. - 703, [1] s. S. — ISBN 5030017933 .
↑ Sandifer, Charles Edward, 1951-. Raná matematika Leonharda Eulera . — Washington, DC: Mathematical Association of America, 2007. — xix, 391 stran s. — ISBN 0883855593 .
↑ WR Alford, Andrew Granville, Carl Pomerance. Existuje nekonečně mnoho Carmichaelových čísel // Annals of Mathematics. - 1994. - T. 139 , no. 3 . - S. 703-722 . - doi : 10.2307/2118576 . Archivováno z originálu 26. února 2019.
↑ Charles C. Sims. Enumerating p-Groups // Proceedings of the London Mathematical Society. — 1965-01-01. — Sv. s3-15 , iss. 1 . - S. 151-166 . — ISSN 1460-244X . - doi : 10.1112/plms/s3-15.1.151 . Archivováno z originálu 23. prosince 2017.
↑ Jacobson, Nathan, 1910-1999. Základní algebra . — 2. vyd., Dover ed. - Mineola, NY: Dover Publications, 2009. - 2 svazky s. — ISBN 9780486471877 .
↑ Sagalovič Yu.L. Úvod do algebraických kódů . - 2011. - 302 s. Archivováno 25. prosince 2017 na Wayback Machine
↑ Ferguson, Niels. praktická kryptografie . - New York: Wiley, 2003. - xx, 410 stran s. — ISBN 0471223573 . Archivováno 10. června 2009 na Wayback Machine
↑ W. Diffie, M. Hellman. Nové směry v kryptografii // IEEE Transactions on Information Theory. - Listopad 1976. - T. 22 , no. 6 . - S. 644-654 . — ISSN 0018-9448 . - doi : 10.1109/tit.1976.1055638 . Archivováno z originálu 28. prosince 2017.
↑ Bakhtiari, Maarof, 2012 , str. 175.
↑ Boneh D. Dvacet let útoků na kryptosystém RSA // Notices Amer . Matematika. soc. / F. Morgan - AMS , 1999. - Sv. 46, Iss. 2. - S. 203-213. — ISSN 0002-9920 ; 1088-9477
↑ 1 2 RSA Laboratories, The RSA Factoring Challenge Archived {{{2}}}. . Publikováno 18. května 2007.
↑ Jones JP, Sato D., Wada H., Wiens D. Diofantní reprezentace množiny prvočísel // Amer . Matematika. Po. : deník. - 1976. - Sv. 83 , č. 6 . - str. 449-464 . Archivováno z originálu 31. března 2010.
↑ Yuri Matiyasevich, Diophantine Equations in the XX Century (nepřístupný odkaz)
↑ Matijasevicův polynom Archivováno 6. srpna 2010 na Wayback Machine . První glosář.
↑ Weisstein, Eric W. Landau's Problems on the Wolfram MathWorld website .
↑ Neznámý matematik udělal průlom v teorii dvojčat . Datum přístupu: 20. května 2013. Archivováno z originálu 7. června 2013. (neurčitý)
↑ Ohraničené mezery mezi prvočísly . Získáno 21. května 2013. Archivováno z originálu 18. května 2013. (neurčitý)
↑ Weisstein, Eric W. Legendre's Hypothesis (anglicky) na webu Wolfram MathWorld .
↑ Zobecnění na libovolné pologrupy , viz Kuroshova kniha.
↑ Van der Waerden, 2004 , str. 75.
↑ 1 2 Kurosh, 1973 , str. 82-83.
↑ Leng, 1967 , str. 89.
↑ Van der Waerden, 2004 , str. 77-78.
↑ William W. Adams, Larry Joel Goldstein (1976), Úvod do teorie čísel, str. 250, Prentice-Hall, Inc., ISBN 0-13-491282-9
↑ 1 2 Eisenstein Integer -- z MathWorld . Staženo 23. prosince 2017. Archivováno z originálu 15. prosince 2020. (neurčitý)
↑ Vinberg E. B. Algebra polynomů. - M . : Vzdělávání, 1980. - S. 122-124. — 176 str.

Literatura

Van der Waerden . Algebra. Definice, věty, vzorce. - Petrohrad. : Lan, 2004. - 624 s. — ISBN 5-8114-0552-9 .
Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . - M. : MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Malá věta Vinberga EB Fermata a její zobecnění // Matem. osvícení - M . : Nakladatelství MTSNMO , 2008. - T. 12. - S. 43-53.
Galperin G. Jen o prvočíslech // Kvant . - č. 4 . - S. 9-14 :38 .
Henry S. Warren, Jr. Kapitola 16. Vzorce pro prvočísla // Algoritmické triky pro programátory = Hacker's Delight. - M. : "Williams", 2007. - 288 s. — ISBN 0-201-91465-4 .
Karpushina N. Palindromy a "posouvači" mezi prvočísly // Věda a život . - 2010. - č. 5 . (Ruština)
Kordemsky B. A. Matematická vynalézavost . - M. : GIFML, 1958. - 576 s.
Kormen T., Leiser C. Kapitola 33.8. Kontrola čísel pro jednoduchost // Algoritmy. Konstrukce a analýza . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R. , Pomerance K. Prvočísla . Kryptografické a výpočetní aspekty = prvočísla: výpočetní perspektiva. — M. : URSS , Librocom, 2011. — 664 s. - ISBN 978-5-397-02060-2 .
Kurosh A.G. Přednášky o obecné algebře. - 2. vyd. - Nauka, 1973.
Leng S. Algebra. — M .: Mir, 1967.
Matiyaševič Yu . Vzorce pro prvočísla // Kvant . - 1975. - č. 5 . - S. 5-13 .
Nesterenko Yu. V. Algoritmické problémy teorie čísel // Úvod do kryptografie / Editoval V. V. Yashchenko. - Petr, 2001. - 288 s. - ISBN 5-318-00443-1 .
Zager D. Prvních 50 milionů prvočísel // Pokroky v matematických vědách . - Ruská akademie věd , 1984. - T. 39 , č. 6 (240) . - S. 175-190 . (Ruština)
Cheryomushkin A. V. Přednášky o aritmetických algoritmech v kryptografii . - M. : MTSNMO , 2002. - 104 s. - 2000 výtisků. — ISBN 5-94057-060-7 . Archivováno z originálu 31. května 2013. .
Prvočíslo // Encyklopedický slovník mladého matematika / Komp. A. P. Savin. - M . : Pedagogika , 1985. - S. 262 -263. — 352 s.
Enrique Gracien. Jednoduchá čísla. Dlouhá cesta do nekonečna. - De Agostini, 2014. - T. 3. - 148 s. — (Svět matematiky). - ISBN 978-5-9774-0682-6 . - ISBN 978-5-9774-0637-6 .
Bakhtiari M. , Maarof M. A. Vážná bezpečnostní slabina v RSA Cryptosystem (anglicky) // IJCSI - 2012. - Vol. 9, Iss. 1, č. 3. - S. 175-178. — ISSN 1694-0814 ; 1694-0784
Crandall R., Pomerance C. Kapitola 3. Rozpoznávání prvočísel a kompozitů. Kapitola 4. "Dokazování prvočíselnosti" // Prvočísla: Výpočetní perspektiva . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .

Odkazy

Knop K. Ve snaze o jednoduchost .
The Prime Pages je databáze největších známých prvočísel .
Geometrie prvočísel a dokonalých čísel (španělština) .
Vizualizační skript
Fórum Prime Finders .

Slovníky a encyklopedie

V bibliografických katalozích
BNF : 11932592t GND : 4047263-2 J9U : 987007538747905171 LCCN : sh85093218 LNB : 000232578 NDL : 00571462 NKC : ph139050

Numerické soustavy
Počitatelné sady	Přirozená čísla ( ) $\scriptstyle \mathbb {N}$ celá čísla ( ) $\scriptstyle \mathbb {Z}$ racionální ( ) $\scriptstyle \mathbb {Q}$ algebraické ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Období Vypočitatelný Aritmetický
Reálná čísla a jejich rozšíření	Skutečné ( ) $\scriptstyle \mathbb {R}$ Komplexní ( ) $\scriptstyle \mathbb {C}$ čtveřice ( ) $\scriptstyle \mathbb {H}$ Cayleyova čísla (oktávy, osminky) ( ) $\scriptstyle \mathbb {O}$ sedenions ( ) $\scriptstyle \mathbb {S}$ Alternions Dvojí Hyperkomplex Superreálné Hypermateriál nadreálný
Nástroje pro numerické rozšíření	Cayley-Dixonův postup Frobeniova věta Hurwitzova věta
Jiné číselné soustavy	kardinální čísla Řadové číslovky (překonané, řadové) p-adic Nadpřirozená čísla intervalová čísla
viz také	dvojitá čísla Iracionální čísla transcendentální čísla číselný paprsek Biquaternion

Čísla podle charakteristik dělitelnosti
Obecná informace	Faktorizace celých čísel Dělitelnost unitární dělitel Funkce děliče prvočíslo Základní teorém aritmetiky Aritmetické číslo
Faktorizační formy	prvočíslo Složené číslo Semiprime obdélníkové číslo Sfénické číslo Číslo bez čtverců Plný násobek Perfektní stupeň Achillovo číslo hladké číslo Běžné číslo hrubé číslo neobvyklé číslo
S omezenými děliteli	dokonalé číslo Poněkud nedostatečná čísla Trochu nadbytečná čísla Multiperfektní číslo Hemiperfektní čísla hyperdokonalé číslo super dokonalé číslo unitární prvočíslo polodokonalé číslo pararytmické číslo Erdős-Nicolasovo číslo
Čísla s mnoha děliteli	Přebytečná čísla Primitivní nadbytečná čísla Vysoce nadbytečná čísla Super redundantní čísla Velmi nadbytečná čísla superkompozitní číslo Vysoce superkompozitní číslo podivné číslo
Souvisí s alikvotními sekvencemi	posvátné číslo přátelská čísla veřejná čísla Kvazi přátelská čísla
jiný	Nedostatek čísel čísla kamarádů sublimovaná čísla Rudná čísla skromné číslo Stejné číslice extravagantní číslo