Algoritmi di fattorizzazione
Sono alla ricerca degli algoritmi per la fattorizzazione in numeri primi (nel caso limite il numero è primo).
Io ho realizzato qualcosa sino a 10 cifre, ma vorrei saperne di più su come si trattano i grandi numeri, scomposizione etc.
Grazie
res
Io ho realizzato qualcosa sino a 10 cifre, ma vorrei saperne di più su come si trattano i grandi numeri, scomposizione etc.
Grazie
res
Risposte
Ma che lavoro fai? Deve essere interessante occuparsi di queste cose..
Asimmetria nel senso che, detto papale e a quest'ora in cui non ho ancora cenato -mannaggia al pc- , è facile da codificare, ma molto difficile la funzione inversa.
Hai ragione, la chiave dinamica che cambia in continuazione deve raggiungere in qualche modo il destinatario e qui entra in ballo la tecnologia, potrebbe ad esempio essere recapitata sul cellulare e da questo trasferita via infrared al Pc, oppure sfruttare un mix di cellulare e gps che ti fa arrivare la chiave solo se sei nel tale luogo (a casa tua). Oppure operare su portatili con tutte queste funzioni integrate.
Hai ragione, la chiave dinamica che cambia in continuazione deve raggiungere in qualche modo il destinatario e qui entra in ballo la tecnologia, potrebbe ad esempio essere recapitata sul cellulare e da questo trasferita via infrared al Pc, oppure sfruttare un mix di cellulare e gps che ti fa arrivare la chiave solo se sei nel tale luogo (a casa tua). Oppure operare su portatili con tutte queste funzioni integrate.
manca un non..
cmq ci siamo capiti
cmq ci siamo capiti
in che senso parli di asimmetria?
sulla questione di chiavi dinamiche sono un po' scettico..
come potrebbe avvenire la dinamicità della chiave? In modo casuale oppure no.
Se è casuale non dovrebbe riuscire a decifrare il messagio neanche il destinatario,
se non è casuale va criptato il metodo di rigenerazione della chiave.. ma siamo punto e a capo..
(spero di aver detto troppe cavolate in un solo post)
sulla questione di chiavi dinamiche sono un po' scettico..
come potrebbe avvenire la dinamicità della chiave? In modo casuale oppure no.
Se è casuale non dovrebbe riuscire a decifrare il messagio neanche il destinatario,
se non è casuale va criptato il metodo di rigenerazione della chiave.. ma siamo punto e a capo..
(spero di aver detto troppe cavolate in un solo post)
In realtà nell'ultima parte del discorso non ti sono stato per niente dietro!
Però ti so dire che nel libro "crittografia" di Simon singh si legge che già esiste un metodo di crittografia inviolabile.
Ma inviolabile non per adesso.. per natura stessa del sistema crittografico.
Solo che ad oggi la tecnica consente di utilizzare tale metodo da pc a distanze ridicole (nell'ordine del metro).
Piuttosto inutili per ora.
Però ti so dire che nel libro "crittografia" di Simon singh si legge che già esiste un metodo di crittografia inviolabile.
Ma inviolabile non per adesso.. per natura stessa del sistema crittografico.
Solo che ad oggi la tecnica consente di utilizzare tale metodo da pc a distanze ridicole (nell'ordine del metro).
Piuttosto inutili per ora.
Ai tempi della guerra nei Balcani Clinton ordinò alla Cia di perforare i codici bancari di Milosevitch.
Forse un sistema per mandare all'aria l'Rsa esiste ma è top secret per due ragioni: la prima è poter entrare dove si vuole, la seconda è che se venisse conclamato, in poco tempo (e con i finanziamenti delle banche) qualche fiorente matematico escogiterebbe un sistema più ermetico, distruggendo un utile strumento in mano ai servizi segreti.
Tieni presente cmq che la potenza dell'RSA oltre all'idea dei fattori segreti è anche la sua asimmetria, pensata quando le comunicazioni e i sistemi biometrici non avevano questo grado di evoluzione. Non escluderei che tra non molto avremo sistemi superveloci e sicuri per il trasferimento di chiavi private dinamiche.
Forse un sistema per mandare all'aria l'Rsa esiste ma è top secret per due ragioni: la prima è poter entrare dove si vuole, la seconda è che se venisse conclamato, in poco tempo (e con i finanziamenti delle banche) qualche fiorente matematico escogiterebbe un sistema più ermetico, distruggendo un utile strumento in mano ai servizi segreti.
Tieni presente cmq che la potenza dell'RSA oltre all'idea dei fattori segreti è anche la sua asimmetria, pensata quando le comunicazioni e i sistemi biometrici non avevano questo grado di evoluzione. Non escluderei che tra non molto avremo sistemi superveloci e sicuri per il trasferimento di chiavi private dinamiche.
eheh..
comunque ho letto che esiste qualche metodo di attacco alla RSA (l'ho trovato scritto nel programma del corso di un esame di matematica).
forse potremmo investigare un po' prima e poi vediamo che idee abbiamo. E dopo magari aprire una sezione del forum dedicata!
comunque ho letto che esiste qualche metodo di attacco alla RSA (l'ho trovato scritto nel programma del corso di un esame di matematica).
forse potremmo investigare un po' prima e poi vediamo che idee abbiamo. E dopo magari aprire una sezione del forum dedicata!
Ho appena ricevuto una mail da Chris Caldwell che opera nel sito prima citato, a mia domanda se per definire primo è sufficiente verificare che non ci siano divisori nell'intervallo 2 - sqrt del numero, egli mi ha risposto con queste parole: "as long "between" is inclusive".
Ossia ho chiesto una banalità e anche in maniera tale da dover essere corretta
Ossia ho chiesto una banalità e anche in maniera tale da dover essere corretta
Quesito per tutti.
P*Q=N
dato il numero di cifre di N da quante cifre possono essere composti P e Q?
P*Q=N
dato il numero di cifre di N da quante cifre possono essere composti P e Q?
l'idea di fermarsi a cercare fino alla radice del numero l'avevo avuto anche io (credo conveniamo che non è proprio un lampo di genio ma una cosa piuttosto logica)
non mi eromai posto il problema del cambiamento di base.
io cercavo una strada per risalire ai numeri partendo da quel poco che si sà. Mi spiego.
p*q=N
diciamo che le ultime cifre di N siano a b c ( c unità, b decine etc..) note.
la cifra delle unità di p (chiamiamola d) viene moltiplicata per quella delle unità di q (poniamo e)
quindi il prodotto d*e=...c => ha come unità proprio c. poichè p e q sono primi sono anche dispari (se fosse 2 me ne sarei accorto!!) le combinazioni di d*e dispari che danno un certo numero nelle unità (c, noto) non sono tante..
Spero di essermi spiegato.
Però andando un po' avanti la faccenda può ingarbugliarsi (non sempre, però).
Ribadisco, se vuoi approfondiamo il discorso.. giusto per divertirsi!!
non mi eromai posto il problema del cambiamento di base.
io cercavo una strada per risalire ai numeri partendo da quel poco che si sà. Mi spiego.
p*q=N
diciamo che le ultime cifre di N siano a b c ( c unità, b decine etc..) note.
la cifra delle unità di p (chiamiamola d) viene moltiplicata per quella delle unità di q (poniamo e)
quindi il prodotto d*e=...c => ha come unità proprio c. poichè p e q sono primi sono anche dispari (se fosse 2 me ne sarei accorto!!) le combinazioni di d*e dispari che danno un certo numero nelle unità (c, noto) non sono tante..
Spero di essermi spiegato.
Però andando un po' avanti la faccenda può ingarbugliarsi (non sempre, però).
Ribadisco, se vuoi approfondiamo il discorso.. giusto per divertirsi!!
Scrivimi pure mi farà piacere.
Intanto mi riguardo i miei giochi perchè certamente c'è qualche errore mastodontico, l'unica certezza e che almeno uno dei fattori primi di n, a prescindere dal loro numero totale, giace tra 1 e la radice di n, quindi se la ricerca di fattori in quell'intervallo è infruttuosa il numero n è certamente primo, verità che però penso essere da sempre di dominio pubblico.
Pensando all'RSA che citi, se non sbaglio la codifica è a 128 bit, ossia corrisponde a:
3,4028236692093846346337460743177e+38
Ora per sapere i fattori di un numero di questa grandezza "basta" cercarne uno nell'intervallo che non oltrepassa il numero che ha come ordine di grandezza la sua radice, ossia:
18446744073709551616 (hai detto niente !)
Se ci si vuole poi divertire a cambiare la base di numerazione di questo numero, lasciando quella decimale in luogo di qualcos'altro, che però non è una delle classiche conosciute (ottale, hex, binaria, base 32, 64) ho notato delle strane e curiose proprietà (?) che aprono viste a possibili nuovi strumenti che "forse" ne snelliscono la fattorizzazione.
Qui mi fermo perchè non vorrei dire scemate, magari mi faccio aiutare da qualche guru e cerco di imbastire un modellino credibile o comunque degno di ragionamento.
Attendo tua mail
Saluti
Res
Intanto mi riguardo i miei giochi perchè certamente c'è qualche errore mastodontico, l'unica certezza e che almeno uno dei fattori primi di n, a prescindere dal loro numero totale, giace tra 1 e la radice di n, quindi se la ricerca di fattori in quell'intervallo è infruttuosa il numero n è certamente primo, verità che però penso essere da sempre di dominio pubblico.
Pensando all'RSA che citi, se non sbaglio la codifica è a 128 bit, ossia corrisponde a:
3,4028236692093846346337460743177e+38
Ora per sapere i fattori di un numero di questa grandezza "basta" cercarne uno nell'intervallo che non oltrepassa il numero che ha come ordine di grandezza la sua radice, ossia:
18446744073709551616 (hai detto niente !)
Se ci si vuole poi divertire a cambiare la base di numerazione di questo numero, lasciando quella decimale in luogo di qualcos'altro, che però non è una delle classiche conosciute (ottale, hex, binaria, base 32, 64) ho notato delle strane e curiose proprietà (?) che aprono viste a possibili nuovi strumenti che "forse" ne snelliscono la fattorizzazione.
Qui mi fermo perchè non vorrei dire scemate, magari mi faccio aiutare da qualche guru e cerco di imbastire un modellino credibile o comunque degno di ragionamento.
Attendo tua mail
Saluti
Res
Sì, ma fondamentalmente il metodo va per tentativi, giusto? Hai detto "una volta trovato.." il problema è proprio quella volta!
Se ti interessa e se migliori il tuo metodo divertiti con l'RSA. Tra le altre cose c'è un sito in cui ti danno un bel po' di soldi se gli trovi i fattori di un numero che ti danno loro (i più ci dovrebbero essere sulle 10 cifre). Se vuoi te lo posto.
Comunque l'argomento interessa anche me.. vuoi scambiare qualche idea sono a tua disposizione.
Aggiungo che a me risulta non esistere modo per la determinazione (in tempi ragionevoli) dei fattori primi (anche perchè altrimenti addio RSA e problema P Vs NP)
Se ti interessa e se migliori il tuo metodo divertiti con l'RSA. Tra le altre cose c'è un sito in cui ti danno un bel po' di soldi se gli trovi i fattori di un numero che ti danno loro (i più ci dovrebbero essere sulle 10 cifre). Se vuoi te lo posto.
Comunque l'argomento interessa anche me.. vuoi scambiare qualche idea sono a tua disposizione.
Aggiungo che a me risulta non esistere modo per la determinazione (in tempi ragionevoli) dei fattori primi (anche perchè altrimenti addio RSA e problema P Vs NP)
Beh direi di sì o meglio un procedimento che attacca il numero da punti particolari e cerca in ogni modo di sfrondarlo, appena trovato un fattore non banale (2,3,5,potenze di 10) il resto è ricorsione.
Ad esempio nell'ipotesi che abbia due fattori, questi saranno necessariamente ed esclusivamente il primo nell' intervallo da 1 e radice di n (di cui considero la parte intera) e il secondo tra radice di n ed n.
Questa è la partenza, il resto sono mie congetture e qualche trucco, che a me ha sempre funzionato me che non saprei dimostrare e forse è fondamentalmente sballato.
Mi chiedo solo se e quali sono gli approcci di altri alla fattorizzazione. Mi piacerebbe divertirmi con qualcosa di più funzionale dei miei esperimenti.
Ad esempio nell'ipotesi che abbia due fattori, questi saranno necessariamente ed esclusivamente il primo nell' intervallo da 1 e radice di n (di cui considero la parte intera) e il secondo tra radice di n ed n.
Questa è la partenza, il resto sono mie congetture e qualche trucco, che a me ha sempre funzionato me che non saprei dimostrare e forse è fondamentalmente sballato.
Mi chiedo solo se e quali sono gli approcci di altri alla fattorizzazione. Mi piacerebbe divertirmi con qualcosa di più funzionale dei miei esperimenti.
res.. fammi capire. se ti do un numero di dieci cifrei hai un algoritmo che ne trova i fattori primi?
Indipendentemente da quanti sono?
Indipendentemente da quanti sono?
Le 10 cifre sono un limite al quale ho lavorato, ma avrei potuto andare oltre.
Un limite però la macchina ce l'ha sempre; mi chiedo qual'è la regola per gestire numeri grandi a piacere, col solo vincolo del tempo più o meno grande in funzione della velocità dell macchina, non del numero di cifre che riesce a gestire.
Es. per verificare l'ultimo numero di Mersenne, tempo a parte, come si fa ? e li di cifre ce ne sono parecchie e nessun Pc lo può calcolare, però con opportuni algoritmi di partizione sì. Io cerco questi algoritmi.
Grazie
Res
Un limite però la macchina ce l'ha sempre; mi chiedo qual'è la regola per gestire numeri grandi a piacere, col solo vincolo del tempo più o meno grande in funzione della velocità dell macchina, non del numero di cifre che riesce a gestire.
Es. per verificare l'ultimo numero di Mersenne, tempo a parte, come si fa ? e li di cifre ce ne sono parecchie e nessun Pc lo può calcolare, però con opportuni algoritmi di partizione sì. Io cerco questi algoritmi.
Grazie
Res
Perchè fino a 10 cifre? In Pascal si possono gestire interi nel range $-2^63..2^63-1$, che hanno 18-19 cifre in decimale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo