Scomposizione di numeri

[motaba]

la chiave di crittografia rsa si basa sul fatto che due numeri primi moltiplicati tra loro danno un numero. Il bello di questo numero e' che formato solo da questi due numeri a differenza di altri.
11*7= 77 che e' formato solo da 11 e 7
4*5=20 puo' essere formato da vari numeri 2*10 e 4*5
esempi...
dicono che sia impossibile risalire alla chiave per la decifratura perche' impossibile scomporre il numero nei due numeri primi..
ovvero se io ho 77 e' impossibile trovare in modo veloce 11 e 7 il che per numeri grandissimi e' vero...
PROVIAMO a proporre idee per la scomposizione?
tante teste possono creare qualcosa cissa'!!!!
non dimentichiamo che per un numero con chiave 1024 c'e' in palio 100.000 dollari.. per 2048 se non sbaglio 200.000 ecc....
cominciamo a buttare idee? che ne dite?


Idea ma se il numero finisce per 476478... posso dedurre che 8 e' formato solo dalla moltiplicazione di 1,8 e 2,4... quindi so che i numeri che sto cercando terminano per quelli????!!!!!

che il valore di radice sta in mezzo ai numeri che cerco es... radq 77 = 8,77
quindi uno e' piu' basso (7) e uno e' piu' alto (11)

ecc....

 

[Gen.le Andrea]

Ma non ti è mai passato di mente di andare a vendere gelati? LOL AHAHAH dai scherzo non te la prendere!

 

[Revan]

Idea ma se il numero finisce per 476478... posso dedurre che 8 e' formato solo dalla moltiplicazione di 1,8 e 2,4... quindi so che i numeri che sto cercando terminano per quelli????!!!!!

ecc....

Il numero in questione non terminerà mai per 8 o per qualunque altra cifra pari, altrimenti sarebbe divisibile per 2. Invece il numero in questione è prodotto di 2 numeri primi molto grandi (altrimenti sarebbe troppo facile risalire ad essi)

Ciao

Revan

 

[Rubigno]

è esplosa la mania della matematica.......mha, io la odio :nod:

 

[motaba]

Certo Che Non Termina Per 8, Ma Potrebbe Terminare Per 9 Ed Essere Un Numero Primo Ma Anche Divisibile Per 3 O Per 7 (7*7=49) O Per 9 Ecc...
Era Un Esempio, Non Si Vuole Scomporre Il Numero Di 2048 Che E':

25195908475657893494027183240048398571429282126204
032027777137836043662020707595556264018525880784406918290641249
515082189298559149176184502808489120072844992687392807287776735
971418347270261896375014971824691165077613379859095700097330459
748808428401797429100642458691817195118746121515172654632282216
869987549182422433637259085141865462043576798423387184774447920
739934236584823824281198163815010674810451660377306056201619676
256133844143603833904414952634432190114657544454178424020924616
515723350778707749817125772467962926386356373289912154831438167
899885040445364023527381951378636564391212010397122822120720357

Questo Termina Per 7 O 57 O 357 O 20357 Come Posso Trovare I Due Numeri Che Lo Formano...???????????
So Che Sono Numeri Primi!!!

 

[K.I.]

Mah, io direi di fare un programmino (magari in c) si prende il numero e si fa la radice quadrata, se siamo fortunati, abbiamo un quadrato esatto :D (cosa quasi impossibile :D:D: abbiamo trovato il risultato!!!). Altrimenti (caso effettivo) si fanno 2 cicli 1 che parte da 1 e l'altro dal numero stesso e si trovano tutti i numeri primi e si tenta con la moltiplicazione. il primo ciclo incrementa i numeri, il secondo li decrementa.
Tutti e due i cicli tendono ad arrivare al numero estratto con la radice quadrata.

Spero di essere stato chiaro.
Ciao!!!

 

[Revan]

Certo Che Non Termina Per 8, Ma Potrebbe Terminare Per 9 Ed Essere Un Numero Primo Ma Anche Divisibile Per 3 O Per 7 (7*7=49) O Per 9 Ecc...
Era Un Esempio, Non Si Vuole Scomporre Il Numero Di 2048 Che E':

