Domanda scomposizione in fattori primi

[gerasia]

salve ragazzi, sto implementando un piccolo protocollo di cifratura e mi servirebbe una mano a scomporre un numero in fattori primi. Il numero è molto grande e quindi andarci per bruteforce è infattibile. Siete a conoscenza di un algoritmo ottimizzato per scomporre tale numero? Altrimenti devo pensare di condividere i due fattori primi e non mi piace come cosa

 

[St3ve]

Il problema che chiede di verificare se un numero è composto (i.e., non è primo) è nella classe di complessità NP e si pensa che non possa essere in P. Long story short: attualmente non si conoscono algoritmi efficienti per fattorizzare e si pensa che tali algoritmi non esistono (sui computer normali, perché sui quantum computer la storia cambia).

Detto questo, alcuni numeri sono più facili da fattorizzare rispetto ad altri. Ho accennato di alcune tecniche per fattorizzare in questa guida, leggendo l'intero thread vedrai che ho anche postato una challenge e ho mostrato come risolverla postando anche il codice.

Se il tuo algoritmo richiede di fattorizzare un numero per cifrare/decifrare, dovrai condividere i fattori. RSA, per esempio, si appoggia al problema della fattorizzazione per offrire sicurezza, ma non chiede di fattorizzare per cifrare/decifrare.

 

[gerasia]

grazie mille! Comunque dando un'occhiata alla tua guida ho notato che è andata persa la notazione matematica.

 

[St3ve]

grazie mille! Comunque dando un'occhiata alla tua guida ho notato che è andata persa la notazione matematica.

Si era semplicemente perso il trick della urlbar in Firefox, anche se in Chrome funzionava ancora. In ogni caso ho sistemato e, come prima, devi leggere il primissimo pezzo della guida (quello antecedente all'introduzione).
Fammi sapere se ti da problemi.

EDIT1: nevermind, ho fatto casino... mi servirà ancora un po' di tempo

EDIT2: risolto.