Dimostrazione calcolo inverso in aritmetica modulo n
Dimostrazione calcolo inverso in aritmetica modulo n
Noto il numero a, voglio calcolare il numero $ $$b=a^{-1} $$ $ tale che $ $$ab=1 \mod n$$ $
Per il teorema di Eulero abbiamo $ $$a^{\Phi(n)} = 1 \mod n$$ $ e dobbiamo trovare un b tale che $ $$ab=1 \mod n$$ $
Uguagliando modulo n le 2 espressioni abbiamo
$ $ab & = & a^{\Phi (n)} $ $
$ $b & = & a^{\Phi (n)-1} \mod n$ $
ma non sono tanto convinto del passaggio di uguagliare le 2 espressioni e di quello che porta alla formulazione dell'ultima equazione
sono giusti?
Per il teorema di Eulero abbiamo $ $$a^{\Phi(n)} = 1 \mod n$$ $ e dobbiamo trovare un b tale che $ $$ab=1 \mod n$$ $
Uguagliando modulo n le 2 espressioni abbiamo
$ $ab & = & a^{\Phi (n)} $ $
$ $b & = & a^{\Phi (n)-1} \mod n$ $
ma non sono tanto convinto del passaggio di uguagliare le 2 espressioni e di quello che porta alla formulazione dell'ultima equazione
sono giusti?
[url=http://davidpet.interfree.it/renato.html:3r47vsho]Stamattina hanno suonato alla porta. Sono andato ad aprire e...[/url:3r47vsho]
[url=http://davidpet.interfree.it/jabber/index.html:3r47vsho]Guida introduttiva a Jabber[/url:3r47vsho]
[url=http://davidpet.interfree.it/jabber/index.html:3r47vsho]Guida introduttiva a Jabber[/url:3r47vsho]
C'è da premettere che devi supporre $ (a,b)=1 $, altrimenti l'inverso banalmente non esiste e non c'è Teorema di Euler che tenga.hexen ha scritto:non sono tanto convinto del passaggio di uguagliare le 2 espressioni e di quello che porta alla formulazione dell'ultima equazione
sono giusti?
L'aritmetica $ \mod n $ è molto simile all'aritmentica consueta sugli interi e quindi il passaggio di uguagliare le due espressioni è valido.
Per quanto riguarda la "divisione per $ a $" dell'ultimo passaggio, normalmente sarebbe questionabile. Però a te serve solo una delle due implicazioni.
A te occorre $ b = a^{\Phi (n)-1} \pmod n \Longrightarrow ab = 1 \pmod n $, che è certamente vera (moltiplico per $ a $ ambo i membri), e quindi mostri che, per quella scelta di $ b $, ottieni un inverso come si deve.
Ti faccio notare che l'algoritmo da te suggerito è in pratica di scarsa utilità, soprattutto se lo devi applicare a moduli molto grandi: genericamente il calcolo di $ \Phi(n) $ è di difficoltà paragonabile alla fattorizzazione di $ n $, che è notoriamente un problema difficile.
In pratica conviene usare l'algortimo euclideo esteso per il calcolo del M.C.D.
Esso, dati $ a $ e $ n $, ti permette di trovare rapidamente interi $ r $ e $ s $ t.c. $ ar + ns = 1 $. Se questa la leggi $ \mod n $...
@MaGo: $ a^{\Phi(n)-1} $, semmai...
Ciao. M.
Ultima modifica di Marco il 29 mar 2005, 15:41, modificato 1 volta in totale.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
sis conosco la difficoltà compulazionale della $ $$\Phi$$ $ pari a quella della fattorizzazione...
devo fare una presentazione sul RSA e con esempi calcolati a mano (quindi già ho i fattori che cmq sono numeri piccoli, roba tipo p=11 e q=13) quindi la forma che richiede il teorema di eulero mi basta e mi avanza, grazie cmq per l'algo di euclide
devo fare una presentazione sul RSA e con esempi calcolati a mano (quindi già ho i fattori che cmq sono numeri piccoli, roba tipo p=11 e q=13) quindi la forma che richiede il teorema di eulero mi basta e mi avanza, grazie cmq per l'algo di euclide
[url=http://davidpet.interfree.it/renato.html:3r47vsho]Stamattina hanno suonato alla porta. Sono andato ad aprire e...[/url:3r47vsho]
[url=http://davidpet.interfree.it/jabber/index.html:3r47vsho]Guida introduttiva a Jabber[/url:3r47vsho]
[url=http://davidpet.interfree.it/jabber/index.html:3r47vsho]Guida introduttiva a Jabber[/url:3r47vsho]
Già che siamo in tema, propongo un esercizio tanto facile quanto grazioso.
Sia n il prodotto di due primi distinti. Supponiamo di conoscere m =$ \phi(n) $. determinare i due primi, esprimendoli in funzione di m e n.
Se ritenete che sia un esercizio da problem solving olimpico, spostatelo pure in quella sezione. Secondo me è troppo facile (viste le teste che ci sono qua dentro...) (ovviamente è un esercizio per i "piccoli": Euler, giù le mani; idem tutti gli altri normalisti ).
ps: siccome $ \phi(n) $ è completamente determinato dai primi che compongono n, questo esercizio dimostra che fattorizzare n e trovarne $ \phi(n) $ è esattamente la stessa cosa!
Sia n il prodotto di due primi distinti. Supponiamo di conoscere m =$ \phi(n) $. determinare i due primi, esprimendoli in funzione di m e n.
Se ritenete che sia un esercizio da problem solving olimpico, spostatelo pure in quella sezione. Secondo me è troppo facile (viste le teste che ci sono qua dentro...) (ovviamente è un esercizio per i "piccoli": Euler, giù le mani; idem tutti gli altri normalisti ).
ps: siccome $ \phi(n) $ è completamente determinato dai primi che compongono n, questo esercizio dimostra che fattorizzare n e trovarne $ \phi(n) $ è esattamente la stessa cosa!
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
$ n=pq $pazqo ha scritto:Già che siamo in tema, propongo un esercizio tanto facile quanto grazioso.
Sia $ n $ il prodotto di due primi distinti. Supponiamo di conoscere $ m =\phi(n) $. determinare i due primi, esprimendoli in funzione di $ m $ e $ n $.
$ m=\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)=pq-(p+q)+1 $
Quindi
$ pq=n $
$ p+q=n-m+1 $
Per Vietè $ p $ e $ q $ sono le soluzione dell'equazione:
$ x^2-(n-m+1)x+n=0 $
certo (anche senon serve certo tirare in ballo Viéte...).
quindi, cosa si può dire su m e n, affinchè siano una coppia ammissibile?
$ (\frac{n-m+1}{2})^2 - n $ deve essere un quadrato perfetto.
può essere questo un modo per trovare subito quali sono gli m candidati a essere $ \phi(n) $ ?
cioè: dato n, è possibile dare,, tramite questa formula, una forte restrizione sui possibili valori di $ \phi(n) $?
quindi, cosa si può dire su m e n, affinchè siano una coppia ammissibile?
$ (\frac{n-m+1}{2})^2 - n $ deve essere un quadrato perfetto.
può essere questo un modo per trovare subito quali sono gli m candidati a essere $ \phi(n) $ ?
cioè: dato n, è possibile dare,, tramite questa formula, una forte restrizione sui possibili valori di $ \phi(n) $?
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
beh, si era discusso anche prima sul problema computazionale... fattorizzare n non è facile e la crittografia a chiave pubblica si basa sul calcolo della $ \phi(n) $, che come hai mostrato poc'anzi è equivalente.Boll ha scritto:Dato $ n $ te lo scomponi e ti trovi la $ \phi $ :D:D:D:D:D
A questo punto: con l'osservazione sul $ \Delta $ dell'eq. di 2° grado, è possibile rompere la crittografia in tempi ragionevoli? e se non lo è, perché? qual è la ragione teorica?
Stefano 'Pazqo' Pascolutti
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
A good mathematical joke is better, and better mathematics, than a dozen of mediocre papers -John Edensor LITTLEWOOD-
Use [tex]\LaTeX[/tex] in your math messages!
www.pazqo.altervista.org
rispondo dal "lato informatico" , come qualcuno di voi sa non troppo tempo da dei ricercatori indiani avevano trovato una soluzione polinomiale al problema , c'erano due problemi principali:
1)facevo delle forti assunzioni
2) la velocita` tra la risoluzione polinomiale e quella non polinomiale si faceva "sentire" solo con numeri molto grandi (molto oltre i numeri usati per gli algoritmi asimmetrici )
Quindi si tende a definire il problema della fattorizzazione un problema np(non deterministic polynomial) , ora alla domanda : "ma esistono davvero i problemi np(di qualunque genere essi siano) oppure siamo solo noi che non riusciamo a trovare una soluzione polinomiale?"
Non sono in grado di rispondere , senza dubbio pero` quando si parla di problemi np in termni informatici significa che se un computer "normale" supponiamo ad 3.6ghz riesce a risolvere un problema np dove si processa al piu` n , un computer molto piu` potente riuscira` a risolvere al piu` n+2, e un computer infinitamente piu` potente del secondo riuscira` a risolvere da n+2 in poi . Quindi allo stato attuale delle cose , computer quantistici a parte(chissa` in un futuro remoto) , la crittografia asimmetrica simil-RSA non e` facilmente "crackabile". Poi ovviamente ci sono i distinguo da fare sulle varie implementazioni , ma questo esula un po` dalla domanda di pazqo. Spero di essere stato esauriente , di non avervi annoiato troppo e mangari di avervi anche aiutato un po`
1)facevo delle forti assunzioni
2) la velocita` tra la risoluzione polinomiale e quella non polinomiale si faceva "sentire" solo con numeri molto grandi (molto oltre i numeri usati per gli algoritmi asimmetrici )
Quindi si tende a definire il problema della fattorizzazione un problema np(non deterministic polynomial) , ora alla domanda : "ma esistono davvero i problemi np(di qualunque genere essi siano) oppure siamo solo noi che non riusciamo a trovare una soluzione polinomiale?"
Non sono in grado di rispondere , senza dubbio pero` quando si parla di problemi np in termni informatici significa che se un computer "normale" supponiamo ad 3.6ghz riesce a risolvere un problema np dove si processa al piu` n , un computer molto piu` potente riuscira` a risolvere al piu` n+2, e un computer infinitamente piu` potente del secondo riuscira` a risolvere da n+2 in poi . Quindi allo stato attuale delle cose , computer quantistici a parte(chissa` in un futuro remoto) , la crittografia asimmetrica simil-RSA non e` facilmente "crackabile". Poi ovviamente ci sono i distinguo da fare sulle varie implementazioni , ma questo esula un po` dalla domanda di pazqo. Spero di essere stato esauriente , di non avervi annoiato troppo e mangari di avervi anche aiutato un po`
Ciao. Rientro per un attimo nel mio ruolo di moderatore. Vi ricordo che qui siamo nella sezione "Glossario e Toeria di Base". I ragionamenti su problemi computazionalmente difficili e compagnia cantando sono senz'altro interessanti, ma appertengono più di diritto alla zona "non elementare" del Forum (Matematica o Informatica, a seconda dei gusti).
Qui vorremmo che fosse uno spazio per tecniche semplici, spiegate chiaramente, possibilmente con applicazioni dirette al problem-solving olimpico.
Se vogliamo approfondire i temi, basta spostare la discussione in un altro filo.
Grazie. Ciao.
M.
Qui vorremmo che fosse uno spazio per tecniche semplici, spiegate chiaramente, possibilmente con applicazioni dirette al problem-solving olimpico.
Se vogliamo approfondire i temi, basta spostare la discussione in un altro filo.
Grazie. Ciao.
M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."