Fattorizzazioni semiprimi e espansioni periodiche

Fattorizzazioni di un semiprimo con le espansioni periodiche di base 10 di 1/N

Tra le fattorizzazioni più curiose e simpatiche di un semiprimo N=p*q c'è la tecnica della "Espansione periodica in base 10 della frazione 1/N".

Facciamo un esempio: N=1517 con PARI/GP.

Step 1: troviamo la lunghezza del periodo T(1/N) della frazione 1/N

1/N=0.000659195781147000659195781147

dove per semplicità abbiamo marcato in bold rosso solo la "parte periodica" della frazione 1/N. Se contiamo le cifre di tale periodo (bold rosso) si ottiene che T(1/N)=15.

Step 2: Fattorizziamo la lunghezza del periodo della frazione 1/N

Fattorizziamo adesso la lunghezza del periodo T(1/N) = 15 = 3*5  (stesso risultato ottenibile da PARI/GP con factor(15)), dove k1=3 e k2=5

Step 3: troviamo il MCD (in inglese GCD) di N con 10^k1-1  e di N con 10^k2-1

GCD(1517,10^3-1)=37=p

GCD(1517,10^5-1)=41=q

Allora N=1517=37*41

Controprova

La contro-prova del metodo che valida l'esempio (poi  lo dimostriamo generalizzando) è la seguente:

Sappiamo che N=1517=37*41

Ora cerchiamo per p=37 e q=41 i più piccoli valori k1 e k2 tali che siano intere le quantità:

(10^k1-1)/p=3 

(10^k2-1)/q=5

Come si dimostra?

Intanto ricordiamo che lcm è il minimo comune multiplo (mcm), mentre LCM è il prodotto dei minimi comuni multipli in gioco; inoltre indichiamo con T il periodo di una frazione.

Se N=p*q è allora:

T(N)=LCM(T(p), T(q))

Se indichiamo  g = GCD[T(p),T(q)] allora  T(N) = T(p)T(q) / g.

Così per qualche fattorizzazione T(N) = abg noi avremo:

T(p) = ag e T(q) = bg

ed in conclusione

p = GCD [ N, 10^ag - 1 ]

q = GCD [ N, 10^bg - 1 ]

In tutto questo abbiamo usato la base B=10 ma nella dimostrazione al posto del 10 potevamo mettere genericamente B.

Simpatico no? E' un metodo che si applica bene e facilmente ad un numero semiprimo; mentre le cose si complicano di più se non è semiprimo  o se il periodo non si riesce a individuare.

Se N è semiprimo possiamo saperlo ad esempio in PARI/GP con la funzione bigomega(N) che se è semiprimo restituisce 2. La bigomega fornisce il numero di fattori primi anche se ripetuti.

Esiste sempre un periodo? No, non sempre.

Se N è primo, 1/N è periodica ad eccezione del caso N=2 e N=5

Se N è semiprimo N=p*q non è periodica se p=q oppure p e q sono fattori primi uguali a 2 o potenze di 2 o uguali a 5 o potenze di 5 o prodotti di 2 e 5

Le difficoltà:

1. In PARI/GP occorre scriversi un algoritmo per individuare il periodo

2. Non sempre la frazione è periodica

3. Per N grandi PARI/GP restituisce il valore in notazione esponenziale (esempio 23 E-21)

Cercare il periodo significa, da quanto visto, cercare il più piccolo valore k tale che B^k = 1 mod N. E una ricerca esaustiva non è sempre più veloce di una "Division Trial".

L'esempio di prima era banale. Esaminiamo N = 66167. T(66167)=1092

La fattorizzazione è:  1092 = 2*2*3*7*13

Qui dobbiamo vedere come combinare le possibili partizioni di 1092. Ad esempio dopo qualche tentativo 

si vede 1092=21*26*2 da cui ag=42 e bg=52. In questo caso T(p) e T(q) non sono coprimi.

Da qui:

GCD[66167,10^(21*2)-1]  =  127

GCD[66167,10^(26*2)-1]  =  521

Ovviamente basta calcolarne solo uno dei fattori, l'altro è ottenibile per divisione,

finchè non si ottiene un fattore non banale tale che GCD[N,B^k-1]. 

Questo tipo di fattorizzazione sicuramente potrebbe lavorare su numeri inferiori rispetto a N, ed è utile soprattutto per i semiprimi. Ma, come visto, non è detto che sia più veloce di una fattorizzazione di tipo trial.

Se avete idee a tal proposito, postatemele.

Alla prossima