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

Composti (numeri)

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Fattori primi dei numeri composti
  3. 3. Scomposizione dei numeri composti
  4. 4. Numeri composti consecutivi
  5. 5. Fattori primi di numeri composti consecutivi
  6. 6. Rappresentazione di interi come somma di numeri composti
  7. 7. Proprietà basate sulle cifre

Come si può scomporre un intero in fattori primi? Il metodo più ovvio e noto dall’antichità è provare a dividerlo per tutti i numeri primi inferiori alla sua radice quadrata, ma per numeri grandi il costo è proibitivo: nel caso peggiore il numero di operazioni per scomporre un intero n cresce come sqrt(n) / log(n), ma solo supponendo di disporre della lista dei primi minori di Radice quadrata di n, ipotesi non realistica per n molto grande, altrimenti cresce come Radice quadrata di n.

 

Il primo progresso si deve a Fermat (1643), che suggerì di provare a esprimere il numero come differenza di quadrati: se n = x2y2, allora n = (x + y)(xy), quindi trovando x e y si sono trovati due fattori, eventualmente da scomporre a loro volta. Fermat iniziava dal minimo quadrato maggiore di n ed esaminava le differenze tra quadrati successivi (che si possono calcolare con semplici addizioni) e n, verificando se otteneva un quadrato (cosa molto più veloce che determinare se un numero è primo). Il metodo è in generale più complesso di quello elementare, ma può funzionare bene in alcuni casi, in particolare se il numero da scomporre è il prodotto di due interi, la differenza dei quali è relativamente piccola. Nei secoli seguenti il metodo venne perfezionato, eleminando molti tentativi sulla base delle cifre finali e del resto ottenuto dividendo n per alcuni numeri, ma la sua efficacia resta legata a circostanze favorevoli.

In media il metodo di Fermat è più veloce del metodo di provare i vari numeri primi; nel caso peggiore, però, il numero di operazioni necessarie per scomporre il numero cresce come n.

 

Nel 1798 Legendre dimostrò che si può scomporre un numero in fattori primi, se si riesce a rappresentare il numero o un suo multiplo come ax2 + y2, con a abbastanza piccolo: produsse allo scopo tabelle che semplificavano i successivi calcoli per vari valori di a.

 

In seguito molti matematici proposero metodi basati sui possibili prodotti che potevano generare l’ultima cifra o le ultime due, talvolta utilizzando rappresentazioni in base 30 o in altre basi, e facilitavano la scomposizione utilizzando tabelle ausiliarie. Tali metodi restano limitati dall’estensione delle tabelle di primi disponibili e di fatto sono adatti solo per numeri relativamente piccoli.

 

Esistono altri metodi adatti a interi di forme particolari: il metodo basato su campi di interi funziona piuttosto bene per numeri vicini a una potenza, quindi in particolare per i numeri di Mersenne e di Fermat.

 

Il grande problema insoluto è se esista un algoritmo capace di trovare un fattore di un intero di n cifre in un tempo che non cresca più velocemente di una potenza di n; non se ne conosce nessuno, ma non è stato dimostrato che non possa esistere. La scoperta di un algoritmo per determinare se un intero è primo con crescita del tempo proporzionale a una potenza del numero di cifre (v. numeri primi) ha riacceso le speranze.

Il miglior metodo noto valido per qualsiasi intero, detto “General Number Field Sieve” impiega un tempo che cresce come e^((64 / 9 * n * log(n)^2)^(1/3)), dove n è il numero di cifre.

Scomporre un numero che sia il prodotto di due soli primi molto grandi, è un’impresa ardua, già a partire da un centinaio di cifre.

La crittografia a chiave pubblica con l’algoritmo RSA, del resto, si basa sul fatto che è relativamente facile trovare due primi molto grandi e moltiplicarli, ma è difficile scomporre il prodotto.

Nel 1977 Gardner propose ai lettori un testo cifrato, per decifrare il quale era necessario trovare i due fattori primi di un intero di 129 cifre. Gardner azzardò che sarebbero stati necessari milioni di anni di calcolo, ma solo 17 anni dopo 600 volontari in 6 mesi di sforzo coordinato trovarono i fattori. Al momento, comunque, non è troppo complesso trovare primi di un centinaio di cifre, il prodotto dei quali può resistere agli sforzi dei migliori calcolatori per anni (no, non aggiungo “milioni”!).

 