25195908475657893494027183240048398571429282126204
032027777137836043662020707595556264018525880784406918290641249
515082189298559149176184502808489120072844992687392807287776735
971418347270261896375014971824691165077613379859095700097330459
748808428401797429100642458691817195118746121515172654632282216
869987549182422433637259085141865462043576798423387184774447920
739934236584823824281198163815010674810451660377306056201619676
256133844143603833904414952634432190114657544454178424020924616
515723350778707749817125772467962926386356373289912154831438167
899885040445364023527381951378636564391212010397122822120720357

Questo Termina Per 7 O 57 O 357 O 20357 Come Posso Trovare I Due Numeri Che Lo Formano...???????????
So Che Sono Numeri Primi!!!

Forse interpreto male il tuo ragionamento ma un numero per essere primo deve avere la caratteristica di essere divisibile solo per 1 e per se stesso.

Ciao

Revan

 

[K.I.]

SI, infatti il risultato della moltiplicazione di due numeri primi NON è un numero primo.

Ciao!!

 

[Revan]

Ovviamente gli algoritmi di criptazione sono pensati in modo da far si che tecniche di de-criptazione di tipo "forza bruta" come quello proposto da K.I. richiedano un tempo di esecuzione di anni (se non di più.....) anche se eseguiti sui computer più potenti esistenti (quelli dei centri di calcolo che possono contare su centinaia o migliaia di processori che lavorano in parallelo)

Ciao

Revan

 

[K.I.]

Ma dai, basta mettere 5 o 6 computer con linux che li fa vedere come un unico computer e fare i calcoli ;) (i 5 o 6 computer sono riferiti a quelli di Ludus Lorynz ecc.ecc...) :D:D:D

Non ho capito una cosa la chiave 2048? che significa che sono 2048 cifre???

Ciao!!!

 

[Revan]

Ma dai, basta mettere 5 o 6 computer con linux che li fa vedere come un unico computer e fare i calcoli ;) (i 5 o 6 computer sono riferiti a quelli di Ludus Lorynz ecc.ecc...) :D:D:D

Non ho capito una cosa la chiave 2048? che significa che sono 2048 cifre???

Ciao!!!

Si parla di chiavi a 2048 bit; cioè di un numero compreso fra 0 e 2^2048 circa uguale a 1,6*10^616; un numerino decimale a 616 cifre :biglaugh:

Ciao

Revan

 

[K.I.]

Si parla di chiavi a 2048 bit; cioè di un numero compreso fra 0 e 2^2048 circa uguale a 1,6*10^616; un numerino decimale a 616 cifre :biglaugh:

Ciao

Revan

ah, capisco :eyes: :eyes: :eyes: :eyes: :)

Ci serve solo un computer con achitettura a 256 Byte!! (2048 /8) :D:D :lol:

Ok, le cose si complicano, ma si possono superare...

Basta implementare un pò di algoritmi, ad esempio mettendo in ordine i numeri primi fino al numero dato e poi gestirsi i dati con ricerca binaria ecc ecc.. sfruttando il fatto che non si deve superare la metà dell'aaray!!!

Ciao!!

 

[Revan]

ah, capisco :eyes: :eyes: :eyes: :eyes: :)

Ci serve solo un computer con achitettura a 256 Byte!! (2048 /8) :D:D :lol:

Ok, le cose si complicano, ma si possono superare...

Basta implementare un pò di algoritmi, ad esempio mettendo in ordine i numeri primi fino al numero dato e poi gestirsi i dati con ricerca binaria ecc ecc.. sfruttando il fatto che non si deve superare la metà dell'aaray!!!

Ciao!!

Si, con queste tecniche riuscirai a ridurre un po' la complessità ma se riesci a far si che un PC (o anche un centro di cacolo) riesca a decriptare in tempi ragionevoli un algoritmo di questo tipo... beh significa che sei più bravo di tutti i matematici e di tutti gli informatici che ci hanno provato fin ora.

Ciao

Revan

 

[K.I.]

beh significa che sei più bravo di tutti i matematici e di tutti gli informatici che ci hanno provato fin ora.

Non dico questo ;) però penso che lavorando su algoritmi e matematica si possa fare. Il problema è far stare i numeri così grandi (2048 bit ) in un long (numero a 32 bit su piattaforma a 32 bit e a 64 su amd64) ad esempio... qui si potrebbero sfruttare i database.... (oracle o MS Sql Server)

 

[motaba]

si facendo un programma che calcola 1.000.000 di numeri al secondo (direi un ottimo programma con un ottimo computer) impiegherebbe anni....