Newsgroup: it.hobby.enigmi
Titolo: RSA

http://www.rsasecurity.com/rsalabs/challenges/factoring/index.html
In questo sito offrono parecchi dollari per la
fattorizzazione di alcuni numeri.
Per un numero composto da 174 cifre 10.000 dollari, fino a
200.000 dollari per 617 cifre.
Ci sono alcuni programmi in grado di affrontare agevolmente
il centinaio di cifre. 
Qualche idea per dividere il lavoro ?
mmmm... mi sa che e' dura.
:) dario

"Dario Uri" <Da...@Uriland.it> ha scritto nel messaggio
news:3B1573BF...@Uriland.it...

RSA-2048
Prize: $200,000
Status: Not Factored
Decimal Digits: 617
25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357
Questo me lo lasciate a me che ne ho bisogno dei 400 milioni...!
(io comincio a vedere se e' divisibile per 3 ok?)
fulvio

 (io comincio a vedere se e' divisibile per 3 ok?)
Ho già verificato la divisibilità per 2 e per 5
Entrambe negative.
Quanto mi spetta?
:-)))
ciao
paolo

 ha scritto nel messaggio
news:iNkR6.4565$vt.5...@news1.tin.it...

Avendo eliminato tutti i pari ed i multipli dispari di 5 , direi che
piu' del 50 % dei possibili fattori sono scartati, credi che
ci daranno almeno la meta'?
Inoltre se non ho sbagliato (e non lo rifaccio una seconda volta!),
la radice numerica e' 5 ....dunque eliminiamo pure 3 ed i suoi
multipli
Sara' mica un numero primo?????????
;-)
ciao
fulvio

 97122822120720357
Ci sono, ci sono!!!
E' divisibile per 1!!!
E anche per -1! E per il numero stesso! E pure per il suo opposto!!!
Scusate, vado a rimpolpare il mio conto in banca! :-)
MaxArt

> > 97122822120720357
E' primo!!!
La mia calcolatrice solare trovata nel Dash lo conferma!!!
Saluti dalle Hawaii
Stark

no dovrebbe semplicemente essere il prodotto di due 
numeri primi piuttosto grandi
per fattorizzare quelle bestie nere ci vogliono un 
bel po' di pc in rete (meglio se serie workstation) 
per fare un po' di calcolo distribuito
oppure un culo marziano e azzeccare tirando a caso
o mesi e mesi e mesi di calcolo di una cpu
ne avevan gia' fatto uno di concorso cosi'.. ma un 
altro tizio (forse era simon singh?)
l'han risolto ma la chiave era piu' piccola, se non 
erro e non di poco
ciao! (e auguri eh)

 bel po' di pc in rete (meglio se serie workstation)
Workstation? Ma scherzi? Io ci metterei una batteria di Sun 10000!
Questi giocattolini costano cosi' tanto che quando ce l'hanno consegnata
una, il camion e' arrivato scortato. Non sto scherzando.
--AG

In
questo sito offrono parecchi dollari per la fattorizzazione di alcuni
numeri. Per un numero composto da 174 cifre 10.000 dollari, fino a 200.000
dollari per 617 cifre...
.
.
.
TEMPO DI BUFALE...
.
Intendiamoci, non
ho la prova che questa sia una bufala, ma il sospetto e' fortissimo.
Perche' mai qualcuno dovrebbe darci 400 MLit per fattorizzare un numero?
Tempo fa una ditta di puzzle offri' 3 miliardi per la soluzione di un suo
prodotto: "Eternity". Mi adoperai a convincere gli amici che qualche conto
non tornava. Arrivai a predirre che il puzzle era cosi' difficile che se
per caso una buona equipe di matematici informatici l'avesse risolto,
sicuramente sarebbe saltato fuori uno sconosciuto che l'aveva risolto anche
lui (evento improbabile al quadrato). La cosa si e' verificata
puntualmente, eppure la maggior parte e' ancora convinta che Eternity sia
una cosa seria.
Il 1.o Aprile di quest'anno nella mia ultima pagina ho
offerto 1000 dollars al solutore di un mio puzzle impossibile. Pensavo
fosse chiaro a tutti che era una bufala dichiarata! Ricevo ancora emails di
gente che e' convinta di averlo risolto e vuole i 1000 $. E io sono
costretto a rispondergli cercando di convincerli che si sbagliano. Dovro'
toglierlo, ma se lo tolgo la gente cosa pensera'? Che l'ho tolto per non
pagare?
.
Ciao  :o)
Livio
http://www.geocities.com/liviozuc/
--------------------------------
Inviato via 
http://usenet.iol.it
 