Altri metodi si basano su tentativi, in un certo senso più “mirati” che non provare a dividere il numero per i vari primi in successione; tali metodi spesso utilizzano alcuni numeri come “punti di partenza” e consistono nell’effettuare un certo numero di tentativi; se non si riesce a trovare una scomposizione, si cambia punto di partenza e si riprova. Questi metodi si comportano in media abbastanza bene, ma non danno alcuna garanzia di riuscire a trovare un fattore in un tempo finito.

 

Nel 1974 J.M. Pollard propose un algoritmo, noto come “p – 1”, che può riuscire a trovare un fattore di un intero in un tempo relativamente rapido, ma non dà nessuna garanzia.

L’algoritmo consiste nel calcolare xk = 2k! – 1 per valori crescenti di k ed esaminare se MCD(xk, n) è diverso da 1, nel qual caso è un divisore, non necessariamente primo, di n.

Il calcolo di 2k! – 1 mod n si esegue come (2^((k – 1)!))^k – 1 mod n, in modo che è necessario calcolare un solo elevamento a potenza (modulo n) per ogni nuovo valore di k.

Per esempio, per scomporre n = 21583 = 113 • 191 si calcola:

x1 = 21! – 1 mod 21583 = 1;

x2 = 22! – 1 mod 21583 = 3; MCD(3, 21583) = 1;

x3 = 23! – 1 mod 21583 = 63; MCD(63, 21583) = 1;

x4 = 24! – 1 mod 21583 = 7224; MCD(7224, 21583) = 1;

x5 = 25! – 1 mod 21583 = 6809; MCD(6809, 21583) = 1;

x6 = 26! – 1 mod 21583 = 14286; MCD(14286, 21583) = 1;

x7 = 27! – 1 mod 21583 = 11300; MCD(11300, 21583) = 113.

Abbiamo trovato un fattore di 21583 in 7 passi, mentre ce ne sarebbero voluti 30 provando i numeri primi in ordine crescente. In questo caso il metodo ha funzionato piuttosto bene, ma potrebbe richiedere un numero enorme di passi o non trovare alcun fattore. Se l’algoritmo supera un numero prefissato di passi senza trovare un divisore, solitamente si preferisce cambiare il numero che fa da base, invece di insistere. In questo modo non si ha alcuna garanzia di successo, ma il comportamento medio dell’algoritmo è piuttosto buono. Se avessimo usato 7 al posto di 2, avremmo trovato 113 in soli 5 passi.

Per illustrare un caso di fallimento, proviamo a scomporre 65 = 5 • 13:

x1 = 21! – 1 mod 65 = 1;

x2 = 22! – 1 mod 65 = 3; MCD(3, 65) = 1;

x3 = 23! – 1 mod 65 = 63; MCD(63, 65) = 1;

x4 = 24! – 1 mod 65 = 0.

I termini successivi della sequenza sono tutti nulli e proseguire è inutile. Avremmo però trovato il fattore 13 in soli 3 passi se avessimo usato 3 al posto di 2.

 

Nel 1975 lo stesso Pollard propose un algoritmo, noto come “rho”, che può riuscire a trovare un fattore di un intero in un tempo relativamente rapido, ma non dà nessuna garanzia.

L’algoritmo è semplice: per scomporre un intero n si inizia con un intero x0 ≡ 2 mod n e si calcola ripetutamente x(k + 1) = x(k)^2 + 1 mod n. Si esamina quindi se MCD(xkx2k, n) è maggiore di 1 e divide n per qualche valore di k. Se la risposta è affermativa, un fattore di n (non necessariamente primo) è stato trovato, altrimenti si continua per un certo numero di tentativi o fino a quando la sequenza diviene periodica ed eventualmente si riprova con un diverso valore iniziale.

Per esempio, per scomporre n = 21583 si calcola:

x0 = 2;

x1 = 22 + 1 mod 21583 = 5;

x2 = 52 + 1 mod 21583 = 26; MCD(5 – 26, 21583) = 1;

