Don't take life too seriously: it's just a temporary situation

Primi (numeri)

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Proprietà
  3. 3. Distribuzione dei numeri primi
  4. 4. Differenze tra primi consecutivi
  5. 5. Progressioni aritmetiche di numeri primi
  6. 6. Progressioni aritmetiche contenenti numeri primi
  7. 7. Funzioni che producono numeri primi
  8. 8. Esami di primalità
  9. 9. Tabelle di primi
  10. 10. Grandi primi
  11. 11. Primi di forme particolari
  12. 12. Somme che coinvolgono numeri primi
  13. 13. Prodotti che coinvolgono numeri primi
  14. 14. Rappresentazioni di interi come somma di numeri primi
  15. 15. Proprietà basate sulle cifre
  16. 16. Categorie di primi

Le applicazioni pratiche dei numeri primi, in particolare nella crittografia (ebbene sì: i primi hanno applicazioni militari!), hanno stimolato lo sviluppo di metodi per stabilire se un intero è primo. Possiamo grossolanamente suddividerli in sei categorie.

 

La prima categoria contiene metodi basati su teoremi che affermano che solo i numeri primi soddisfano certe caratteristiche. Questi metodi danno una risposta certa, sono validi per ogni intero, ma efficaci solo per numeri relativamente piccoli o di interesse solamente teorico, per la quantità di calcoli necessari.

  • Naturalmente si può provare a dividere il numero in esame per tutti i numeri primi minori della sua radice quadrata.

  • Nel 1758 Eulero dimostrò che un intero n è primo se e solo se ha una sola rappresentazione come x2 + ky2, dove k è un numero idoneo minore di n; Eulero dimostrò che 18518809 è primo, mostrando che ha una sola rappresentazione come x2 + 1848y2; credo questo e alcuni altri trovati da Eulero con la stessa tecnica siano gli unici numeri dimostrati primi in questo modo.

  • Nel 1778 Eulero generalizzò il metodo, dimostrando che se, fissati a e b, un intero ammette più di una rappresentazione della forma ax2 + by2, con x e y interi non entrambi uguali a 1, allora è composto, mentre non è necessariamente vero l’inverso: un numero composto può avere un’unica rappresentazione del genere, a meno che a sia 1 e b idoneo.

  • Il teorema di Wilson afferma che un intero n è primo se e solo se è un divisore di (n – 1)! + 1. Il massimo primo dimostrato tale tramite il teorema di Wilson è 1099511628401.

  • Dal teorema di Wilson segue che Formula che vale 1 se n è primo, 0 altrimenti per n > 4 vale 1 se n è primo, 0 altrimenti (Hardy e Wright).

  • D.J. Lehmann dimostrò che un intero dispari n è primo se e solo se per ogni intero positivo a minore di n vale a^((n – 1) / 2) ≡ ±1 mod n ed esiste almeno un intero a minore di n tale che a^((n – 1) / 2) ≡ –1 mod n (v. pseudoprimi assoluti di Eulero).

  • Nel 1964 C.P. Willan dimostrò che Formula che vale 1 se n è primo, 0 altrimenti vale 1 se n è 1 o primo, 0 altrimenti (Mathematical Gazette, 1964). Come conseguenza si ottengono altre curiose formule: Formula per il calcolo di π(n), Formula per il calcolo di p(n), Formula per il calcolo di p(n).

  • H.B. Mann e D. Shanks dimostrarono nel 1972 che un intero n è primo se e solo se per ogni k tra Massimo intero non superiore a (n + 2) / 3 e Massimo intero non superiore a n / 2 k divide Coefficiente binomiale C(k, n – 2 * k).

  • Il teorema dimostrato da Emmanuel Vantieghem nel 1991 afferma che un intero n maggiore di 2 è primo se e solo se Congruenza soddisfatta dai primi maggiori di 2. Nel 2008 Vantieghem dimostrò una generalizzazione del teorema: un intero n maggiore di 2 è primo se e solo se Congruenza soddisfatta dai primi maggiori di 2.

  • Un un intero n è primo se e solo se Congruenza soddisfatta dai primi.

  • Un intero n è primo se e solo se Somma uguale a 2 solo per i primi.

  • per n > 4 Espressione uguale a 1 per i primi vale 1 se n è primo, 0 altrimenti (H. Laurent).

  • per n > 4 Espressione uguale a 1 per i primi vale 1 se n è primo, 0 altrimenti.

  • per n > 1 Espressione uguale a 1 per i primi vale 1 se n è primo, 0 altrimenti.

  • per n > 4 Espressione uguale a 1 per i primi vale 1 se n è primo, 0 altrimenti.

 

