Semiprimi fattorizzazione

[claugoru]

Volevo sfatare l'idea che un numero molto grande non possa essere fattorizzato in numeri primi in pochi secondi.
In rete non si trova molto sull'argomento e quello che si trova non dice niente salvo che è molto complicato o impossibile.

I numeri composti si dividono in due categorie, deboli e forti con una crescente difficoltà. Il semiprimo debole può essere di qualsiasi grandezza come lo è quello forte

Vi faccio un esempio

Questo numero è un numero debole con fattorizzazione in un decimo di secondo (cifre 260)
3075078893078405214196186192080591610393296729517876648623267590456373888048837307575259
2173385037335955677262580553574888172359106512134725420919513785664647701815130144933436
892777895761785936242219197749793058911484260325701737819419297192227501970384697339


Questo numero è un numero forte con fattorizzazione molto complicata (cifre 93)
260740604970814219042361048116400404614587956866941834618972331034545249334030655151
23005957

se vi chiedete quali siano i divisori di questi numeri e pensate che siano piccoli, vi sbagliate.

Questi sono i divisori primi del primo numero
55453393882416297191568283682861674068728741507516331503409591
61229242615611251246079948812208279156194782421922807143657948325959
x
55453393882416297191568283682861674068728741507516331503409591612292
42615611251246079948812208279156194782421922807143657948315821


e questi sono i divisori primi del secondo numero
11417981541647679048466287755595961091061973087
x
22835963083295358096932575511191922182123946011


Di questi semiprimi deboli ce ne sono una infinità e non appartengono a una grandezza specifica.

Perciò quando sentite parlare di numeri semiprimi grandi o grandissimi che non si possono fattorizzare sappiate che
se appartengono a una famiglia debole si possono fattorizzare in pochissimi secondi.

Preciso solo che i numeri primi sono stati trovati con l'algoristmo Rabin-Miller il quale tiene un margine d'errore molto basso che comunque è pur sempre un errore.
L'algoritmo però che fattorizza questi semiprimi trova sempre gli stessi numeri primi che lo hanno generato. Vi dico questo perchè se ci fosse un terzo divisore più piccolo lo avrebbe trovato

[Martino]

Ok ma non ho capito dove vuoi arrivare. Cosa sono i numeri forti e i numeri deboli?

[claugoru]

Ok ma non ho capito dove vuoi arrivare. Cosa sono i numeri forti e i numeri deboli?

Volevo solo arrivare a dire che la fattorizzazione dei semiprimi non dipende dalla loro grandezza ma dalla sua distribuzione all'interno dei suoi moltiplicatori. Questo li rende più forti o più deboli nell'essere fattorizzati. Questo principio vale per tutti e per questo anche un numero di migliaia di cifre può essere fattorizzato con estrema facilità. Questo perchè chi dice, e lo dicono in tantissimi in rete, che un semiprimo molto grande non può essere fattorizzato se non in tempi biblici, si sbaglia.

[Martino]

E come si fa a fattorizzare velocemente i semiprimi deboli?

[claugoru]

E come si fa a fattorizzare velocemente i semiprimi deboli?

Posso dirti che si basa sull'algoritmo di Pollard.