Numero primo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
ho aggiunto una tabella preso dal sito del ling della parola "tabella" e cambiato un po' la spiegazione Etichette: Annullato Modifica visuale |
Annullata la modifica 146551467 di 2A01:E11:5400:7630:110E:D0EC:6B0B:C007 (discussione) mi sembra fosse meglio prima Etichetta: Annulla |
||
| (13 versioni intermedie di 11 utenti non mostrate) | |||
Riga 2:
In [[matematica]], un '''numero primo''' (in breve anche '''primo''') è un [[numero intero]] positivo che abbia esattamente due [[Divisore|divisori]] distinti. In modo equivalente si può definire come un [[numero naturale]] maggiore di 1 che sia [[divisore|divisibile]] solamente per [[1 (numero)|1]] e per sé stesso; al contrario, un numero maggiore di 1 che abbia più di due divisori è detto [[numero composto|composto]]. Ad esempio 2, 3 e 5 sono primi mentre 4 e 6 non lo sono perché sono divisibili rispettivamente anche per 2 e per 2 e 3. L'unico numero primo [[numeri pari e dispari|pari]] è 2, in quanto tutti gli altri numeri pari sono divisibili per 2.
La [[successione (matematica)|successione]] dei numeri primi comincia con [[2 (numero)|2]], [[3 (numero)|3]], [[5 (numero)|5]], [[7 (numero)|7]], [[11 (numero)|11]], [[13 (numero)|13]], [[17 (numero)|17]], [[19 (numero)|19]], [[23 (numero)|23]], [[29 (numero)|29]], [[31 (numero)|31]], [[37 (numero)|37]], [[41 (numero)|41]], [[43 (numero)|43]], [[47 (numero)|47]], [[53 (numero)|53]], [[59 (numero)|59]], [[61 (numero)|61]], [[67 (numero)|67]], [[71 (numero)|71]], [[73 (numero)|73]], [[79 (numero)|79]], [[83 (numero)|83]], [[89 (numero)|89]], [[97 (numero)|97]], [[101 (numero)|101]], [[103 (numero)|103]], [[107 (numero)|107]], [[109 (numero)|109]], [[113 (numero)|113]], [[127 (numero)|127]], [[131 (numero)|131]], [[137 (numero)|137]], [[139 (numero)|139]]...<ref>{{Cita web|url=https://oeis.org/A000040|titolo=The on-line encyclopedia of integer sequences|editore=The OEIS Foundation|lingua=en|accesso=28 dicembre 2018|urlarchivio=https://web.archive.org/web/20180129172600/https://oeis.org/A000040|dataarchivio=29 gennaio 2018|urlmorto=no}}</ref>
Quello di numero primo è uno dei concetti basilari della [[teoria dei numeri]], la parte della matematica che studia i [[numero intero|numeri interi]]: l'importanza sta nella possibilità di costruire con essi, attraverso la moltiplicazione, tutti gli altri numeri interi, nonché l'unicità di tale [[fattorizzazione]]. I primi sono inoltre [[infinito (matematica)|infiniti]] e la loro distribuzione è tuttora oggetto di molte ricerche.
Riga 747 ⟶ 11:
== Storia ==
Non è noto quando sia stato definito il concetto di numero primo, tuttavia un segnale che fa supporre una qualche consapevolezza della diversità di tali numeri è testimoniato dall'[[Osso d'Ishango]], un reperto osseo datato al [[Paleolitico superiore]], in cui compaiono dei segni rappresentanti i numeri primi compresi tra 10 e 20. Per trovare un altro segno di questa consapevolezza bisogna recarsi in [[Mesopotamia]] e aspettare il [[II millennio a.C.|secondo millennio a.C.]]; a tale periodo appartengono infatti alcune tavolette contenenti le soluzioni di alcuni problemi aritmetici che, per essere svolti, richiedono una buona conoscenza della fattorizzazione in primi.<ref>{{cita libro|autore=[[Otto Eduard Neugebauer|Otto Neugebauer]]|titolo=Le scienze esatte nell'antichità|editore=Feltrinelli|città=Milano|anno=1974|capitolo=Capitolo 2|
[[File:Oxyrhynchus papyrus with Euclid's Elements.jpg|thumb|left|Un frammento degli ''Elementi'' di Euclide rinvenuto a [[Ossirinco]].]]
Riga 753 ⟶ 17:
[[File:Pierre de Fermat.jpg|thumb|[[Pierre de Fermat]]]]
I secoli seguenti registrarono un certo disinteresse per lo studio dei numeri primi<ref>{{cita web|autore=John J. O'Connor|autore2=Edmund F. Robertson|url=
Altri risultati vennero ottenuti da Eulero nel corso del [[XVIII secolo|diciottesimo secolo]]: tra di essi vi sono la [[limite di una successione|divergenza]] della [[serie (matematica)|serie]] infinita <sup>1</sup>⁄<sub>2</sub> + <sup>1</sup>⁄<sub>3</sub> + <sup>1</sup>⁄<sub>5</sub> + <sup>1</sup>⁄<sub>7</sub> + <sup>1</sup>⁄<sub>11</sub> + ..., in cui gli addendi sono gli inversi dei numeri primi, e il cosiddetto [[formula prodotto di Eulero|prodotto di Eulero]], una formula che evidenzia il legame dei primi con la [[serie armonica]].<ref>{{cita|Du Sautoy|p. 149|Sautoy}}.</ref> Nella corrispondenza di Eulero con [[Christian Goldbach]], quest'ultimo formulò inoltre la famosa [[congettura di Goldbach]], ancora oggi non dimostrata, che riguarda la rappresentazione dei numeri naturali pari come somma di numeri primi.<ref>{{cita|Apostol|p. 9|Apostol}}.</ref>
Dall'inizio dell'[[XIX secolo|Ottocento]], l'attenzione di molti matematici si rivolse allo studio della distribuzione [[stima asintotica|asintotica]] dei primi, ossia allo studio dell'andamento della funzione che conta i primi minori o uguali a ''x''.<ref>{{cita|Apostol|p. 8|Apostol}}.</ref> [[Adrien-Marie Legendre|Legendre]] e [[Carl Friedrich Gauss|Gauss]] congetturarono indipendentemente che tale funzione [[limite di una funzione|tende]], al crescere di ''x'', a ''x'' / ln(''x''), dove ln(''x'') indica il [[logaritmo naturale]] di ''x''.<ref>{{cita|Du Sautoy|capitolo 2|Sautoy}}.</ref> Nel
I numeri primi restarono confinati nell'ambito della matematica pura fino agli [[Anni 1970|anni settanta]], quando venne sviluppato il concetto di [[Crittografia asimmetrica|crittografia a chiave pubblica]]; il primo algoritmo di questo tipo, l'[[RSA (crittografia)|RSA]], sfrutta infatti la difficoltà di [[fattorizzazione|fattorizzare]] numeri grandi formati da due soli fattori primi. Per questo motivo, ha assunto una notevole importanza anche la ricerca di numeri primi sempre più grandi. A partire dal
== Prime proprietà ==
[[File:Sieve of Eratosthenes animation.gif|thumb|upright=1.4|Applicazione del [[crivello di Eratostene]] per trovare i numeri primi minori o uguali a 120.]]
Il più piccolo numero primo è 2; tutti gli altri sono [[numeri pari e dispari|dispari]], in quanto ogni numero pari è divisibile per 2. Nel passato 1 era a volte considerato un numero primo: ad esempio [[Derrick Norman Lehmer]] lo incluse nella sua tavola dei numeri primi pubblicata nel
Un metodo per verificare se un numero ''n'' è primo si definisce ''[[test di primalità]]''. Un metodo che discende direttamente dalla definizione è controllare che non sia diviso da nessun numero minore di ''n'' o, in modo più efficiente, da nessun primo minore di ''n''. Ad esempio, per provare che 11 è primo, basta osservare che non è diviso da 2, 3, 5 e 7 (che sono i primi minori di 11).
Riga 831 ⟶ 95:
:<math>\pi(x)\sim\frac{x}{\ln x}.</math><ref>Con questa espressione si intende che il [[limite (matematica)|limite]] del rapporto tra queste due espressioni tende a 1 quando ''x'' tende a infinito.</ref>
Il tentativo di dimostrare questa congettura attraversò tutto l'Ottocento; i primi risultati furono ottenuti tra il
:<math>A\leq \frac{\pi(x)}{\frac{x}{\ln x}} \leq B</math>
per ''x'' sufficientemente grande.<ref>{{cita|Ingham|p. 4 e 14|Ingham}}.</ref> Riuscì anche a provare che, se il [[limite (matematica)|limite]] del rapporto esiste, allora esso deve essere 1.<ref>{{cita|Ingham|p. 4 e 20|Ingham}}.</ref>
Una dimostrazione fu invece trovata nel
[[File:Primi-nlnn.svg|thumb|left|upright=1.4|Confronto tra l{{'}}''n''-esimo numero primo (in blu) e ''n'' · ln ''n'' (in rosso), per ''n'' tra 0 e 10000.]]
Gauss aveva introdotto anche una stima più precisa, utilizzando la funzione [[logaritmo integrale]]:
Riga 841 ⟶ 105:
:<math>\pi(x)\sim\frac{}{}\mathrm{Li}(x)=\int_2^x \frac{1}{\ln u}\mathrm{d}u.</math><ref>{{cita|Ingham|p. 3|Ingham}}.</ref>
Nel
:<math> \pi(x)-\mathrm{Li}(x) = O \left(x \mathrm{e}^{-a\sqrt{\ln x}}\right)=O\left(\frac{x}{(\ln x)^m}\right)</math>
per una costante positiva ''a'' e ogni intero ''m''; tale risultato è stato leggermente migliorato nel corso degli anni.<ref>{{cita|Ingham|p. xi|Ingham}}.</ref> Inoltre, nel
:<math> \pi(x) - \mathrm{Li}(x) = O\left(\sqrt x \ln x\right). </math><ref>{{cita|Ingham|p. 83 e 84|Ingham}}.</ref>
Una forma equivalente al teorema dei numeri primi è che ''p<sub>n</sub>'', l{{'}}''n''-esimo numero primo, è ben approssimato da ''n'' ln(''n''). In effetti, ''p<sub>n</sub>'' è strettamente maggiore di questo valore, come è stato dimostrato da [[J. Barkley Rosser]] nel
:<math>p_n>n(\ln n+\ln\ln n -1),~</math>
per ''n'' ≥ 2.<ref>{{cita pubblicazione | autore = P. Dusart | anno = 1999 | titolo = The k^(th) Prime is Greater than k(lnk+lnlnk-1)
=== Intervalli tra i numeri primi ===
Riga 869 ⟶ 133:
mentre il valore successivo, 6!+7=727, è primo.<ref group="N">Si noti tuttavia che in generale non è vero che il numero successivo è primo: ad esempio, se ''n'' è dispari, allora N!+(''N''+1) è divisibile per 2.</ref> Si noti comunque che esistono modi più "efficienti" per costruire intervalli senza numeri primi; ad esempio invece di (''N'' + 1)! + 1 si può considerare il prodotto dei numeri primi minori di ''N'' + 2.
Dal teorema dei numeri primi discende facilmente che l'intervallo [[Valore atteso|atteso]] tra due numeri primi consecutivi ''p<sub>n</sub>'' e ''p''<sub>''n''+1</sub> ha lunghezza ln(''p<sub>n</sub>''); tuttavia questi intervalli sono talvolta molto più grandi e talvolta molto più piccoli. Sugli intervalli corti, la [[congettura dei numeri primi gemelli|congettura dei primi gemelli]] afferma esattamente che l'intervallo è il minimo possibile infinite volte. Questa congettura è tuttora aperta, ma grazie al lavoro di [[Zhang Yitang]] (annunciato nel 2013, e basato sull'approccio di [[Daniel Goldston|Goldston]], [[János Pintz|Pintz]] e [[Cem Yıldırım|Yıldırım]]<ref>{{cita pubblicazione | autore = D.A. Goldston|autore2=J. Pintz|autore3=Y. Yilidrim| titolo = Primes in tuples. II. | rivista =
Sul problema opposto, degli intervalli lunghi, ci si aspetta che tali intervalli siano di ordine ln<sup>2</sup> ''p<sub>n</sub>'', o, più precisamente, che
:<math>0<\limsup_{n\rightarrow\infty}\frac{p_{n+1}-p_{n}}{\ln^2n}\ll1,</math><ref name = Pintz>{{cita web| autore = J. Pintz| titolo = Landau's problems on primes. | url = http://www.renyi.hu/~pintz/pjapr.pdf|accesso=14 gennaio 2011}}</ref>
mentre i migliori risultati dimostrati sono
:<math>\limsup_{n\rightarrow\infty}\frac{p_{n+1}-p_{n}}{\ln p_n(\ln\ln p_n)(\ln\ln\ln\ln p_n)/\ln\ln\ln p_n}> 0</math><ref>{{cita pubblicazione | autore = K. Ford | autore2 = B. Green | autore3 = S. Konyagin| autore4 = J. Maynard | autore5= T. Tao| titolo =
e
:<math>p_{n+1}-p_n=O\left(p_n^{\frac{21}{40}}\right),</math><ref>{{cita pubblicazione | autore = R. C. Baker|autore2=G. Harman|autore3=J. Pintz | titolo = The difference between consecutive primes, II. | rivista =
dovuti rispettivamente a [[Kevin Ford|Ford]], [[Ben Green|Green]], [[Sergej Konjagin|Konjagin]], Maynard e [[Terence Tao|Tao]] e a Pintz.
Un altro risultato classico, seppur più debole di quelli appena riportati, è il [[postulato di Bertrand]] (che in realtà è un teorema, essendo stato dimostrato da [[Pafnutij L'vovič Čebyšëv|Čebyšëv]] nel
:<math>p_n<2^n.</math>
Riga 944 ⟶ 208:
:<math>a^{n}\not\equiv a\mod n</math>
per qualche intero ''a'', allora ''n'' non può essere primo. Tuttavia questa proprietà non può essere usata per controllare se un numero è primo: esistono infatti alcuni numeri, detti [[numero di Carmichael|numeri di Carmichael]] (il più piccolo dei quali è 561), che verificano questa proprietà per ogni ''a'' pur non essendo primi. Nel
=== Numeri ''p''-adici ===
Riga 978 ⟶ 242:
== Polinomi e progressioni aritmetiche ==
È stato dimostrato da [[Adrien-Marie Legendre|Legendre]] alla fine del [[XVIII secolo|Settecento]]<ref>{{cita|Boyer|p. 565|Boyer}}.</ref> che nessun [[polinomio]] a coefficienti interi può assumere valori soltanto primi: infatti, se esistesse un polinomio ''P''(''n'') di questo tipo, si avrebbe ''P''(1) = p per qualche primo ''p'' e quindi ''P''(1) ≡ 0 mod ''p''. Ma ''P''(1) ≡ ''P''(1+''kp'') mod ''p'' per ogni intero ''k'', e quindi ''P''(1+''kp'') dovrebbe assumere infinite volte il valore ''p'' (perché i multipli di ''p'' non possono essere primi). Tuttavia questo è assurdo, perché nessun polinomio può assumere uno stesso valore un numero di volte maggiore del proprio grado.<ref>{{cita libro|cognome=Stark|nome=Harold|titolo=An introduction to number theory|editore=The MIT Press|città=Cambridge| edizione=10|anno=1998|p=61|
Alcuni polinomi sembrano assumere valori primi "più spesso" degli altri: ad esempio [[Eulero]] notò che il polinomio di secondo grado <math>n^2+n+41</math> produce numeri primi per ogni valore di ''n'' compreso tra 0 e 39; tuttavia, sebbene circa un terzo dei valori che questa funzione assume nei primi 10 milioni siano primi,<ref>{{cita|Devlin|p. 73|Devlin}}.</ref> non è stato ancora dimostrato che ne esistano infiniti. Più in generale, non c'è alcun polinomio in una sola variabile e di grado maggiore di uno di cui sia stato dimostrato che assume infiniti valori primi. Diversa è la situazione per i polinomi in due variabili: Dirichlet dimostrò che questo avviene per ogni [[forma quadratica]] <math>ax^2+bxy+cy^2</math> (a patto che ''a'', ''b'' e ''c'' siano coprimi e che la forma non sia il quadrato di un polinomio di primo grado),<ref>{{cita|Davenport|p. 33|Davenport}}.</ref> mentre nel
[[File:Primi=3mod4.svg|thumb|upright=1.4|Frazione dei numeri primi [[aritmetica modulare|congrui]] a 3 modulo 4.]]
A differenza di quanto accade per i polinomi di grado più alto, [[Peter Gustav Lejeune Dirichlet|Dirichlet]] dimostrò nel
È noto inoltre che, se ''n'' e ''k'' sono coprimi, il rapporto tra ''M'' e i primi minori di ''M'' che sono congrui a ''k'' [[aritmetica modulare|modulo]] ''n'' tende a <math>1/\phi(n)</math> per ''M'' che tende all'infinito, ovvero i primi tendono a dividersi equamente tra le <math>\phi(n)</math> progressioni di ragione ''n'' che contengono più di un primo.<ref>{{cita|Apostol|p. 149|Apostol}}.</ref>
Sebbene non esistano progressioni aritmetiche i cui valori siano soltanto numeri primi, nel
Tali teoremi non sono tuttavia ''costruttivi'', ovvero non permettono di determinare esplicitamente delle progressioni arbitrariamente lunghe; la più lunga sequenza di primi (attualmente conosciuta) che sono termini consecutivi di una progressione aritmetica è composta da 26 numeri.<ref>{{cita web|autore=[[Jens Kruse Andersen]]|url=http://primerecords.dk/aprecords.htm|titolo=Primes in Arithmetic Progression Records|accesso=28 giugno 2014|lingua=en}}</ref> È stato anche congetturato che esistano sequenze arbitrariamente lunghe di questo tipo tali che tra due termini della progressione non ci siano altri numeri primi, e la più lunga sequenza di primi di questo tipo finora trovata comprende 10 termini.<ref>{{cita pubblicazione | autore = H. Dubner|autore2=T. Forbes|autore3=N. Lygeros|autore4=M. Mizony|autore5=H. Nelson|autore6=P. Zimmermann | anno = 2002 | titolo = Ten consecutive primes in arithmetic progression | rivista = [[Mathematics of Computation]] | volume = 71 | pp = 1323-1328 | url = http://www.ams.org/mcom/2002-71-239/S0025-5718-01-01374-6/home.html | accesso = 14 gennaio 2011 }}</ref><ref>{{cita web|autore=[[Jens Kruse Andersen]]|url=http://primerecords.dk/cpap.htm|titolo=The Largest Known CPAP's|accesso=28 giugno 2014}}</ref>
Riga 1 008 ⟶ 272:
Alla congettura di Goldbach ne è legata un'altra, più debole e ora dimostrata, che afferma che ogni numero dispari è la somma di tre numeri primi. Questa ''ex''-congettura è comunemente nota con il nome di [[congettura debole di Goldbach]].
Mentre la congettura di Goldbach sembra molto lontana dall'essere risolta, la seconda ha conosciuto diversi progressi nel corso degli anni, culminati nella dimostrazione completa data da [[Harald Helfgott]] nel
Sono noti anche altri risultati, sebbene molto più deboli. Usando il [[postulato di Bertrand]] si può dimostrare che ogni intero maggiore di 6 può essere scritto come somma di primi distinti. Inoltre, se ''p<sub>n</sub>'' è l{{'}}''n''-esimo numero primo, allora almeno uno tra ''p<sub>n</sub>'', ''p<sub>n</sub>'' − 1 e ''p<sub>n</sub>'' + 1 può essere scritto come
Riga 1 020 ⟶ 284:
== Principali problemi aperti ==
Molte congetture riguardanti i numeri primi non sono ancora state dimostrate. La più importante tra queste è senza dubbio l'[[ipotesi di Riemann]], uno dei problemi aperti più importanti di tutta la matematica:<ref>{{cita web|autore=[[Enrico Bombieri]]|url=https://claymath.org/millennium/Riemann_Hypothesis/riemann.pdf|titolo=Problems of the Millennium: The Riemann Hypothesis|accesso=14 gennaio 2011|urlmorto=sì|urlarchivio=https://web.archive.org/web/20110111163814/http://www.claymath.org/millennium/Riemann_Hypothesis/riemann.pdf|dataarchivio=11 gennaio 2011}}</ref><ref>{{cita|Devlin|p. 211|Devlin}}.</ref> era uno dei ventitré [[problemi di Hilbert]], enunciati nel
Altri problemi aperti molto famosi sono le già citate congetture di [[congettura di Goldbach|Goldbach]], dei [[congettura dei numeri primi gemelli|primi gemelli]] e di [[congettura di Legendre|Legendre]].
Riga 1 034 ⟶ 298:
è sempre un numero primo. Tuttavia non si conosce nessuna formula chiusa per calcolare la costante di Mills: le approssimazioni attualmente utilizzate si basano sulla sequenza dei cosiddetti primi di Mills (i numeri primi generati tramite questa formula), che non possono essere ricavati rigorosamente, ma solamente in maniera probabilistica, assumendo per vera l'[[ipotesi di Riemann]].<ref>{{cita pubblicazione|url=https://www.cs.uwaterloo.ca/journals/JIS/VOL8/Caldwell/caldwell78.pdf|titolo=Determining Mills' Constant and a Note on Honaker's Problem|autore=Chris Caldwell|autore2=Yuanyou Cheng|rivista=Journal of Integer Sequences|volume=8|anno=2005|accesso=14 gennaio 2011}}</ref>
A seguito della dimostrazione del [[teorema di Matiyasevich]], sono stati trovati vari polinomi i cui valori positivi sono sempre numeri primi. Matijasevič dimostrò l'esistenza di un polinomio di 37º grado in 24 incognite, ma senza esplicitarlo; in seguito alcuni di questi sono stati determinati, ma rimangono poco utili per la ricerca di nuovi primi perché hanno diverse variabili e un grado molto elevato, e inoltre assumono spesso valori negativi.<ref name=littlebook>{{cita libro|url=http://books.google.it/books?id=zUCK7FT4xgAC&printsec=frontcover&hl=en&source=gbs_navlinks_s#v=onepage&q=&f=false|titolo=The little book of big primes|autore=Paulo Ribenboim|anno=1996|editore=Springer-Verlag|
Altre formule si possono costruire attraverso il [[teorema di Wilson]] con l'uso della funzione [[parte intera]], ma anche queste sono sostanzialmente inutilizzabili a causa della loro elevata [[Teoria della complessità computazionale|complessità computazionale]].
Riga 1 051 ⟶ 315:
Diversi altri algoritmi sono stati sviluppati nel corso del tempo: alcuni di essi si applicano solo a classi particolari di numeri, come ad esempio i [[test di Lucas-Lehmer]] e [[teorema di Proth|di Proth]], che si applicano solo ai [[numero primo di Mersenne|numeri di Mersenne]] e [[numero di Proth|di Proth]] rispettivamente. Altri, come il [[test di Miller-Rabin]], sono [[probabilità|probabilistici]], ovvero danno una risposta certa solo se affermano che il numero ''non'' è primo, mentre se si ottiene come risultato che il numero è primo, allora c'è solo un'alta probabilità che il numero effettivamente lo sia. I numeri che passano uno di questi test, pur senza essere primi, sono detti "[[pseudoprimo|pseudoprimi]]". La classe più famosa di pseudoprimi è quella dei [[numero di Carmichael|numeri di Carmichael]], che verificano il [[piccolo teorema di Fermat]] pur essendo composti.
Tra i test di primalità di uso generale il più usato attualmente è l'[[Algoritmo ECPP|ECPP]], basato sulle [[curva ellittica|curve ellittiche]];<ref>{{cita web|url=http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html|titolo=Elliptic Curve Primality Proving|autore=Eric W. Weisstein|sito=MathWorld|accesso=3 settembre 2009}}</ref> sebbene la sua complessità computazionale non sia nota, sperimentalmente si osserva che esso è un [[P (complessità)|algoritmo polinomiale]] nel numero delle cifre di ''n''.<ref>{{cita web|lingua=en |url=http://primes.utm.edu/prove/prove4_2.html |editore=The Prime Pages|accesso=14 gennaio 2011|titolo=Elliptic curves and ECPP test}}, da {{cita libro|autore= Lenstra Jr. K.|autore2=Lenstra|autore3=Jr. H. W.|capitolo= Algorithms in number theory. |titolo=Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity|editore= The MIT Press|città= Amsterdam and New York|pp= 673-715|anno=1990|
=== Algoritmi di fattorizzazione ===
Riga 1 058 ⟶ 322:
Più recentemente, gli algoritmi per la fattorizzazione sono stati basati su una gran varietà di tecniche diverse, come le [[frazione continua|frazioni continue]] o le [[curva ellittica|curve ellittiche]], mentre altri, come ad esempio il [[crivello quadratico]], sono basati su miglioramenti del metodo di Fermat. Altri ancora, come il [[Algoritmo rho di Pollard|metodo rho di Pollard]], sono probabilistici, e non offrono la garanzia che, dato un numero non primo, ne trovino i divisori.
A oggi il più veloce algoritmo deterministico di impiego generale, ovvero senza necessità di numeri in forma particolare, è il ''[[Crivello dei campi di numeri generale|general number field sieve]]'', che ha complessità esponenziale sul numero di cifre di ''N'';<ref>{{cita web|lingua=en|url=http://mathworld.wolfram.com/NumberFieldSieve.html|autore=Eric W. Weisstein|titolo=Number Field Sieve|accesso=14 gennaio 2011}}</ref> è stato proposto un algoritmo che ha tempo di esecuzione polinomiale nel numero di cifre di ''N'' ([[algoritmo di fattorizzazione di Shor|algoritmo di Shor]]), ma esso richiede di essere eseguito su un [[computer quantistico]], la cui simulazione su un normale calcolatore richiede un tempo esponenziale.<ref>{{cita libro|autore=Samuel J. Lomonaco jr.|titolo=Shor's Quantum Factoring Algorithm, in Quantum Computation - A Grand Mathematical Challenge for the Twenty-First Century and the Millennium|anno=2002|editore=AMS|url=https://www.csee.umbc.edu/~lomonaco/ams/lecturenotes/SamShor.pdf|accesso=14 gennaio 2011|
==== Impiego nella crittografia ====
Riga 1 069 ⟶ 333:
È possibile, in teoria, ricavare la chiave privata dalle informazioni pubbliche: attualmente questo richiede la fattorizzazione del numero ''n'', rendendo quindi la trasmissione del messaggio sicura se i due primi scelti soddisfano alcune condizioni e sono "sufficientemente" grandi. Non è ancora noto se vi siano metodi efficienti per decriptare il messaggio che non prevedano l'attacco diretto alla fattorizzazione di ''n'', ma è stato mostrato che una cattiva scelta della chiave pubblica potrebbe rendere il sistema più vulnerabile ad attacchi di questo tipo.<ref>{{cita web|autore=[[Ronald Rivest|Ron Rivest]] e Burt Kaliski|titolo=RSA Problem|url=https://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf|data=10 dicembre 2003|accesso=14 gennaio 2011|dataarchivio=17 maggio 2011|urlarchivio=https://web.archive.org/web/20110517084549/http://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf|urlmorto=sì}}</ref>
Nel
=== Numeri primi grandi ===
{{Vedi anche|Maggior numero primo conosciuto}}
[[File:Largest known prime number.svg|thumb|upright=1.4|Il numero di cifre (in [[sistema numerico decimale|base 10]]) del più grande numero primo conosciuto, dal
Già da molti secoli la ricerca di numeri primi "grandi" ha destato l'interesse dei matematici; tuttavia questa ricerca ha assunto una particolare importanza negli ultimi decenni, a causa del bisogno di tali numeri che caratterizza algoritmi quali l'RSA.
Riga 1 079 ⟶ 343:
Il metodo più efficace per ottenere numeri primi grandi risale al diciassettesimo secolo, quando [[Marin Mersenne]] congetturò che <math>M_n=2^n-1</math> sarebbe stato primo (quando ''n'' ≤ 257) solo per ''n'' uguale a 2, 3, 5, 7, 13, 19, 31, 67, 127 e 257.<ref>{{cita|Du Sautoy|p. 78|Sautoy}}.</ref> La verifica della primalità di tali numeri era molto al di sopra delle possibilità dell'epoca, e infatti soltanto nel [[XX secolo|Novecento]] si scoprì che la congettura era falsa e probabilmente fatta "alla cieca", in quanto Mersenne tralasciò tre casi (per ''n'' = 61, 89 e 107) e non si accorse che i numeri corrispondenti a ''n'' = 67 e ''n'' = 257 erano in realtà composti.
''M''<sub>127</sub> (un numero di 39 cifre) fu dimostrato essere primo da [[Édouard Lucas]] nel 1876, e rimase il numero primo più grande conosciuto fino al
In seguito, i quattordici nuovi numeri primi più grandi sono stati scoperti attraverso il [[GIMPS]], un progetto di [[calcolo distribuito]] basato anch'esso sul test di Lucas-Lehmer. A oggi (dicembre 2018) il più grande numero primo, scoperto nel dicembre del
La [[Electronic Frontier Foundation]] ha offerto dei premi in denaro ai primi che riusciranno a trovare numeri primi di oltre un certo numero di cifre. I primi due di questi premi, di {{formatnum:50000}} e {{formatnum:100000}} [[dollaro statunitense|dollari]], sono stati assegnati nel
== Generalizzazioni ==
Riga 1 119 ⟶ 383:
In [[teoria dei nodi]], un [[nodo primo]] è un [[nodo (matematica)|nodo]] non banale che non può essere "scomposto" in due nodi più piccoli. In maniera più precisa, è un nodo che non può essere scritto come [[somma connessa]] di due nodi non banali.
Nel
== Numeri primi in natura ==
Riga 1 133 ⟶ 397:
== Numeri primi nell'arte e nella letteratura ==
I numeri primi hanno influenzato molti artisti e scrittori. Il compositore francese [[Olivier Messiaen]] era ossessionato da tali numeri<ref name= Du_Sautoy >{{cita libro|cognome= Du Sautoy|nome= Marcus|wkautore= Marcus du Sautoy|curatore= Michael Emmer|capitolo= Un divertissement in prima serata|titolo=Matematica e cultura 2006|url= http://books.google.it/books?id=GUW8v0u56dYC&printsec=frontcover&source=gbs_summary_r&cad=0|accesso= 4 settembre 2008|anno= 2006|editore= Springer|pp= 201-207 |
I numeri primi svolgono un ruolo anche in alcuni libri. Ad esempio, nel romanzo di fantascienza ''[[Contact (romanzo)|Contact]]'' di [[Carl Sagan]] (così come nella sua [[Contact (film)|versione cinematografica]]), i numeri primi vengono utilizzati dagli alieni per comunicare; un caso reale di uso dei primi come mezzo di comunicazione è presente nel saggio ''[[L'uomo che scambiò sua moglie per un cappello]]'', del neurologo [[Oliver Sacks]], dove sono descritti due gemelli [[autismo|autistici]] che per parlarsi si scambiano primi molto elevati. Vi sono riferimenti ai numeri primi anche nel romanzo di [[Mark Haddon]] ''[[Lo strano caso del cane ucciso a mezzanotte]]'', in cui la numerazione dei capitoli segue la successione dei primi, e nel romanzo di [[Paolo Giordano (scrittore)|Paolo Giordano]] ''[[La solitudine dei numeri primi]]'', vincitore del [[premio Strega]] nel 2008. Il romanzo ''Lo zio Petros e la congettura di Goldbach'' di [[Apostolos Doxiadis]] (pubblicato in italiano nel 2001) è stato trasposto per le scene da [[Angelo Savelli]].<ref>Angelo Savelli, ''[http://www.springerlink.com/content/978-88-470-0346-0/#section=593676&page=1 Zio Petros tra scienza, letteratura e teatro]'', in Mirella Manaresi (a cura di), ''[http://books.google.it/books?id=o-TlWNLC710C Matematica e cultura in Europa]'', Milano, Springer, 2005, pp. 305-312. ISBN 88-470-0346-6; ISBN 978-88-470-0346-0.</ref>
Riga 1 146 ⟶ 410:
== Bibliografia ==
* {{Cita libro| autore = [[Tom M. Apostol]]|titolo=Introduction to Analytic Number Theory|anno=1976 |editore=Springer-Verlag |città=New York |ed=2|lingua=
* {{Cita libro| autore = Michael Artin|titolo=Algebra|anno=1997 |editore= Bollati Boringhieri|città=Torino|cid=Artin|
* {{Cita libro| autore= [[Carl B. Boyer]]|titolo=[[Storia della matematica (Boyer)|Storia della matematica]]|anno=1990 |editore=Mondadori |città= Milano |cid=Boyer|
* {{Cita libro|autore= [[John Conway|John H. Conway]] e [[Richard K. Guy]] | titolo=Il libro dei numeri| anno=1999 | editore=Hoepli | città=Milano |cid=Conwayguy|
* {{Cita libro| autore=[[Harold Davenport]] | titolo=Aritmetica superiore| anno=1994 | editore=Zanichelli | città=Bologna |cid=Davenport|
* {{Cita libro| autore= [[Keith Devlin]] | titolo=Dove va la matematica | anno=1994 | editore=Bollati Boringhieri | città=Torino |cid=Devlin|
* {{Cita libro| autore= [[Marcus du Sautoy]]| titolo=[[L'enigma dei numeri primi]]| anno=2004 | editore=Rizzoli | città=Milano |cid=Sautoy|
* [[Euclide]], ''[[Elementi (Euclide)|Elementi]]''
* {{Cita libro| autore= Richard K. Guy|titolo=Unsolved problems in number theory| url= https://archive.org/details/unsolvedproblems0003guyr| anno=2004 | editore= Springer-Verlag | città=New York|lingua=
* {{cita libro | autore= [[Godfrey Harold Hardy]] e [[Edward M. Wright]]|editore = Oxford University Press|titolo = An Introduction to the Theory of Numbers |ed=6 |città=Oxford | anno = 2008 |lingua=
* {{Cita libro| autore= Albert Edward Ingham|wkautore=Albert Ingham|titolo=The Distribution of Prime Numbers| anno=1932 | editore=Cambridge University Press| città=Cambridge|lingua=
* {{Cita libro| autore=Leo Moser | titolo=An Introduction to the Theory of Numbers| 2004 | editore=The Trillia Group | città=West Lafayette (Indiana, USA) | url=http://www.trillia.com/moser-number.html |lingua=
* {{Cita libro| autore=Giulia Maria Piacentini Cattaneo | titolo=Algebra - un approccio algoritmico| anno=1996 | editore=Decibel-Zanichelli | città=Padova |
* {{Cita libro| autore=[[Simon Singh]]| titolo=[[Codici & segreti]]| anno=1999 | editore=Rizzoli|città=Milano|
* {{Cita libro| autore= [[Ian Stewart (matematico)|Ian Stewart]] e David Tall|titolo=Algebraic number theory and Fermat's last theorem| url= https://archive.org/details/algebraicnumbert0000stew_o8a3| anno=2002 | editore= A K Peters| città=Natick, Massachusetts |lingua=
* {{Cita libro| autore= [[Terence Tao]] e Van Vu|titolo= Additive combinatorics| anno=2006 | editore= Cambridge University Press | città=Cambridge|lingua=
* {{Cita libro| autore=Song Y. Yan|titolo=Primality testing and integer factorization in public-key cryptography| url=https://archive.org/details/primalitytesting0000yans| anno=2004 | editore= Kluwer Academic Publishers| città=Boston|lingua=
== Voci correlate ==
| |||