Una versione del teorema di Wilson afferma che p è primo se e solo se (pd)!(d – 1)! ≡ –1 mod p, per d dispari; da queste due forme del teorema si ricava che p e p + d sono simultaneamente primi se e solo se (p – 1)! * (1 / p + (–1)^d * d! / (p + d)) + 1/ p + 1 / (p + d) è intero.

 

Una piccola nota sul teorema “di Wilson”; oggi è universalmente noto con quel nome, ma l’attribuzione è errata: fu enunciato per la prima volta dal matematico, astronomo e fisico arabo Abū ‘Alī al-Hasan ibn al-Hasan ibn al-Haytham (circa 965 – circa 1040), che per semplicità chiamerò col nome latinizzato di Alhazen, col quale è più noto. Pare che Leibniz lo conoscesse nel XVII secolo, ma non lo enunciò esplicitamente, forse perché non riuscì a dimostrarlo. Edward Waring (Old Heath, Inghilterra, circa 1736 – Plealey, Inghilterra, 15/8/1798) lo enunciò nuovamente nel 1770, ma né Alhazen, né Waring né il suo studente John Wilson (Applethwaite, Inghilterra, 6/8/1741 – Kendal, Inghilterra, 18/10/1793) lo dimostrarono. La prima dimostrazione si deve a Lagrange, nel 1771.

 