x3 = 262 + 1 mod 21583 = 677;

x4 = 6772 + 1 mod 21583 = 5087; MCD(26 – 5087, 21583) = 1;

x5 = 50872 + 1 mod 21583 = 21136;

x6 = 211362 + 1 mod 21583 = 5563; MCD(677 – 5563, 21583) = 1;

x7 = 55632 + 1 mod 21583 = 18531;

x8 = 185312 + 1 mod 21583 = 12432; MCD(5087 – 12432, 21583) = 113.

Anche in questo caso il metodo ha funzionato piuttosto bene, ma l’algoritmo potrebbe non terminare mai.

La sequenza generata diviene periodica dopo un numero di passi che per quasi tutti gli interi cresce come Radice quadrata di n; se questo avviene senza aver trovato un divisore, bisogna ricominciare con un diverso numero di partenza. Per esempio, tentando di scomporre 21 = 3 • 7 si produce la sequenza:

x0 = 2;

x1 = 22 + 1 mod 21 = 5;

x2 = 52 + 1 mod 21 = 5.

La sequenza ha raggiunto un ciclo di un solo elemento senza trovare divisori.

In pratica si fissa un limite al numero di tentativi e se non si trova un fattore si prova un diverso numero di partenza.

Si possono usare anche iterazioni basate su polinomi differenti, ma x(k + 1) = x(k)^2 + 1 mod n è semplice da calcolare e in pratica si è dimostrato efficace.

 

Nel 1980 R. Brent pubblicò una variante dell’algoritmo di Pollard; le differenze sono che l’iterazione è x(k + 1) = x(k)^2 + 2 mod n e a ogni passo si calcola MCD(xkxm, n), dove m è la massima potenza di 2 minore di k.

Nel nostro caso avremmo:

x0 = 2;

x1 = 22 + 2 mod 21583 = 6;

x2 = 62 + 2 mod 21583 = 38; MCD(6 – 38, 21583) = 1;

x3 = 262 + 1 mod 21583 = 1446; MCD(38 – 1446, 21583) = 1;

x4 = 14462 + 1 mod 21583 = 18950; MCD(38 – 18950, 21583) = 1;

x5 = 189502 + 1 mod 21583 = 4548; MCD(18950 – 4548, 21583) = 1;

x6 = 45482 + 1 mod 21583 = 7792; MCD(18950 – 7792, 21583) = 1;

x7 = 77922 + 1 mod 21583 = 2287; MCD(18950 – 2287, 21583) = 1;

x8 = 22872 + 1 mod 21583 = 7285; MCD(18950 – 7285, 21583) = 1;

x9 = 72852 + 1 mod 21583 = 20213; MCD(7285 – 20213, 21583) = 1;

x10 = 202132 + 1 mod 21583 = 20764; MCD(7285 – 20764, 21583) = 1;

x11 = 207642 + 1 mod 21583 = 1690; MCD(7285 – 1690, 21583) = 1;

x12 = 16902 + 1 mod 21583 = 7146; MCD(7285 – 7146, 21583) = 1;

x13 = 71462 + 1 mod 21583 = 21523; MCD(7285 – 21523, 21583) = 113.

In questo caso l’algoritmo di Brent impega 5 passi in più; in media il metodo di Brent non sembra più veloce dei quello di Pollard.

 

Negli ultimi decenni i progressi sulla scomposizione degli interi si devono più ai miglioramenti dei calcolatori, che a nuovi algoritmi.

Bibliografia

  • Balzarotti, Giorgio;  Lava, Paolo Pietro;  103 Curiosità matematiche, Milano, Hoepli, 2010.
  • De Koninck, Jean-Marie;  Those Fascinating Numbers, American Mathematical Society, 2009 -

    Un'inesauribile miniera di notizie sugli interi, informazioni e spunti per approfondimenti.

  • Honsberger, Ross;  In Pólya’s Footsteps, The Mathematical Association of America, 1997 -

    Una magnifica raccolta di problemi a sfondo matematico e geometrico di vario tipo.

  • Kuczma, E. Marcin;  International Mathematical Olympiads 1986 – 1999, Mathematical Association of America, 2003.
  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

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