Primtal

Ett primtal är ett naturligt tal som har exakt två distinkta naturliga delare . Ett naturligt tal är med andra ord primtal om det är olikt och delbart utan rester endast av sig självt [1] . $sid$ $ett$ $ett$ $sid$

Exempel: talet är primtal (delbart med och med ), men är inte primtal, eftersom det, förutom och , är delbart med - det har tre naturliga delare. $2$ $ett$ $2$ $fyra$ $ett$ $fyra$ $2$

Studiet av egenskaperna hos primtal är engagerad i talteorin , och aritmetikens huvudsats fastställer deras centrala roll i den: varje heltalsöverskridande är antingen primtal eller kan uttryckas som en produkt av primtal, och en sådan representation är unik upp till ordningen av faktorerna [1] . Enheten hänvisas inte till som primtal, eftersom den angivna expansionen annars blir tvetydig [2] : . $ett$ $x=1\cdot x=1\cdot 1\cdot x=1\cdot 1\cdot ...\cdot 1\cdot x$

Naturliga tal kan delas in i tre klasser: ett (har en naturlig delare), primtal (har två naturliga delare), sammansatt tal (har fler än två naturliga delare) [1] . Det finns oändligt många primtal och sammansatta tal.

Följden av primtal börjar så här:

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

Det finns olika algoritmer för att kontrollera om ett tal är primtal. Till exempel är den välkända divisoruppräkningsmetoden primitiv och långsam i jämförelse med andra.

Primtal används i stor utsträckning inom matematik och relaterade vetenskaper. Många informationsteknologialgoritmer , såsom asymmetriska kryptosystem , använder faktoriseringsegenskaperna hos heltal [4] .

Många problem med primtal är fortfarande öppna .

Det finns generaliseringar av begreppet ett primtal för godtyckliga ringar och andra algebraiska strukturer .

Historik

Det är inte känt när begreppet ett primtal definierades, men de första bevisen går tillbaka till den övre paleolitikum, vilket bekräftas av Ishango-benet [5] .

I forntida egyptiska matematikers bevarade uppgifter finns det antydningar om att de hade några idéer om primtal: till exempel innehåller Rhind-papyrusen , som går tillbaka till det andra årtusendet f.Kr., en tabell över förhållandena mellan talet 2 till , representerad av summan av tre eller fyra egyptiska bråk med en enhet i täljare och olika nämnare. Expansionerna av bråk vars nämnare har en gemensam divisor är liknande, så egyptierna visste åtminstone skillnaden mellan ett primtal och ett sammansatt tal [6] . $n$

De tidigaste studierna av primtal som har kommit ner till oss beror på matematikerna i det antika Grekland . De uppfann sikten av Eratosthenes , en algoritm för att sekventiellt hitta alla primtal från 1 till . Publicerad omkring 300 f.Kr. innehåller Euklids element viktiga satser om primtal, inklusive oändligheten av deras mängd, Euklids lemma och aritmetikens grundsats [7] . $n$

Fram till 1600-talet fanns det inga betydande nya verk inom primtalsområdet [8] . År 1640 formulerade Pierre de Fermat Fermats lilla sats , sedan bevisad av Leibniz och Euler , och tvåkvadratsummasatsen , och antog också att alla tal i formen är primtal, och bevisade till och med detta upp till . Men redan för nästa Fermat-nummer visade Euler delbarhet med . Nya primtal i Fermat-sekvensen har ännu inte hittats. Samtidigt upptäckte den franske munken Marin Mersenne att sekvensen , där är ett primtal, också ger ett primtal [9] ( Mersenne-tal ). $2^{{2^{n}}}+1$ $n=4$ $2^{2^{5}}+1$ $641$ $2^{p}-1$ $sid$

Eulers arbete med talteorin innehöll mycket information om primtal. Han visade att en oändlig talserie är divergerande. 1747 bevisade han att även perfekta tal är värdena för sekvensen , där faktorn är Mersenne-talet. I sin korrespondens med Goldbach uppgav den senare sin berömda gissning om representationen av vilket jämnt tal som helst, med början från fyra, med summan av två primtal [10] . Beviset för gissningen har ännu inte hittats. $1/2+1/3+1/5+1/7+1/11+...$ $2^{p-1}(2^{p}-1)$

Sedan början av 1800-talet har många matematikers uppmärksamhet varit upptagen av problemet med den asymptotiska fördelningen av primtal [10] . Legendre och Gauss föreslog oberoende att tätheten av primtal är i genomsnitt nära ett värde som är omvänt proportionellt mot den naturliga logaritmen [11] .

Under lång tid ansågs primtal vara till liten nytta utanför ren matematik . Detta förändrades på 1970-talet med tillkomsten av begreppen public-key kryptografi , där primtal utgjorde grunden för tidiga krypteringsalgoritmer som RSA [12] .

Nedbrytning av naturliga tal till en produkt av primtal

Representationen av ett naturligt tal som en produkt av primtal kallas nedbrytning till primtal , eller talfaktorisering . För närvarande är inga polynomalgoritmer för att faktorisera tal kända, även om det inte har bevisats att sådana algoritmer inte existerar. RSA -kryptosystemet och några andra är baserade på den förmodade höga beräkningskomplexiteten hos faktoriseringsproblemet. Faktorisering med polynom komplexitet är teoretiskt möjlig på en kvantdator med Shors algoritm [13] .

Grundläggande sats för aritmetik

Aritmetikens grundläggande sats säger att varje naturligt tal större än ett kan representeras som en produkt av primtal, och på ett unikt sätt, upp till faktorernas ordning [14] . Primtal är alltså de elementära "byggstenarna" för naturliga tal. Till exempel:

$23244$	$=2\cdot 2\cdot 3\cdot 13\cdot 149$
	$=2^{2}\cdot 3\cdot 13\cdot 149$ . ( betecknar kvadrat eller andra potens .) $2^{2}$ $2$

Som visas i det här exemplet kan samma primtalare visas flera gånger. Sönderfall:

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

tal n till (finita tal) primtalsfaktorer p 1 , p 2 , … , p t kallas primtalsfaktorisering av n . Den grundläggande satsen för aritmetik kan omformuleras enligt följande: varje nedbrytning till primtal kommer att vara identisk upp till ordningen för divisorer . I praktiken, för de flesta siffror, finns det många enkla faktoriseringsalgoritmer, som alla ger samma resultat [13] .

Enhetens enkelhet

De flesta av de gamla grekerna övervägde inte ens ett tal, så de kunde inte betrakta det som ett primtal [15] . Under medeltiden och renässansen inkluderade många matematiker som första primtal [16] . I mitten av 1700-talet angav Christian Goldbach som det första primtalet i sin berömda korrespondens med Leonhard Euler ; Emellertid ansåg Euler själv inte att det var ett primtal [17] . På 1800-talet ansåg många matematiker fortfarande att ett tal var ett primtal. Till exempel började Derrick Norman Lemaires lista över primtal till tal, omtryckt 1956, med som det första primtal. Det sägs att Henri Lebesgue är den siste matematikern som kallade prime [18] . I början av 1900-talet började matematiker komma till enighet om vad som inte är ett primtal, utan snarare bildar en egen speciell kategori - "ett" [16] . $ett$ $ett$ $ett$ $ett$ $ett$ $10006721$ $ett$ $ett$ $ett$