La seconda categoria comprende metodi che danno risposta certa, validi per ogni intero e applicabili anche a numeri molto grandi, anche se alcuni sono efficaci solo per alcune categorie di numeri. Il loro sviluppo è relativamente recente.

  • I primi passi per migliorare l’esame basato sulle divisioni per tutti i primi minori della radice quadrata del numero in esamefurono fatti da Gary Miller, che nel 1976 sviluppò un algoritmo difficile da valutare, ma che probabilmente impiega in media un tempo proporzionale alla quinta potenza del logaritmo del numero. Dato che il logaritmo è proporzionale al numero di cifre, possiamo dire che il metodo di Miller richiede un tempo proporzionale alla quinta potenza del numero di cifre; la validità dell’algoritmo dipende però dall’ipotesi di Riemann.

  • L’algoritmo di Leonard M. Adleman, Carl Pomerance e Robert S. Rumely, sviluppato nel 1983, richiede un numero di operazioni proporzionale a lognClogloglogn, dove C è una costante: in pratica è poco più che proporzionale a una potenza del numero di cifre.

  • Il test di François Édouard Anatole Lucas (Amiens, Francia, 4/4/1842 – Parigi, 3/10/1891) è efficace, se si conosce la scomposizione in fattori primi di n + 1: n è primo se esiste una sequenza di Lucas generalizzata tale che Un + 1 ≡ 1 mod n e U(n + 1) / r – 1 non è multiplo di n, per tutti i primi p che dividono n + 1.

  • Un altro test di Lucas è basato sulle sequenze di Fibonacci: un intero n della forma 10k ± 3 è primo se e solo se divide Fn + 1 e nessun numero di Fibonacci con indice che divida n + 1; un intero n della forma 10k ± 1 è primo se e solo se divide Fn – 1 e nessun numero di Fibonacci con indice che divida n – 1. Il test richiede quindi di conoscere la scomposizione in fattori primi di n + 1 o n – 1, quindi è particolarmente semplice per i numeri di Mersenne e permette di affrontare numeri enormi.

  • Esistono test per decidere se un intero n è primo, quando sono noti una parte dei fattori di n + 1 o n – 1, come il test proposto nel 1914 da Henry Cabourn Pocklington (Exeter, Inghilterra, 28/1/1870 – Leeds, Inghilterra, 15/5/1952): se n – 1 = ab, con a e b primi tra loro e a > b e se per ogni fattore primo p di a esiste un intero k tale che kn – 1 ≡ 1 mod n e n è primo rispetto a k^(n – 1) / q – 1, allora n è primo (si possono usare differenti valori di k per ogni fattore p). Per applicare il test si possono raccogliere in a i fattori più piccoli di n – 1, senza dover scomporre b. Il test è particolarmente vantaggioso se n – 1 è il prodotto di potenze elevate di primi piccoli o se la scomposizione di n – 1 è nota e semplice, come nel caso dei primi sicuri.

  • Il test analogo proposto da Derrick Henry Lehmer (Berkeley, USA, 23/2/1905 – Berkeley, USA, 22/5/1991) nel 1928 richiede di scomporre n – 1 = ab, con a e b primi tra loro e a maggiore della radice quadrata di n, e di riuscire a scomporre completamente a. Nel 1975 J. Brillhart, lo stesso Lehmer e J.L. Selfridge lo migliorarono in modo da richiedere solo che a > n^(1 / 3). S. Konyagin e Carl Pomerance apportarono ulteriori miglioramenti, in modo da richiedere solo che a > n^(3 / 10). Il metodo è veloce, ma applicabile solo a casi particolari, perché richiede di riuscire a scomporre parzialmente n – 1 e completamente un numero che può essere piuttosto grande, cosa generalmente molto difficile.

  • Il test di Lucas – Lehmer è una semplificazione del test di Lucas: se per ogni fattore primo p di n – 1 esiste un intero a non congruente a 1 modulo n tale che an – 1 ≡ 1 mod n e a^((n – 1) / p), allora n è primo; i valori di a possono essere differenti per i vari primi p. Il test è particolarmente semplice per alcune categorie di numeri, come i numeri di Fermat, per i quali i fattori di n – 1 sono pochi e noti, ma può anche essere adattato a numeri della forma 2k – 1; è quindi particolarmente efficace con i numeri di Mersenne.

  • Il test di Lucas, Lehmer, Brillhart e Selfridge: se per ogni primo p che divide n – 1 esiste un intero ap tale che a(p) ^ (n – 1) – 1 sia multiplo di na(p) ^ ((n – 1) / p) – 1 no, allora n è primo; vale anche l’inverso: se n è primo, una sua radice primitiva può essere presa come ap. Il test vale per qualsiasi intero, ma è conveniente applicarlo solo se n – 1 ha fattori primi non molto grandi.

  • Un metodo proposto da Hendrik W. Lenstra nel 1981 e perfezionato da altri permette di dimostrare che n è primo se si conoscono fattori primi di nk – 1, con k < (logn)logloglogn, tali che il loro prodotto sia maggiore della radice cubica di n. Questo è sempre possibile (ma non necessariamente semplice), perché è stato dimostrato che per ogni n esiste almeno un intero k < (logn)logloglogn, per il quale i primi p che dividono nk – 1, con p – 1 che divide k (quindi non troppo grandi), hanno un prodotto almeno pari alla radice quadrata di n. Questo metodo è particolarmente conveniente per alcune categorie di interi, come i numeri di Mersenne, Fermat e Woodall, per i quali è agevole scomporre nk – 1.

  • L’algoritmo di A.O.L. Atkin e F. Morain (1993) richiede generalmente un tempo proporzionale alla quinta potenza del numero di cifre, anche se non è noto come cresca il tempo di calcolo nei casi peggiori; ha permesso di dimostrare primi i massimi primi noti non di forme particolari.

  • L’algoritmo di Selfridge e Weinberger richiede un tempo proporzionale a una potenza del numero di cifre se è vera l’ipotesi di Riemann generalizzata, e la conoscenza di numeri con particolari proprietà che non sono semplici da calcolare (v. pseudoquadrati).

  • Finalmente nell’agosto 2002 Manindra Agrawal, Neeraj Kayal, e Nitin Saxena, dell’Indian Institute of Technology in Kanpur, annunciarono il primo algoritmo (detto “AKS”, dalle iniziali degli ideatori) di uso generale e deterministico che richiede un numero di operazioni che cresce come una potenza del numero di cifre. Nella versione iniziale l’esponente della potenza era 21 / 2 e asintoticamente 15 / 2, ma alcuni miglioramenti l’hanno ridotto a 6 (Hendrik W. Lenstra Jr. e Carl Pomerance, 2003) e successivamente a 4 (tranne in rarissimi casi). Se si riuscirà a dimostrare vera la congettura di Agrawal o una sua variante, l’esponente potrà essere ridotto a 3.

 

La terza categoria contiene metodi che danno una risposta certa, ma sono validi solo per numeri di alcune forme particolari.

  • Un teorema dimostrato da Eulero nel 1752 afferma che un intero è primo se si può esprimere come somma di quadrati in un solo modo. Eulero dimostrò così che 1000009 = 10002 + 32 è primo perché non è somma di quadrati in altro modo. Utilizzando tabelle di quadrati, il metodo non richiede moltiplicazioni e divisioni, inoltre considerazioni sul resto ottenuto dividendo il numero per 5 permettono di ridurre i candidati da provare. Il metodo però è applicabile solo a 2 e ai primi della forma 4k + 1.

  • Per alcune categorie di numeri, si sa che i divisori, se esistono, devono essere anch’essi di una certa forma: per esempio, i divisori del numero di Mersenne 2n – 1 devono essere della forma 2kn + 1; si possono quindi provare selettivamente i primi di quella forma, sino alla radice quadrata del numero. Per provare che 231 – 1 è primo, Eulero provò solo i numeri primi della forma 64k + 1. Questo metodo era tipicamente usato tempo fa per numeri di Mersenne e loro divisori.

  • Se n è della forma k2m + 1, con k dispari e 2m > k, e non è residuo quadratico modulo un primo dispari p, n è primo se e solo se p^((n – 1) / 2) ≡ –1 mod n; il metodo è applicabile solo per gli interi di quella forma e solo se si trova un primo p adatto.

  • Il test di Jean François Théophile Pépin (Cluses, Francia, 14/5/1826 – 3/4/1904) è un caso particolare del test di Lucas, valido solo per i numeri di Fermat: Fn è primo se e solo se k^(F(n) – 1) / 2) ≡ –1 mod F(n), cioè se k^(2^(2^n – 1)) ≡ –1 mod F(n), dove k è un qualsiasi nonresiduo quadratico di Fn. Per esempio, F2 = 17 e 5^((17 – 1) / 2) + 1 è multiplo di 17.

  • Il test di Proth (v. numeri di Proth) e le sue generalizzazioni vale solo per numeri della forma kph + 1, con p primo e ph > k.

  • Il test di Hugh Cowie Williams (1982) vale per interi della forma forma kb2n + hbn – 1 (v. numeri di Lucas (I)).

 

La quarta categoria comprende metodi che danno una risposta certa con probabilità più o meno alta, vale a dire che possono non riuscire a determinare che un numero primo è effettivamente tale, ma se lo affermano non sbagliano.

  • Nel 1985, Hendrik W. Lenstra introdusse un metodo basato sulle curve ellittiche; successivamente altri idearono metodi analoghi, come quello di Atkin e l’algoritmo di Goldwasser – Kilian, che è uno dei più efficienti. Nel 1992 Francois Morain dimostrò in questo modo che il numero di partizioni p(1840926), che ha 1505 cifre, è primo, stabilendo allora il record del massimo numero primo noto, al di fuori dei primi di Mersenne.

  • Nel 1987 Adleman e Huang idearono un algoritmo basato sulle proprietà delle varietà abeliane, che utilizza un numero generato casualmente (ma che rispetta vincoli precisi). In un tempo proporzionale a un polinomio calcolato sul numero di cifre del numero in esame, l’algoritmo determina se il numero è primo o composto, o dichiara di non riuscire a stabilirlo. Si può quindi provare con un altro numero casuale di partenza e sperare d’essere più fortunati. Si tratta del primo algoritmo trovato con un tempo di calcolo proporzionale al massimo a una potenza del numero di cifre, anche se non sempre dà una risposta. Con un numero relativamente piccolo di tentativi si ha una probabilità altissima di avere una risposta, inoltre in caso di fallimento non si ottiene una risposta errata, ma si sa di non avere risposta.

 

