"METODO", N. 19/2003

Francesco Di Noto – Anna Rita Tulumello
(Gruppo Eratostene – Caltanissetta)
TEOREMA N° 13:
È POSSIBILE FATTORIZZARE UN PRODOTTO N=p×q CON p E q PRIMI,
MA DIVERSI DA 2 E 3, SENZA USARE LA TAVOLA DEI NUMERI PRIMI,
IN MODO LINEARE, PIÙ SEMPLICE, E FORSE ANCHE PIÙ VELOCE

DIMOSTRAZIONE

In base al Teorema n° 1, tutti i numeri primi, (tranne il 2 e il 3), i loro prodotti e le loro potenze hanno la forma generale:

p; p×q; px = 6n±1

Un prodotto tra primi, quindi si configurerebbe in particolare con la forma:

N = p×q = (6a±1) (6b±1) con "a" e "b" interi.

Poiché anche i numeri primi sono della forma 6n±1, per fattorizzare N basta dividere N per tutti i valori di 6a±1 con "a" da 1 a

per ottenere q=(6b±1).

=(6b±1)

nel caso in cui p=q, avremo un quadrato (6a±1)2

o una potenza: (6a±1)x

ma non lo sappiamo a priori, per cui dobbiamo applicare la (1.2); che ci evita di memorizzare nel computer la lista dei numeri primi, almeno fino a (ricordiamo che, così come in una somma "a"+"b" uno dei due numeri è inferiore o al massimo uguale a N/2, così in una prodotto "a×b" oppure nel nostro caso due primi p×q, uno dei due numeri è minore o al massimo uguale a .
Per cui, per fattorizzare N, prima bastava dividere N per tutti i primi fino a , mentre ora, con la (1.2), basta dividere N per tutti i valori progressivi (6a±1) con "a" fino /6+ 1, evitando così di memorizzare nel computer la lista dei numeri primi, che sono compresi automaticamente (tranne sempre il 2 e il 3) nella forma (6a±1).
Il numero delle divisioni possibili sarà un po' maggiore che col vecchio sistema; ma, evitando la lista dei primi e programmando al loro posto la relazione 6a±1 con "a" da 5 (= 6×1-1) fino a

/6+ 1, il calcolo elettronico potrebbe essere più veloce, usando tutti possibili valori della relazione 6a-1; e se non si trova q, si ripetono le divisioni, con i valori della relazione 6a+1.
Per esempio, per un numero N prossimo a N=104=10.000, avremo ; con il vecchio metodo dovremmo fare 22 divisioni, poiché fino a 100 ci sono 22 primi, escludendo il 2 e il 3 (abbiamo posto N=p×q con p e q diversi da 2 e 3; il teorema è finalizzato a semplificare la fattorizzazione di un numero di tipo RSA, usato per le cifrature di messaggi usando come chiave un prodotto di due grandi numeri primi, e quindi esclusi il 2 e il 3).
Con il nuovo metodo occorre invece fare 17 divisioni per la forma 6a-1 e 17 divisioni per la forma 6a+1 (poiché 100/6=16 multipli di 6, più 1 per maggiore sicurezza=17, e 17×2=34 divisioni.
34 è un numero di divisioni maggiore di 22 dell'altro metodo, ma permette di evitare la memorizzazione e l'uso diretto dei numeri primi; e il semplice calcolo progressivo delle due forme 6a-1 e 6a+1, con "a" da 5 a /6+ 1, potrebbe rendere ugualmente la fattorizzazione al computer di N molto più veloce dei metodi di calcolo attuali; con i quali, con numeri RSA molto grandi occorrerebbe più tempo; per esempio per fattorizzare RSA-129 (composto da 129 cifre) sono occorsi ben 8 mesi a 1600 computer connessi in Internet; ma un futuro computer quantistico, si prevede, impiegherebbe solo 8 secondi!).

ESEMPIO

N =10.001=73×137=(12×6+1)×(23×6-1)
P=73 è inferiore a =100

n=(10.001+1)/6=1667

a=(73-1)/6=12

b=(137-1)/6=23

N/P=10.001/73=(1667×6+1)/(12×6-1)=23×6-1=137=q

Con la fattorizzazione classica occorrevano 19 divisioni (73 è il 19° numero primo dopo il 2 e il 3).
Con la nuova fattorizzazione, ne occorrono divisioni 100/6=16 della forma 6a-1, tra le quali non si trova q, e 12="a" divisioni della forma 6a+1; infatti alla 12ª divisione, per 6×12+1=73, si ha il risultato intero q=137, l'altro fattore.
In totale, quindi, 16+12=28 divisioni anziché 19 della fattorizzazione classica, ma si è evitato l'uso della tavola dei numeri primi, cosa che con i computer avrebbe richiesto più tempo.
Si propone un confronto temporale tra i due calcoli, e un confronto tra i due software, per N molto grandi.
Si presume un tempo minore e un software più semplice per il secondo metodo descritto da questo Teorema n° 13.

Nota al Teorema n° 13

Con la (1.2) si trasformerebbe un probabile complesso calcolo nonpolinominale, come la fattorizzazione, in un più semplice calcolo lineare, di tipo P=k×N; nel nostro caso P=q=N/(6a±1) con k=6 ed N coincidente con "a"=tutti i numeri interi fino a un certo /6+ 1; qui, però, N è il numero da scomporre e non il simbolo "N" della P=k×N.
Riporto dal libro di fisica quantistica Un’occhiata alle carte di Dio di Gian Carlo Ghirardi (EST), pag. 291:

Si possono dare gradi molto diversi di complessità (computazionale). Per i nostri scopi considereremo solo i cosiddetti casi lineare, polinomiale, nonpolinominale ed esponenziale.
Diciamo che il problema ha complessità lineare quando il numero di passi necessari per risolverlo cresce proporzionalmente a N [caso nostro della 1.2, ndA]. Detto P questo numero, si avrà allora P=k×N con k una costante positiva che non ci interessa precisare. Si dirà invece che la complessità risulta polinomiale, quando il numero P cresce come un polinomio di N, per esempio P=aN3+bN2+c… Se non si dà nessuno dei casi considerati, si dirà che la complessità computazionale del problema è nonpolinominale.
Tra questi tipi di problemi sono particolarmente rilevanti quelli che presentano una complessità esponenziale…
Passiamo ora a considerare una famiglia di problemi che presentano una caratteristica peculiare. Si considerano due operazioni che sono l'inverso l'una dall'altra.
Accade, in certi casi, che mentre è relativamente semplice eseguire l'operazione diretta (tipicamente … lineare o al più polinomiale) l'operazione inversa può risultare estremamente ardua e costituire un problema con difficoltà computazionale non polinomiale. Il più noto, e forse il più studiato problema di questo tipo è quello di decomporre nei suoi fattori il prodotto di due numeri primi.
Ovviamente il problema diventa interessante quanto il numero delle cifre N del prodotto risulta notevolmente elevato…
Anche se non è stato possibile dimostrare che l'operazione inversa cui siamo interessati presenta effettivamente una complessità nonpolinominale, nessuno è stato capace di elaborare un algoritmo che la rende facilmente eseguibile.
Il procedimento da seguire risulta più o meno quello ovvio, vale a dire quello di provare a dividere il prodotto per tutti i numeri primi a partire da 2 in su, fino a che si ottenga una divisione senza resto.


Il nostro algoritmo "lineare" della (1.2), invece, potrebbe semplificare l'operazione di fattorizzazione, non tenendo presente la lista dei numeri primi fino a .