Om det betraktas som ett primtal, så kommer Euklids grundläggande sats om aritmetik (som nämns ovan) inte att hålla, vilket indikerades i början av artikeln. Till exempel kan ett tal delas upp som 3 5 och 1 3 5 . Om det var ett primtal skulle dessa två alternativ betraktas som olika faktoriseringar ; följaktligen skulle uttalandet av denna sats behöva ändras [16] . På samma sätt skulle Eratosthenes sikt inte fungera korrekt om det ansågs enkelt: en modifierad version av sikten, som antar att det är ett primtal, utesluter alla faktorer som är multipler (det vill säga alla andra tal), och producerar endast ett nummer i utdata - . Dessutom har primtal flera egenskaper som ett tal inte har , såsom förhållandet mellan ett tal och dess motsvarande Euler-identitetsfunktionsvärde eller summan av en divisorfunktion [2] . $ett$ $femton$ $ett$ $femton$ $ett$ $ett$ $ett$ $ett$ $ett$

Algoritmer för att söka och känna igen primtal

Enkla sätt att hitta en första lista med primtal upp till något värde ger sikten av Eratosthenes , sikten av Sundaram och sikten av Atkin [19] .

Men i praktiken, istället för att få en lista med primtal, är det ofta nödvändigt att kontrollera om ett givet tal är primtal. Algoritmer som löser detta problem kallas primatitetstester . Det finns många polynomiska primalitetstester , men de flesta av dem är probabilistiska (till exempel Miller-Rabin-testet ) och används för kryptografi [20] . 2002 bevisades det att det allmänna primaalitetsproblemet är polynomiellt lösbart, men det föreslagna deterministiska Agrawal-Kayal-Saksena-testet har en ganska stor beräkningskomplexitet , vilket gör det svårt att tillämpa det i praktiken [21] .

För vissa klasser av siffror finns det specialiserade effektiva primatitetstester (se nedan).

Enkelhetstest

Ett primalitetstest (eller primalitetstest) är en algoritm som, efter att ha tagit ett tal som indata, gör det möjligt att antingen inte bekräfta antagandet om numrets sammansättning eller att korrekt hävda dess primatitet. I det andra fallet kallas det det sanna primatitetstestet. Primalitetstestets uppgift tillhör komplexitetsklassen P , det vill säga körtiden för algoritmerna för att lösa det beror polynomiellt på storleken på indata, vilket bevisades 2002 [22] . Uppkomsten av en polynomalgoritm förutspåddes av förekomsten av polynomprimalitetscertifikat och , som en konsekvens, av det faktum att problemet med att kontrollera ett tal för primatitet tillhörde klasserna NP och co-NP samtidigt.

Befintliga algoritmer för att testa ett tal för primalitet kan delas in i två kategorier: sanna primalitetstester och probabilistiska primalitetstester. Resultatet av beräkningar av sanna tester är alltid faktumet av enkelhet eller sammansättning av ett tal. Det probabilistiska testet visar om ett tal är primtal med viss sannolikhet. Tal som uppfyller det probabilistiska primalitetstestet, men som är sammansatta, kallas pseudoprimer [23] . Ett exempel på sådana siffror är Carmichael-numren [24] .

Ett exempel på verkliga primatitetstester är Luc-Lehmer-testet för Mersenne-tal . Den uppenbara nackdelen med detta test är att det bara gäller vissa typer av siffror. Andra exempel inkluderar de baserade på Fermats lilla sats [25]

Pepins test för Fermat-siffror
Prots sats för Prots tal
Agrawal-Kayala-Saxene-testet , det första universella, polynomiska, deterministiska och ovillkorliga primalitetstestet.
Luc-Lehmer-Riesel test

Såväl som:

divisor iterationsmetod
Wilsons teorem
Pocklington kriterium
Miller test
Adleman-Pomerans-Rumeli test , förbättrat [26] av Cohen och Lenstroy
Primalitetstest med elliptiska kurvor .

Probabilistiska primalitetstester inkluderar:

Stora primtal

Under många århundraden har sökandet efter "stora" primtal varit av intresse för matematiker. Under de senaste decennierna har dessa studier fått praktisk betydelse på grund av användningen av sådana nummer i ett antal krypteringsalgoritmer, såsom RSA [12] .

På 1600-talet föreslog Marin Mersenne att formens tal är primtal (för n ≤ 257) endast för n lika med 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 och 257 [11 ] . Verifiering av antagandets riktighet var mycket utöver den tidens möjligheter. Först på 1900-talet upptäcktes att hypotesen var falsk och troligen gjord "blint", eftersom Mersenne inte tog hänsyn till tre fall (för n = 61, 89 och 107); dessutom visade det sig att talen som motsvarar n = 67 och n = 257 är sammansatta [11] . $2^{n}-1$

1876 bevisade Eduard Lucas att M 127 (ett 39-siffrigt tal) är ett primtal, det förblev det största kända primtalet fram till 1951, då (44 siffror) hittades och, lite senare, (av 79 siffror) - det sista ett primtal som hittades med hjälp av en elektronisk kalkylator. Sedan dess har alla efterföljande stora primtal upptäckts av dator: från 1952 (när SWAC visade att M 521 var primtal), till 1996 hittades de av en superdator , och alla var Mersenne-primtal (hittades med Luc-Lehmer-testet , en specifik algoritm för sådana siffror), förutom numret , som var ett rekord mellan 1989 och 1992 [27] . ${\frac {2^{148}+1}{17}}$ $180*(2^{127}-1)^{2}+1$ $391581*2^{216193}-1$

Algoritmer för att erhålla primtal

Vissa problem i matematik som använder faktorisering kräver en serie mycket stora primtal som väljs slumpmässigt. Algoritmen för att erhålla dem, baserad på Bertrands postulat (För alla naturliga tal n ≥ 2 finns det ett primtal p i intervallet n < p < 2 n .) [28] :

Algoritm:

Inmatning : naturligt tal $N$
Lösning (sök efter ett slumpmässigt primtal P)
1. $P\får$ Funktionen att generera ett godtyckligt naturligt tal på ett segment $[N,2N]$
2. Om sammansatt, alltså $P$
  1. $P\vänsterpil \,P+1$
  2. Om då $P=2N$
    1. $P\vänsterpil \,N$
3. Returnera " - slumpmässigt primtal" $P$

Tiden för att lösa problemet med denna algoritm är inte definierad, men det finns en stor sannolikhet att det alltid är polynom, så länge det finns tillräckligt med primtal, och de är mer eller mindre jämnt fördelade . För enkla slumptal är dessa villkor uppfyllda [21] .

Det mest effektiva sättet att konstruera primtal är en något modifierad Fermats lilla teorem [26] .

Låt N, S vara udda naturliga tal, N-1 = S*R, och för varje primtal divisor q av S finns ett heltal så att $a$

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

Då uppfyller varje primtal divisor p av N kongruensen

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

Följd. Om villkoren för Fermats sats och är uppfyllda , då är N ett primtal [26] . $R\leqslant 4S+2$

Låt oss nu visa hur man med hjälp av det sista påståendet, givet ett stort primtal , kan konstruera ett betydligt större primtal . För att göra detta väljer vi slumpmässigt ett jämnt tal på intervallet och ställer in . Sedan kontrollerar vi talet för frånvaron av små primtallare genom att dividera det med små primtal; Låt oss testa ett antal gånger med Rabins algoritm. Om det samtidigt visar sig att det är ett sammansatt tal bör du välja ett nytt värde och upprepa beräkningarna igen. Detta bör göras tills ett nummer N hittas som har klarat testet av Rabins algoritm tillräckligt många gånger. I det här fallet finns det hopp som är ett primtal, och man bör försöka bevisa primeness med primeness tester [26] . $S$ $N$ $R$ $R\leqslant 4S+2$ $N=SR+1$ $N$ $N$ $N$ $R$ $N$

Oändlighet av primtal

Det finns oändligt många primtal . Detta påstående kallas Euklids teorem, efter den antika grekiska matematikern Euclid , eftersom det första kända beviset för detta påstående tillskrivs honom. Många fler bevis för oändligheten av primtal är kända, inklusive Eulers analytiska bevis , Goldbachs bevis med Fermat-tal [29] , Furstenbergs bevis med allmän topologi och Kummers eleganta bevis .

Det största kända primtal

Register har hållits under lång tid, vilket markerar de största primtalen som var kända vid den tiden [30] . Ett av rekorden sattes en gång av Euler , efter att ha hittat ett primtal 2 31 − 1 = 2 147 483 647 .

Det största kända primtalet i januari 2019 är Mersenne-talet M 82 589 933 = 2 82 589 933 − 1 . Den innehåller 24 862 048 decimalsiffror ; en bok som registrerar detta nummer skulle ha ungefär nio tusen sidor. Den hittades den 7 december 2018 som en del av den distribuerade GIMPS -sökningen efter Mersenne-primtal . Det tidigare största kända primtalet, upptäckt i december 2017, var 1 612 623 tecken mindre [31] .

Mersenne-tal skiljer sig positivt från resten genom närvaron av ett effektivt primatitetstest : Luc-Lehmer-testet . Tack vare honom har Mersenne primtals länge haft rekordet som de största kända primtalarna.

För att hitta primtal från över 100 000 000 och 1 000 000 000 decimalsiffror tilldelade EFF [32] kontantpriser på 150 000 $ respektive 250 000 $ [33] . EFF har tidigare delat ut priser för att hitta primtal på 1 000 000 och 10 000 000 decimalsiffror.

Primtal av ett speciellt slag

Det finns ett antal siffror vars primäritet kan fastställas effektivt med hjälp av specialiserade algoritmer.

Mersennenummer är nummer av formen , där n är ett naturligt tal [34] . Dessutom kan ett Mersenne-tal endast vara primtal om n är ett primtal. Som nämnts ovan är ett effektivt primatitetstest Luc-Lehmer-testet [35] . $M_{n}=2^{n}-1$
Fermatnummer är nummer av formen , där n är ett icke-negativt heltal [36] . Ett effektivt primalitetstest är Pepins test . Från och med februari 2015 är endast 5 Fermat-primtal kända (för n = 0, 1, 2, 3, 4), nästa tjugoåtta Fermat-primtal (till och med) visade sig vara sammansatta [37] , men det har inte bevisats att andra primtal Farm no [38] . $F_{n}=2^{2^{n}}+1$ $F_{32}$
Woodall-nummer är nummer av formen [39] . Ett effektivt primalitetstest är Lucas-Lehmer-Riesel-testet [40] . $W_{n}=n\cdot 2^{n}-1$
Cullen-nummer är nummer av formen [41] [42] . $C_{n}=n\cdot 2^{n}+1$
Proth-nummer är nummer av formen , där k är udda och [43] . Ett effektivt primalitetstest för Proth-tal är Brillhart -Lehmer-Selfridge-testet [ 44 ] . Cullen-tal och Fermat-nummer är ett specialfall av Proth-tal (för k = n respektive för k = 1 ) [45] . $P=k\cdot 2^{n}+1$ $2^{n}>k$ $n=2^{m}$
Mills-tal är nummer av formen där är Mills-konstanten [46] . $P_{n}=[A^{3^{n}}],$ $A$

För att söka efter primtal av angivna typer används för närvarande de distribuerade datorprojekten GIMPS , PrimeGrid , Ramsey@Home , Seventeen eller Bust , Riesel Sieve , Wieferich@Home .

Vissa egenskaper

Om p är primtal och p delar ab , så delar p a eller b . Beviset för detta faktum gavs av Euklid och är känt som Euklids Lemma [7] [47] . Det används i beviset för aritmetikens grundläggande sats .
En restring är ett fält om och bara om det är enkelt [48] . $\mathbb {Z} _{n}$ $n$
Karakteristiken för varje fält är noll eller ett primtal [48] .
Om är primtal och är naturligt, då är det delbart med ( Fermats lilla sats ) [49] . $sid$ $a$ $a^{p}-a$ $sid$
Om är en finit grupp vars ordning är delbar med , då innehåller den ett ordningselement ( Cauchys sats ) [50] . $G$ $|G|$ $sid$ $G$ $sid$
Om är en finit grupp, och är den maximala potensen som delar , då har den en undergrupp av ordning , som kallas en Sylow-undergrupp , dessutom är antalet Sylow-undergrupper lika för något heltal ( Sylows sats ) [51] . $G$ $p^{n}$ $sid$ $|G|$ $G$ $p^{n}$ $pk+1$ $k$
En naturlig är primtal om och endast om den är delbar med ( Wilsons sats ) [52] . $p>1$ $(p-1)!+1$ $sid$
Om är ett naturligt tal, så finns det ett primtal så att ( Bertrands postulat ) [53] . $n>1$ $sid$ $n<p<2n$
En serie tal invers till primtal divergerar [10] . Dessutom kl $x\till \infty$ $\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x.$
Varje aritmetisk progression av formen , där är coprime heltal , innehåller oändligt många primtal ( Dirichlets sats om primtal i aritmetisk progression ) [54] . $a,a+q,a+2q,a+3q,...$ $a,q>1$
Alla primtal som är större än 3 kan representeras som eller , där är ett naturligt tal. Därför, om skillnaden mellan flera på varandra följande primtal (för k>1) är densamma, så är det nödvändigtvis en multipel av 6 - till exempel: 251-257-263-269; 199-211-223; 20183-20201-20219. $6k+1$ $6k-1$ $k$
Om är primtal, då är det en multipel av 24 (gäller även för alla udda tal som inte är delbara med 3) [55] . $p>3$ $p^{2}-1$
Green-Tao-satsen . Det finns godtyckligt långa ändliga aritmetiska progressioner som består av primtal [56] .
Inget primtal kan se ut som , där n >2, k >1. Med andra ord kan talet efter ett primtal inte vara en kvadrat eller en högre potens med en bas som är större än 2. Av detta följer också att om ett primtal har formen , så är k ett primtal (se Mersennetal ) [34 ] . $n^{k}-1$ $2^{k}-1$
Inget primtal kan se ut som , där n >1, k >0. Med andra ord kan ett tal som föregår ett primtal inte vara en kub eller en högre udda potens med en bas som är större än 1 [57] . $n^{{2k+1}}+1$
Varje primtal (förutom numren i formen ) kan representeras som summan av tre kvadrater [58] . $8n-1$

Applikationer

Primtal är grundläggande komponenter inom många områden av matematiken .

Aritmetiska funktioner

Aritmetiska funktioner , nämligen funktioner som definieras på mängden naturliga tal och tar värden i mängden komplexa tal, spelar en avgörande roll i talteorin. I synnerhet är de viktigaste bland dem multiplikativa funktioner, det vill säga funktioner som har följande egenskap: om ett par består av samprimtal, så sker likheten [59] $f$ $(a,b)$

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

Exempel på multiplikativa funktioner är Euler-funktionen , som associerar ett tal med antalet naturliga tal mindre än n och samprim med det och antalet divisorer av n [60] . Värdet av dessa funktioner från potensen av ett primtal: $\phi$ $n$

Euler funktion $\phi$ :

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

Uppdelningsfunktion :

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

Aritmetiska funktioner kan enkelt beräknas genom att känna till de värden de tar för primtalspotenser [59] . Faktum är att från faktoriseringen av ett naturligt tal n

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

det har vi

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

och därför, för att återgå till beräkningsproblemet, visar det sig att det vanligtvis är lättare att beräkna från varje potens av en primtalsdelare än att beräkna med den allmänna formeln [61] . $f(n)$ $f$ $f$

Till exempel, för att ta reda på värdet på Euler-funktionen från n = 450 = 2 × 3 2 × 5 2 räcker det att beräkna $\phi$

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

Modulär aritmetik

I modulär aritmetik spelar primtal en mycket viktig roll: en restring är ett fält om och endast om n är primtal [48] . Dessutom är förekomsten av en primitiv ringrot knuten till primtal: den existerar endast om n är ett primtal, 1, 2, 4, eller ett tal i formen , där p är udda. $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$ $p^{n}\circ 2p^{n}$

En av de viktigaste satserna inom modulär aritmetik är Fermats lilla sats [52] . Denna sats säger att för alla primtal p och alla naturliga tal a har vi:

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

eller för alla primtal p och alla naturliga a som inte är delbara med p ,

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

Den här egenskapen kan användas för att kontrollera om ett tal inte är primtal. Faktum är att om n är sådant att:

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

för vissa naturliga a , då kan n inte vara enkelt [52] . Den här egenskapen kan dock inte användas för att testa om ett tal är primtal: det finns några tal som kallas Carmichael-tal (den minsta är 561) för vilka detta inte kommer att vara sant. Ett Carmichael-tal är ett sammansatt tal som är ett pseudoprimtal i varje bas b coprime till n. 1994 visade William Robert Alford, Andrew Granville och Carl Pomerance att det finns oändligt många sådana siffror [62] .

Gruppteori

Primtal spelar också en grundläggande roll i algebra . I gruppteorin kallas en grupp där varje element är en potens av ett primtal p -grupp för en p-grupp [63] . En P-grupp är ändlig om och endast om gruppens ordning (antalet av dess element) är en potens av p. Ett exempel på en oändlig p-grupp är Prufer p -gruppen [64] . Det är känt att p -grupper har ett icke-trivialt centrum och därför inte kan vara enkla (förutom en grupp med p - element); om gruppen är finit, skär dessutom alla normala undergrupper centrum på ett icke-trivialt sätt.

Ett exempel på sådana grupper är den cykliska gruppen av multiplikation modulo ett primtal [65] .

Alla grupper av ordningen p är cykliska och därför abeliska ; varje grupp av ordning p 2 är också abelisk . Dessutom är vilken ändlig Abelisk grupp som helst isomorf till en direkt produkt av ett ändligt antal cykliska p-grupper.

Cauchys sats säger att om ordningen för en ändlig grupp G är delbar med ett primtal p, så innehåller G element av ordningen p. Denna sats är generaliserad av Sylows satser [50] .

Public key kryptosystem

Vissa kryptografialgoritmer med offentliga nyckel, som RSA och Diffie-Hellman-nyckelutbyte , är baserade på stora primtal (vanligtvis 1024-2048 bitar). RSA förlitar sig på antagandet att det är mycket lättare (det vill säga effektivare) att utföra multiplikationen av två (stora) tal x och y än att beräkna coprime x och y om bara deras produkt är känd . Diffie-Hellman nyckelutbyte är baserat på det faktum att det finns effektiva algoritmer för exponentieringsmodulo , och den inversa operationen av diskret logaritm anses vara svår [66] [67] . $x\cdot y$

rsa

Svårigheten att faktorisera stora antal ledde till utvecklingen av den första effektiva metoden för kryptografi med offentlig nyckel , RSA [68] . I detta kryptografiska system genererar personen som ska ta emot det krypterade meddelandet en nyckel: två olika slumpmässiga primtal och en given storlek väljs (vanligtvis används 1024- eller 2048- bitars nummer). Vidare beräknas deras produkt , kallad modulen . Värdet på Euler-funktionen beräknas från talet : . Ett heltal ( ) väljs som är coprime med värdet på funktionen . Vanligtvis tas små primtal som sådana (till exempel Fermat primtal ). Numret kallas för en offentlig exponent . Ett tal beräknas , som kallas den hemliga exponenten, multiplikativt inverst till talet e modulo . Paret publiceras som en offentlig RSA- nyckel ( publik RSA-nyckel ) . Paret spelar rollen som en privat RSA -nyckel och hålls hemliga [12] . $sid$ $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)\}$

Det är teoretiskt möjligt att härleda en privat nyckel från offentlig information: detta kräver för närvarande talfaktorisering , vilket gör det säkert att sända ett säkert meddelande om primtalen uppfyller vissa villkor och är "tillräckligt stora". Det är ännu inte känt om det finns effektiva metoder för att dekryptera ett meddelande som inte involverar en direkt faktoriseringsattack , men det har visat sig att dåligt val av offentlig nyckel kan göra systemet mer sårbart för sådana attacker [69] . $n$ $n$

1991 publicerade RSA Security en lista över semiprimes , som erbjuder kontantpriser för att faktorisera några av dem, för att bevisa metodens säkerhet och för att uppmuntra forskning inom detta område: ett initiativ kallat Challenge RSA Factoring [70] . Under årens lopp har några av dessa siffror sönderdelats, och för andra är faktoriseringsproblemet fortfarande öppet; dock avslutades tävlingen 2007 [70] .

Formler för att hitta primtal

Vid olika tillfällen gjordes försök att indikera ett uttryck vars värden för olika värden av variablerna som ingår i det skulle vara primtal [54] . L. Euler angav ett polynom som tar primvärden för n = 0, 1, 2, ..., 40 . Men för n = 41 är polynomets värde ett sammansatt tal. Det kan bevisas att det inte finns något polynom i en variabel n som tar primtal för alla heltal n [54] . P. Fermat föreslog att alla tal i formen 2 2 k + 1 är enkla; Emellertid tillbakavisade Euler denna gissning genom att bevisa att talet 2 2 5 + 1 = 4 294 967 297 är sammansatt [54] . $\textstyle n^{2}-n+41,$

Ändå finns det polynom, vars uppsättning positiva värden, för icke-negativa värden på variablerna, sammanfaller med uppsättningen av primtal. Ett exempel är polynomet

{\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 \}}\ end{aligned}}

som innehåller 26 variabler och har en grad av 25. Den minsta graden för kända polynom av denna typ är 5 med 42 variabler; det minsta antalet variabler är 10 med en grad av cirka 1,6·10 45 [71] [72] . Detta resultat är ett specialfall av den diofantinska egenskapen hos vilken uppsättning som helst som bevisats av Yuri Matiyasevich .

Intressant nog faktoriseras ovanstående polynom, som genererar primtal, själv. Observera att den andra faktorn för detta polynom (inom parentes) har formen: en minus summan av kvadrater. Således kan ett polynom ta positiva värden (för positiva värden ) endast om var och en av dessa kvadrater (det vill säga varje polynom inom hakparenteser) är lika med noll. I det här fallet kommer uttrycket inom parentes att vara lika med 1 [73] . $k$

Öppna frågor

Det finns fortfarande många öppna frågor om primtal, av vilka de mest kända listades av Edmund Landau 1912 vid den femte internationella matematiska kongressen [74] :

Goldbachs problem ( Landaus första problem ): är det sant att varje jämnt tal större än två kan representeras som summan av två primtal?
Landaus andra problem : finns det en oändlig uppsättning " enkla tvillingar " - par av primtal vars skillnad är lika med 2 [54] ? 2013 bevisade matematikern Zhang Yitang vid University of New Hampshire [75] [76] att det finns oändligt många par av primtal, vars avstånd inte överstiger 70 miljoner. Senare förbättrade James Maynard resultatet till 600. 2014 förbättrade Polymath -projektet ledd av Terence Tao den senare metoden något genom att ersätta avståndsuppskattningen med 246.
Legendres gissning ( Landaus tredje problem ): är det sant att det för alla naturliga tal mellan och alltid finns ett primtal [77] ? $n$ $n^{2}$ $(n+1)^2$
Landaus fjärde problem : är uppsättningen av primtal av formen oändlig , där finns ett naturligt tal [54] ? $n^{2}+1$ $n$

Ett öppet problem är också förekomsten av ett oändligt antal primtal i många heltalssekvenser, inklusive Mersenne-tal [54] , Fibonacci-tal , Fermattal , etc.

Variationer och generaliseringar

Irreducible och prime element

I början av artikeln gavs definitionen av ett primtal: ett naturligt tal kallas primtal om det har exakt två delare - en och själva talet. Ett liknande koncept kan introduceras i andra algebraiska strukturer; oftast anses kommutativa ringar utan nolldelare ( integritetsdomäner ) [78] [79] . Sådana ringar kan dock ha enhetsdelare och bildar en multiplikativ grupp . Till exempel, i ringen av heltal finns det två enhetsdelare: och därför har alla heltal, utom enhetsdelare, inte två, utan minst fyra delare; till exempel har talet 7 divisorer.Detta betyder att generaliseringen av begreppet ett primtal måste baseras på dess övriga egenskaper. $+1$ $-ett.$ $1;7;-1;-7.$

Analogen av ett primtal för integritetsområdet är ett irreducerbart element . som definieras enligt följande [80] .

Ett element som inte är noll i integritetsdomänen kallas irreducible (ibland oupplösligt ) om det inte är en enhetsdelare och det följer av jämlikhet att eller är en enhetsdelare. $sid$ $p=ab$ $a$ $b$

För heltal betyder denna definition att de irreducerbara elementen är de naturliga primtalen, såväl som deras motsatser.

Det följer av definitionen att uppsättningen av delare av ett irreducerbart element består av två delar: alla enhetsdelare och produkter av alla enhetsdelare (dessa produkter kallas associerade med element). Det vill säga antalet divisorer av den irreducible , om den är finit, är dubbelt så många som delare av enhet i ringen. $sid$ $sid$ $sid$ $p,$

Av stor betydelse är analogen till aritmetikens huvudsats , som i generaliserad form formuleras enligt följande [81] :

En ring kallas faktoriell om varje element som inte är noll i den som inte är en enhetsdelare kan representeras som en produkt av irreducerbara element, och denna representation är unik upp till en permutation av faktorer och deras association (multiplikation med enhetsdelare ).

Inte varje integritetsdomän är faktoriell, se motexempel . En euklidisk ring är alltid faktoriell [82] .

Det finns en annan, snävare generalisering av begreppet ett primtal, som kallas ett primelement [80] .

Ett element som inte är noll i integritetsdomänen kallas enkel om det inte är en enhetsdelare och produkten kan bara vara delbar med om minst ett av elementen eller är delbar med . $sid$ $ab$ $sid$ $a$ $b$ $sid$

Ett primtal är alltid irreducerbart. Faktum är att om elementet är enkelt och sedan genom definitionen av ett enkelt element en av faktorerna, låt det vara delbart med d.v.s. Då eller, reducerande med (i integritetsdomänen är reduktionen av en faktor som inte är noll alltid möjlig) : det vill säga är en enhetsdelare. ■ $sid$ $p=ab,$ $a,$ $p,$ $a=pq.$ $p=ab=pqb$ $sid$ $1=qb,$ $b$

Det omvända är inte sant i allmänhet; ett irreducerbart element kanske inte är enkelt om ringen inte är faktoriell. Exempel [83] : Betrakta en ring av tal av formen där är heltal. Siffran 3 i den är irreducerbar, eftersom den bara har 4 divisorer: . Det är dock inte ett enkelt element, vilket framgår av jämlikhet: $a+b{\sqrt {5}}i,$ $a,b$ $3,1,-3,-1$

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

Siffran 3 delar den högra sidan av jämlikheten, men delar inte någon av faktorerna. Av detta faktum kan vi dra slutsatsen att ringen i fråga inte är faktoriell; och faktiskt, jämställdheten visar att faktoriseringen till irreducerbara faktorer i denna ring inte är unik. $6=2\cdot 3=(1-i{\sqrt {5)))(1+i{\sqrt {5)))$

Exempel

Heltalsringen är faktoriell. Den har, som nämnts ovan, två enhetsdelare.

Gaussiska heltal

Ringen av Gaussiska tal består av komplexa tal av formen där är heltal. Det finns fyra enhetsdelare: Denna ring är faktoriell, de irreducerbara elementen är bråkdelen av vanliga primtal och "enkla Gausser" (till exempel ). Se Gaussiskt talprimalitetskriterium . $a+bi,$ $a,b$ $1;-1;i;-i.$ $1+i$

Ett exempel på en sönderdelning för talet 2, som inte är enkel i ringen av Gaussiska tal: - det icke-unika i sönderdelningen här är uppenbart, eftersom det är associerat med , enligt likheten: $2=(1+i)(1-i)=i(1-i)(1-i)$ $1-i$ $1+i$ $1-i=(-i)(1+i).$

Eisenstein heltal

Eisenstein- ringen av heltal består av komplexa tal av följande form [84] : $\mathbb {Z} [\omega ]$

z=a+b\omega ,

var är heltal, ( kubroten av enhet ),

a,b

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

Denna ring har sex enhetsdelare: (±1, ±ω, ±ω 2 ), den är euklidisk och därför faktoriell. Irreducerbara element (de är också enkla element) i en ring kallas Eisenstein-primtal.

Primeness-kriterium : Ett Eisenstein-heltal är ett Eisenstein-primtal om och endast om ett av följande ömsesidigt uteslutande villkor är uppfyllt: $z=a+b\omega$

$z$ förknippas med ett naturligt primtal i formen $3n-1.$
${\displaystyle |z|^{2}=a^{2}-ab+b^{2))$ (norm ) är ett naturligt primtal av formen eller . $z$ $3n$ $3n+1$

Detta antyder att normen för alla Eisenstein-tal antingen är ett naturligt primtal eller kvadraten på ett naturligt primtal [84] .

Tal associerade eller komplexa konjugat med Eisenstein-primtal är också Eisenstein-primtal.

Ring av polynom

Av stor betydelse i algebra är polynomringen som bildas av polynom med koefficienter från ett visst fält .Divisorer av enhet är här icke-nollkonstanter (som polynom med grad noll). Polynomringen är euklidisk och därför faktoriell. Om vi tar fältet av reella tal som fältet , då kommer alla polynom av 1:a graden och de polynom av 2:a graden som inte har reella rötter (det vill säga deras diskriminant är negativ) att vara irreducible [85] . $K[x]$ $K.$ $K$

Se även

Anteckningar

↑ 1 2 3 Primtal // Matematisk uppslagsverk (i 5 volymer) . - M . : Soviet Encyclopedia , 1977. - T. 4.
↑ 1 2 " Argument för och emot primaliteten av 1 Arkiverad 24 februari 2021 på Wayback Machine " .
↑ Sekvens A000040 i OEIS . Se även lista över primtal
↑ Gardner, Martin . Från Penrose-plattor till starka chiffer = Penrose-plattor till trapdörr-chiffer / per. från engelska. Yu. A. Danilova. - M . : [[Mir (förlag) |]], 1993. - 416 sid. — 10 000 exemplar. — ISBN 5-03-001991-X .
↑ (franska) Préhistoire de la géométrie: le problème des sources (PDF) (länk ej tillgänglig) . Site de l'IREM de La Reunion. Voir aussi "Les fables d'Ishango, ou l'irresistible tentation de la mathématique-fiction" Arkiverad 22 december 2017 på Wayback Machine , analys av O. Keller sur Bibnum
↑ Egyptiska enhetsbråk // Mathpages. Arkiverad från originalet den 1 april 2016.
↑ 1 2 Rybnikov K. Ryska upplagor av Euclids "Beginnings" // Advances in Mathematical Sciences . - Ryska vetenskapsakademin , 1941. - Nr 9 . - S. 318-321 . (ryska)
↑ John J. O'Connor, Edmund F. Robertson. Primtal (engelska) . MacTutor .
↑ Lista över kända Mersenne-primtal . Bra Internet Mersenne Prime Search . Arkiverad från originalet den 15 mars 2016. (obestämd)
↑ 1 2 3 Apostol, Tom M. Introduktion till analytisk talteori . - New York: Springer-Verlag, 1976. - xii, 338 sidor sid. — ISBN 0387901639 . Arkiverad 28 april 2020 på Wayback Machine
↑ 1 2 3 Du Sautoy, Marcus. L'enigma dei numeri primi . - Milano: Rizzoli, 2005. - 606 sid. Med. — ISBN 8817008435 .
↑ 1 2 3 Menezes, AJ (Alfred J.), 1965-. Handbok för tillämpad kryptografi . - Boca Raton: CRC Press, 1997. - xxviii, 780 sidor sid. — ISBN 9780849385230 .
↑ 1 2 Ishmukhametov Sh. T. Metoder för faktorisering av naturliga tal: lärobok // Kazan: Kazan University. - 2011. - S. 190 .
↑ Dudley, Underwood (1978), Elementär talteori (2nd ed. ) , WH Freeman and Co., ISBN 978-0-7167-0076-0 , Section 2, Theorem 2
↑ Se till exempel David E. Joyces kommentar till Elements (Euclid) , Bok VII, definitionerna 1 och 2 Arkiverad 5 augusti 2011 på Wayback Machine .
↑ 1 2 3 Varför är talet ett inte primtal? (från Prime Pages lista över vanliga frågor) av Chris K. Caldwell. Arkiverad 19 april 2015 på Wayback Machine
↑ Se till exempel: L. Euler. Commentarii academiae scientiarum Petropolitanae 9 (1737), 160-188. Variae observationes circa series infinitas, sats 19, s.187. Arkiverad 5 oktober 2013 på 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, sid. 33, ISBN 978-0-309-08549-6 , OCLC 249210614
↑ David Gries, Jayadev Misra. En linjär sållalgoritm för att hitta primtal. — 1978.
↑ Knuth, Donald Ervin, 1938-. Konsten att programmera datorer . - Reading, Mass.: Addison-Wesley Pub. Co, ©1973-©1981. - 4 band sid. — ISBN 0201896842 . Arkiverad 15 juni 2020 på Wayback Machine
↑ 1 2 Vasilenko, ON (Oleg Nikolaevich). Teoretiko-chislovye algoritmy v kriptografii . — Moskva: MT︠S︡NMO. Moskovskiĭ t︠s︡entr nepreryvnogo matematicheskogo obrazovanii︠a︡, 2006. — 333 sidor sid. — ISBN 5940571034 .
↑ B. Schneier. Tillämpad kryptografi. - S. 296-300.
↑ Kormen T., Leiser Ch . Algorithms. Konstruktion och analys. - M. : MTSNMO, 2002. - S. 765-772.
↑ Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — Springer, 2005.
↑ Introduktion till algoritmer . — 2:a uppl. - Cambridge, Mass.: MIT Press, 2001. - xxi, 1180 sidor sid. — ISBN 0262032937 . Arkiverad 29 januari 2010 på Wayback Machine
↑ 1 2 3 4 Nesterenko Yu. V. Introduktion till kryptografi. - Peter, 2001. - 288 sid.
↑ Chris Caldwell. Den största kända premiären efter år: A Brief History (engelska) . Prime Pages . Hämtad 8 mars 2010. Arkiverad från originalet 19 augusti 2013.
↑ Jitsuro Nagura. På intervallet som innehåller minst ett primtal (EN) // Proceedings of the Japan Academy. - 1952. - T. 28 , nr. 4 . - S. 177-181 . — ISSN 0021-4280 . - doi : 10.3792/pja/1195570997 . Arkiverad från originalet den 17 november 2017.
↑ Brev arkiverat 11 juni 2015 på Wayback Machine på latin från Goldbach till Euler, juli 1730.
↑ Register över primtal efter år . Hämtad 8 mars 2010. Arkiverad från originalet 19 augusti 2013. (obestämd)
↑ Starr, Michelle . Det största primtalet hittills har upptäckts och det skadar våra hjärnor , ScienceAlert . Arkiverad från originalet den 6 januari 2018. Hämtad 6 januari 2018.
↑ EFF Cooperative Computing Awards arkiverade 9 november 2008 på Wayback Machine
↑ Yulia Rudy. En professor från USA har bestämt det största primtalet . Vesti.Ru (7 februari 2013). Hämtad 25 februari 2018. Arkiverad från originalet 26 februari 2018. (obestämd)
↑ 1 2 Sekvens A001348 i OEIS
↑ OEIS -sekvens A000668 : Mersenne - primtal
↑ Sekvens A000215 i OEIS
↑ Keller, Wilfrid (15 februari 2015), Prime Factors of Fermat Numbers , < http://www.prothsearch.net/fermat.html#Summary > . Hämtad 1 mars 2016. Arkiverad 10 februari 2016 på Wayback Machine
↑ Violant-y-Holtz, Albert. Gårdsmysterium. En trehundraårig utmaning för matematik. - M. : De Agostini, 2014. - S. 78. - 151 sid. — (Matematikens värld: i 45 band, band 9). — ISBN 978-5-9774-0625-3 .
↑ OEIS - sekvens A003261 _
↑ OEIS -sekvens A050918 : Woodall primtal
↑ OEIS - sekvens A002064 _
↑ OEIS -sekvens A050920 : Cullen primer
↑ OEIS - sekvens A080075 _
↑ John Brillhart ; Derrick Henry Lehmer ; John Selfridge . Nya primäritetskriterier och faktoriseringar av 2^m ± 1 // Mathematics of Computing : journal. - 1975. - April ( vol. 29 ). - s. 620-647 . - doi : 10.1090/S0025-5718-1975-0384673-1 .
↑ OEIS -sekvens A080076 : Proth primer
↑ Caldwell, Chris K. & Cheng, Yuanyou (2005), Determining Mills' Constant and a Note on Honakers Problem , Journal of Integer Sequences vol 8 (5.4.1) , < http://www.cs.uwaterloo.ca /journals/JIS/VOL8/Caldwell/caldwell78.html > Arkiverad 5 juni 2011 på Wayback Machine
↑ Dudley, Underwood (1978), Elementary number theory (2nd ed. ) , W.H. Freeman and Co., ISBN 978-0-7167-0076-0 , Section 2, Lemma 5
↑ 1 2 3 Stepanov S. A. Jämförelser . - M . : "Kunskap", 1975. - 64 sid.
↑ Vinberg, 2008 , sid. 43.
↑ 1 2 Kurosh A. G. Teori om grupper. 3:e uppl., M.: Nauka, 1967.
↑ A. I. Kostrikin. Introduktion till algebra, del III. Moskva: Fizmatlit, 2001.
↑ 1 2 3 Vinogradov I. M. Talteorins grunder . - 5:e uppl. - M. - L .: Gostekhizdat, 1952.
↑ Chris Caldwell, Bertrands postulat Arkiverad 22 december 2017 på Wayback Machine på Prime Pages ordlista.
↑ 1 2 3 4 5 6 7 Encyclopedic Dictionary of a Young Mathematician, 1985 .
↑ Bevis . Ett udda tal p som inte är en multipel av 3 är lika med 1 eller 2 mod 3 och är lika med 1, 3, 5 eller 7 mod 8. Kvadrering av detta ger 1 mod 3 och 1 mod 8. Subtrahera 1 ger 0 mod modulo 3 och 0 modulo 8. Därför en multipel av 3 och en multipel av 8; därför är det en multipel av 24 $p^{2}-1$
↑ Weisstein, Eric W. Green-Tao Theorem på Wolfram MathWorld -webbplatsen .
↑ Dessa 2 egenskaper följer direkt från expansionsformlerna för summan och skillnaden av grader
↑ Encyclopedic Dictionary of a Young Mathematician, 1985 , sid. 332.
↑ 1 2 Graham, Ronald L. (1935- ). Konkretnaâ matematika : osnovanie informatiki . - Moskva: Publishing House "Mir", 1998. - 703, [1] s. Med. — ISBN 5030017933 .
↑ Sandifer, Charles Edward, 1951-. Leonhard Eulers tidiga matematik . — Washington, DC: Mathematical Association of America, 2007. — xix, 391 sidor sid. — ISBN 0883855593 .
↑ WR Alford, Andrew Granville, Carl Pomerance. Det finns oändligt många Carmichael Numbers // Annals of Mathematics. - 1994. - T. 139 , nr. 3 . - S. 703-722 . - doi : 10.2307/2118576 . Arkiverad från originalet den 26 februari 2019.
↑ Charles C. Sims. Enumerating p-Groups // Proceedings of the London Mathematical Society. — 1965-01-01. — Vol. s3-15 , iss. 1 . - S. 151-166 . — ISSN 1460-244X . - doi : 10.1112/plms/s3-15.1.151 . Arkiverad från originalet den 23 december 2017.
↑ Jacobson, Nathan, 1910-1999. Grundläggande algebra . — 2:a uppl., Dover uppl. - Mineola, NY: Dover Publications, 2009. - 2 volymer sid. — ISBN 9780486471877 .
↑ Sagalovich Yu.L. En introduktion till algebraiska koder . - 2011. - 302 sid. Arkiverad 25 december 2017 på Wayback Machine
↑ Ferguson, Niels. praktisk kryptografi . - New York: Wiley, 2003. - xx, 410 sidor sid. — ISBN 0471223573 . Arkiverad 10 juni 2009 på Wayback Machine
↑ W. Diffie, M. Hellman. Nya anvisningar inom kryptografi // IEEE Transactions on Information Theory. - November 1976. - T. 22 , nr. 6 . - S. 644-654 . — ISSN 0018-9448 . - doi : 10.1109/tit.1976.1055638 . Arkiverad från originalet den 28 december 2017.
↑ Bakhtiari, Maarof, 2012 , sid. 175.
↑ Boneh D. Tjugo år av attacker mot RSA-kryptosystemet // Notices Amer . Matematik. soc. / F. Morgan - AMS , 1999. - Vol. 46, Iss. 2. - S. 203-213. — ISSN 0002-9920 ; 1088-9477
↑ 1 2 RSA Laboratories, The RSA Factoring Challenge Arkiverad {{{2}}}. . Publicerad 18 maj 2007.
↑ Jones JP, Sato D., Wada H., Wiens D. Diofantisk representation av uppsättningen primtal // Amer . Matematik. mån. : journal. - 1976. - Vol. 83 , nr. 6 . - S. 449-464 . Arkiverad från originalet den 31 mars 2010.
↑ Yuri Matiyasevich, Diophantine Equations in the XX Century (otillgänglig länk)
↑ Matijasevics polynom Arkiverad 6 augusti 2010 på Wayback Machine . Prime-ordlistan.
↑ Weisstein, Eric W. Landaus problem på Wolfram MathWorld -webbplatsen .
↑ Okänd matematiker får genombrott inom tvillingprimteori . Datum för åtkomst: 20 maj 2013. Arkiverad från originalet den 7 juni 2013. (obestämd)
↑ Begränsade luckor mellan primtal . Hämtad 21 maj 2013. Arkiverad från originalet 18 maj 2013. (obestämd)
↑ Weisstein, Eric W. Legendre's Hypothesis (engelska) på Wolfram MathWorld- webbplatsen .
↑ Generalisering till godtyckliga semigrupper , se Kuroshs bok.
↑ Van der Waerden, 2004 , sid. 75.
↑ 1 2 Kurosh, 1973 , sid. 82-83.
↑ Leng, 1967 , sid. 89.
↑ Van der Waerden, 2004 , sid. 77-78.
↑ William W. Adams, Larry Joel Goldstein (1976), Introduktion till talteori, sid. 250, Prentice-Hall, Inc., ISBN 0-13-491282-9
↑ 1 2 Eisenstein Integer--från MathWorld . Hämtad 23 december 2017. Arkiverad från originalet 15 december 2020. (obestämd)
↑ Vinberg E. B. Polynomens algebra. - M . : Utbildning, 1980. - S. 122-124. — 176 sid.

Litteratur

Van der Waerden . Algebra. Definitioner, satser, formler. - St Petersburg. : Lan, 2004. - 624 sid. — ISBN 5-8114-0552-9 .
Vasilenko O. N. Talteoretiska algoritmer i kryptografi . - M. : MTSNMO , 2003. - 328 sid. — ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Vinberg EB Fermats lilla sats och dess generaliseringar // Matem. upplysning - M . : Förlag av MTSNMO , 2008. - T. 12. - S. 43-53.
Galperin G. Bara om primtal // Kvant . - Nr 4 . - S. 9-14.38 .
Henry S. Warren, Jr. Kapitel 16. Formler för primtal // Algoritmiska knep för programmerare = Hacker's Delight. - M. : "Williams", 2007. - 288 sid. — ISBN 0-201-91465-4 .
Karpushina N. Palindromer och "skiftningar" bland primtal // Science and Life . - 2010. - Nr 5 . (ryska)
Kordemsky B. A. Matematisk uppfinningsrikedom . - M. : GIFML, 1958. - 576 sid.
Kormen T., Leiser C. Kapitel 33.8. Kontrollera siffror för enkelhet // Algoritmer. Konstruktion och analys . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R. , Pomerance K. Primtal. Kryptografiska och beräkningsaspekter = primtal: ett beräkningsperspektiv. — M. : URSS , Librocom, 2011. — 664 sid. - ISBN 978-5-397-02060-2 .
Kurosh A. G. . Föreläsningar om allmän algebra. - 2:a upplagan - Nauka, 1973.
Leng S. Algebra. — M .: Mir, 1967.
Matiyasevich Yu . Formler för primtal // Kvant . - 1975. - Nr 5 . - S. 5-13 .
Nesterenko Yu. V. Algoritmiska problem med talteori // Introduktion till kryptografi / Redigerad av V. V. Yashchenko. - Peter, 2001. - 288 sid. - ISBN 5-318-00443-1 .
Zager D. De första 50 miljoner primtalen // Framsteg inom matematiska vetenskaper . - Ryska vetenskapsakademin , 1984. - T. 39 , nr 6 (240) . - S. 175-190 . (ryska)
Cheryomushkin A. V. Föreläsningar om aritmetiska algoritmer i kryptografi . - M. : MTSNMO , 2002. - 104 sid. - 2000 exemplar. — ISBN 5-94057-060-7 . Arkiverad från originalet den 31 maj 2013. .
Primtal // Encyclopedic Dictionary of a Young Mathematician / Komp. A.P. Savin. - M . : Pedagogy , 1985. - S. 262 -263. — 352 sid.
Enrique Gracien. Enkla siffror. Lång väg till oändligheten. - De Agostini, 2014. - T. 3. - 148 sid. — (Matematikens värld). - ISBN 978-5-9774-0682-6 . - ISBN 978-5-9774-0637-6 .
Bakhtiari M. , Maarof M. A. Serious Security Weakness in RSA Cryptosystem (engelska) // IJCSI - 2012. - Vol. 9, Iss. 1, nr 3. - S. 175-178. — ISSN 1694-0814 ; 1694-0784
Crandall R., Pomerance C. Kapitel 3. Att känna igen primtal och kompositer. Kapitel 4. "Primality Proving" // Prime Numbers: A Computational Perspective . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .

Länkar

Knop K. In Pursuit of Simplicity .
Prime Pages är en databas med de största kända primtalen .
Primtal och perfekta tals geometri (spanska) .
Visualiseringsskript
Prime Finders Forum .

Ordböcker och uppslagsverk

I bibliografiska kataloger
BNF : 11932592t GND : 4047263-2 J9U : 987007538747905171 LCCN : sh85093218 LNB : 000232578 NDL : 00571462 NKC : ph139050

Numeriska system
Räknebara set	Naturliga tal ( ) $\scriptstyle \mathbb {N}$ Heltal ( ) $\scriptstyle \mathbb {Z}$ Rationell ( ) $\scriptstyle \mathbb {Q}$ Algebraisk ( ) $\scriptstyle {\overline {\mathbb {Q} }}$ Perioder Beräknarbar Aritmetisk
Reella tal och deras anknytningar	Riktig ( ) $\scriptstyle \mathbb {R}$ Komplex ( ) $\scriptstyle \mathbb {C}$ Kvaternioner ( ) $\scriptstyle \mathbb {H}$ Cayley-tal (oktaver, oktonjoner) ( ) $\scriptstyle \mathbb {O}$ Sedenioner ( ) $\scriptstyle \mathbb {S}$ Ändringar Dubbel Hyperkomplex Superrealistiskt Hypermaterial surrealistiskt
Numeriska förlängningsverktyg	Cayley-Dixon procedur Frobenius teorem Hurwitz teorem
Andra nummersystem	grundtal Ordningstal (transfinita, ordningstal) p-adic Övernaturliga siffror intervallnummer
se även	dubbla siffror Irrationella siffror transcendentala tal nummerstråle Biquaternion

Tal efter delbarhetsegenskaper
Allmän information	Faktorisering av heltal Delbarhet enhetsdelare Delningsfunktion primtal Grundläggande sats för aritmetik Aritmetiskt tal
Faktoriseringsformer	primtal Sammansatt tal Semiprime rektangulärt tal Sfeniskt tal Kvadratlöst tal Full multipel Perfekt examen Achilles nummer jämnt antal Vanligt nummer grovt antal ovanligt antal
Med begränsade delare	perfekt nummer Lite otillräckliga siffror Lite överflödiga siffror Multiperfekt nummer Hemiperfekta siffror hyperperfekt siffra super perfekt nummer enhetligt primtal semiperfekt nummer pararytmiskt tal Erdős-Nicolas nummer
Tal med många delare	Överskjutande siffror Primitiva överskottstal Mycket redundanta nummer Superredundanta nummer Enormt överflödiga siffror superkompositnummer Ett mycket supersammansatt tal konstigt nummer
Relaterat till alikvotsekvenser	heligt nummer vänliga siffror offentliga nummer Kvasivänliga siffror
Övrig	Inte tillräckligt med siffror kompisnummer sublimerade tal Malmnummer ödmjukt nummer Lika siffror extravagant nummer