che sia una bufala, non penso proprio
la rsa mica scherza
e non e' senza interesse la fattorizzazione
considera che la sicurezza di quasi tutti (almeno i 
piu' utilizzati e diffusi) sistemi di crittografia 
si basa su tale principio se non sul sistema rsa 
medesimo
ciao

eheh davvero??
d'accordo che sono cari, ma..
dopo che li rubi che ci fai :)
ci giochi a quake? :P
ciao!

davvero interessante il tuo sito, non lo avevo 
ancora visto
ciao!

 (io comincio a vedere se e' divisibile per 3 ok?)
Io faccio quella per due: non è divisibile.
:-)))))
--
Er Roscio.
(e neanche per cinque)

 ;-)
E se fosse un numero di Mersenne ?...
Quanto daranno per verificarlo ?... :-)))
--
Er Roscio.

#include "Roscio.h"

Qual'e' la particolarita' dei numeri di Mersenne?
---
Blackstorm
*Vicario d'Armi di idf*
Tittums e' il nostro gatto, ed ha le dimensioni di un rotolo di soldini.
Inarcava la schiena e bestemmiava come uno studente in medicina.
(Jerome Klapka Jerome)
E da oggi anche su ICQ! UIN 116647346 (nick: blacks)          

sik wrote:

E' una possibilita'.
Io ci metterei un emulatore C64 e mi farei una bella partita a Forbidden
Forest :-))
--AG

 Qual'e' la particolarita' dei numeri di Mersenne?
Se non ricordo male sono dei "falsi numeri primi"
ossia... Sembrerebbe che qualsiasi numero del tipo
2^x - 1  (questi sono i numeri di Mersenne)
sia primo quando x e' primo, invece non e' detto che sia cosi'.
Il piu' piccolo numero di Mersenne (con esponente primo) non primo
dovrebbe essere 2^11-1  cioe'  2047...
Chi me lo scompone?
ciao
fulvio

sia primo quando x e' primo, invece non e' detto che sia cosi'.
C'e` un thread su ism, pero` dovrebbero essere proprio primi. Ce ne
sono 38 in tutto, attualmente.
-- 
Ci sentiamo  |  Remigio Zedda  || Attenzione! campo "From:" alterato
ciao Remigio |                 ||==> E-mail: 
remi...@tiscalinet.it
-------------|      ..si` d'accordo.. ma con la Deb e` un'altra cosa!
/* Linux 2.2.17 su Debian GNU/Linux 2.2 Potato */

Dario Uri <Da...@Uriland.it> wrote in message
3B1573BF...@Uriland.it...

Ci sto facendo un pensierino...
Ma non capisco: il calcolo deve PER FORZA essere fatto
su dei PC ?... Perché non mi spiego come mai studenti e/o
docenti universitari che possono accedere a delle
"number-crunching machines", come i sistemi CRAY,
non si mettano a sparare soluzioni "remunerative"...
--
Er Roscio.

 sono 38 in tutto, attualmente.
Infatti... i numeri di Mersenne sono i numeri PRIMI che
possono essere espressi nella forma 2^n - 1, ma non tutti
i numeri espressi nella forma 2^n - 1 sono primi...
--
Er Roscio.