La quinta categoria comprende metodi che danno una risposta certa, se il numero è composto, ma solo probabile se è primo, con un errore inverso a quelli della categoria precedente; la probabilità di errore può essere resa estremamente piccola. Il loro vantaggio sta nella grande velocità: sono molto usati in applicazioni pratiche, soprattutto nella crittografia, dove una probabilità di errore come 1 su 1020 è accettabile. I primi trovati con i metodi di questa categoria sono generalmente chimati “primi probabili”.

  • Nel 1977 Robert M. Solovay e Volker Strassen proposero un test basato sul verificare se b^((n – 1) / 2) ≡ (b | n) mod n, dove Simbolo di Jacobi (b | n)è il simbolo di Jacobi, per un certo numero di basi b scelte a caso; il metodo dà una risposta certa se il numero è composto, solo probabile se è primo. I due matematici dimostrarono che un numero n composto può superare l’esame, passando per primo, per al massimo φ(n) / 2 basi minori di n (v. pseudoprimi di Eulero – Jacobi), quindi utilizzando k basi la probabilità di errore è inferiore a 2k e può essere ridotta al di sotto di una soglia fissata a piacere.

  • Il metodo sviluppato nel 1980 da Robert Baillie, Carl Pomerance, John Selfridge, e Samuel S. Wagstaff Jr., noto come “test di Baillie-PSW” dai nomi degli ideatori, consiste nel verificare se n passa il test di primalità forte in base 2 (v. pseudoprimi forti di Fermat), poi cercare il minimo valore di D nella sequenza 5, −7, 9, −11, 13, −15, … per il quale il simbolo di Jacobi Simbolo di Jacobi (D | n) sia –1 (Baillie e Wagstaff dimostrarono che bisogna provare in media circa 3.147755149 valori per D) dopodiché verificare se n passa il test di primalità forte di Lucas (v. pseudoprimi forti di Lucas) rispetto a Q = (1 – D) / 4 e P = 1. Il test è considerato migliore di quello di Solovay e Strassen, perché fallisce solo per un numero composto che sia pseudoprimo forte di Fermat in base 2 e pseudoprimo forte di Lucas rispetto a P e Q; non si conosce alcun numero del genere, se esiste è maggiore di 264. Vi sono alcune varianti sul metodo, per esempio, prendere per D il primo numero dispari maggiore di 3 tale che Simbolo di Jacobi (D | n) uguale a –1, quindi prendere per P il minimo numero dispari maggiore della radice quadrata di D e Q = (P^2 – D) / 4.

  • Gary L. Miller propose nel 1976 un test che dipende da una forma generalizzata dell’ipotesi di Riemann (ma che in realtà era stato proposto da M. M. Artjuhov nel 1967). Nel 1980 Michael O. Rabin lo modificò, ricavandone un test probabilistico, che non dipende da alcun teorema non dimostrato, divenuto noto come “test di Miller – Rabin”. Consiste nel verificare se il numero in esame è uno pseudoprimo forte di Fermat rispetto ad alcune basi, scelte tra piccoli primi. Per ogni intero composto dispari n esistono al massimo (n – 1) / 4 basi rispetto alle quali è pseudoprimo forte di Fermat (come dimostrò Rabin), e la probabilità è indipendente per le varie basi, quindi utilizzando k basi la probabilità di errore è inferiore a 4k e può essere ridotta al di sotto di una soglia fissata a piacere. Inoltre il numero di basi per le quali il test fallisce è uguale al massimo solo se n = p1p2, p1 = 2q1 + 1, p2 = 4q2 + 1, con p1, p2, q1, e q2 primi o se n = p1p2p3, p1 = 2q1 + 1, p2 = 2q2 + 1, p3 = 2q3 + 1 con p1, p2, p3, q1, q2 e q3 primi, quindi solo per una piccola minoranza dei numeri composti e la probabilità di fallimento del test è generalmente minore di quanto indicato.

  • Vari matematici, tra i quali Jon Grantham (1998), Siguna Müller (2001), Ivan Bjerre Damgård e Gudmund Skovbjerg Frandsen (2003) e Martin Seysen (2005) proposero test basati sugli pseudoprimi di Frobenius con una probabilità d’errore molto minore per ogni scelta dei parametri (v. pseudoprimi di Frobenius).

 

La sesta categoria comprende metodi deterministici, ma che dipendono da congetture non ancora dimostrate, tipicamente da varie versioni dell’ipotesi di Riemann. Per esempio, Miller dimostrò che, se vale una forma generalizzata di tale ipotesi, il test di Rabin basato sugli pseudoprimi forti di Fermat diventa deterministico se si utilizzano come base tutti gli interi sino a 2log2n. Questo fornisce un metodo che è più lento di quello proposto da Rabin (che prevede di provare solo alcune basi), ma dà una risposta più sicura, solo che la sua lentezza lo rende poco attraente per scopi pratici, mentre la perdurante incertezza sull’ipotesi di Riemann lo esclude dall’ambito delle prove rigorose.

 

Da un punto di vista pratico, nelle applicazioni crittografiche si utilizzano generalmente metodi della quinta categoria, perché l’algoritmo AKS è nettamente più lento, almeno per i numeri utilizzati in tali applicazioni (da alcune centinaia di cifre a oltre un migliaio).

Sempre per le applicazioni nella crittografia, la generazione di primi di centinaia di cifre è stata oggetto di molti studi. Non si conosce ancora un metodo per trovare un primo maggiore di un intero fissato in un tempo che cresca come un polinomio del numero di cifre, tuttavia si conoscono dei metodi che hanno un comportamento medio eccellente.

 

L. van der Dries e Y. Moschovakis dimostrarono nel 2004 che qualsiasi algoritmo ricorsivo per determinare se un numero è primo, che utilizzi solo somme, sottrazioni, confronti e moltiplicazioni e divisioni per 2, non può impiegare un numero di passi minore di un quarto del numero di cifre nella rappresentazione binaria del numero da esaminare.

 

Per altre congetture sugli esami di primalità v. congetture sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.