.
E allora la RSA che
fa? Un gioco a premi per allenare la gente a rompere le sue sicurezze? No,
non e' credibile. Vuole provare che le sue sicurezze sono sicure? Basta la
matematica. In un secolo ci sono 3x10^18 nanosecondi. Come si fa a
fattorizzare un numero di 174 cifre che sia il prodotto di due o tre numeri
primi? Praticamente impossibile con l'attuale tecnologia.
.
Ecco
un'ipotesi piu' realista del re:
Una ditta che fa sicurezza puo' contare
su validi algoritmi matematici, ma il suo punto debole e' l'uomo. Per
costruire un codificatore deve dire il segreto ad un certo numero di uomini
e se uno di questi e' una talpa il gioco e' fatto. Allora faccio in modo
che un gruppo di dipendenti venga a conoscenza di un tal algoritmo che in
realta' non usero' e lo annego in un concorso a premi dall'aria innocente.
Il dipendente disonesto si mette d'accordo con un suo lontano parente del
Montana, faranno a meta' del premio. Ma appena questo manda la soluzione,
quelli con il soprabito bianco e il bavero tirato su lo pizzicano e in 5
minuti vuota il sacco.
.
Ciao  :o)
Livio


 minuti vuota il sacco.
   Mi ricorda quel film con Will Smith e Gene Hackman. :-)

su un sito di matematica ho trovato un breve elenco 
di problemi irrisolti o congetture da approfondire:
http://www.claymath.org/prizeproblems/pvsnp.htm
su questa pagina, l'ultima frase puo' dare una 
risposta a come mai la rsa investe denaro in tale 
ricerca:
..non e' stato pero' finora provato che tale 
operazione (sta parlando della fattorizzazione, 
fatta come esempio, e problemi di questo tipo, dove 
se la soluzione e' nota sono di verifica immediata) 
debba realmente richiedere un tempo cosi' lungo per 
la soluzione: puo' semplicemente essere che non e' 
ancora stato scoperto come farlo in fretta.
ciao

 wrote in message
L9vR6.5207$Ww.9...@news2.tin.it...

Strano... a me ricorda gli sketch di Gin & Fizz a Zelig... :-)))
--
Er Roscio.

 mmmm... mi sa che e' dura.
Mooolto dura... ma nell'ambito della scrittura di un algoritmo
del genere, stavo cercando un metodo per l'estrazione della
radice quadrata, ma non sono riuscito a trovare traccia del
metodo di Tolomeo di Alessandria , che è l'unico - se non
ricordo male - che non abbia bisogno di effettuare operazioni
su un grosso numero di cifre. Tutti i metodi di approssimazione
che si usano adesso, necessitano di compiere moltiplicazioni
o divisioni sul numero nella sua interezza, o su numeri intermedi
molto grandi.
Chi può passarmi l'algoritmo di Tolomeo ?...
(saranno passati una trentina d'anni da quando l'ho studiato a scuola !...)
Ricordo che era una specie di "divisione" in cui si prendevano le cifre
a due a due... e poi ?... :-)))
--
Er Roscio.

a due a due... e poi ?... :-)))
Non sapevo fosse di Claudio(?) Tolomeo.
Guarda che c'e` in un thread di ism, di una o due settimane fa.
E` lunghetto, se no lo posterei qui.


 E` lunghetto, se no lo posterei qui.
Potevi mandarmelo in mail privata... :-)))
(scherzo; grazie della dritta; vado a vedere...)
--
Er Roscio.

 a due a due... e poi ?... :-)))
   Se sia quello di Tolomeo, non so. So che e` quello che mi hanno insegnato
a scuola. Te lo spiego direttamente con un esempio, cosi` nel frattempo
controllo se mi ricordo bene. (Scusa se non ho risposto prima, ma sono
pigro, e speravo lo facesse qualche altro lettore) :-) Leggi con un font a
passo fisso:
   Radice di 575,651:
   Iniziamo dalla parte intera, separandola in gruppi di due cifre (a
partire da destra):
   5|75,651
   Solo per il primo gruppo di cifre, in questo caso 5, cerchiamo a mano il
piu` grande intero, il cui quadrato sia contenuto nel 5 (cioe` 2), e
scriviamo (come in una divisione), il resto e` 1
_
575,651 | 2
4
=======
1
   Come nella divisione, preleviamo altre cifre dal "radicando", solo che
andiamo avanti a coppie di cifre, anziche` una alla volta:
___
575,651 | 2
4
=======
175
   Ora viene la parte piu` strana, prendiamo il doppio della radice fin qui
trovata (2 -> 4), e cerchiamo il piu` grande intero (tra 0 e 9) tale che il
risultato della moltiplicazione (40+n)n sia contenuto nel 175, in pratica:
41x1=41 (contenuto)
42x2=84 (contenuto)
43x3=129 (contenuto)
44x4=176 non contenuto (per poco... acc! :-))
   La prossima cifra della radice e` 3:
___
575,651 | 23
4
=======
175
129
=======
 46
   Poiche` adesso dobbiamo prelevare cifre dopo la virgola, mettiamo la
virgola dietro il 23 (come nella divisione):
___ __
575,651 | 23,
4
=======
175
129
=======
 4665
   Ora costruiamo la sequenza basata su 2x23=46:
461x1=461
462x2=924
....
469x9=4221 (contenuto anch'esso), quindi la prossima cifra e` 9:
___ __
575,651 | 23,9
4
=======
175
129
=======
 4665
 4221
=======
  444
   Continuiamo a prendere coppie di cifre, aggiungendo zeri, se necessario.
___ ___
575,651 | 23,9
4
=======
175
129
=======
 4665
 4221
=======
  44410
   E continuiamo, 239x2=478
4781x1=4781
4782x2=9564
....
4789x9=43101, la prossima cifra e` 9:
___ ___
575,651 | 23,99
4
=======
175
129
=======
 4665
 4221
=======
  44410
  43101
=======
   1309
   Aggiungiamo altri due zeri.
___ ___
575,651 | 23,99
4
=======
175
129
=======
 4665
 4221
=======
  44410
  43101
=======
   130900
   E andiamo avanti con 2399x2 = 4798
47981x1=47981
47982x2=95964
47983x3=143949, la prossima cifra e` 2:
___ ___
575,651 | 23,992
4
=======
175
129
=======
 4665
 4221
=======
  44410
  43101
=======
   130900
    95964
=======
    34936
Continua tu, io faccio la radice con la calcolatrice di windows e incollo il
risultato esatto (ammesso che la calcolatrice di windows dia risultati
esatti :-) ), che e` 23,992728064978355020275588896332
Ok, il nostro risultato e` giusto, spero sia chiaro il procedimento.
Ciao.
Salvatore.

 > Chi può passarmi l'algoritmo di Tolomeo ?...

Non è poi così strano, considera il seguente quadrato ( o
porzione di quadrato, se consideriamo che esso possa
continuare a destra ed in basso)
____a_______b_
|                       |       |
|                       |       |
|                       |       |a
|                       |       |
|__________|___ |
|                       |       |b
|__________|___|
come il quadrato di un binomio [a=20;b=x]
"a" la possiamo ricavare ad occhio dalla prima cifra del
radicando.
Radice di 5 = 2 [in realtà: radice di 500 = 20], deduciamo 4
dal 5 [in realtà 400 da 500].
Aggiungendo 2 cifre a destra, il radicando diventa 175,...
Ora dobbiamo trovare una 2° cifra "b" tale che 2ab+b^2 [=
(2a+b)*b] sia inferiore a 175.
Provando con "b" da 0 a 9, si avrà, appunto:
41x1
42x2
etc.
A questo punto, con a=23 e b=x, ci ritroveremmo di nuovo come
sopra e potremmo continuare ad libitum
Ciao
Gianni
--
Membro del Luigino Fans Club. Tessera n° 0001

 (2a+b)*b] sia inferiore a 175.
   Si`, in effetti hai ragione... Comunque mi sembrava strana dai tempi
delle medie, certo non cambiero` idea adesso. Sono un uomo tutto d'un
pezzo. :-)))