Dimostrazione calcolo inverso in aritmetica modulo n

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
hexen
Messaggi: 237
Iscritto il: 01 gen 1970, 01:00
Località: polonia
Contatta:

Dimostrazione calcolo inverso in aritmetica modulo n

Messaggio da hexen » 29 mar 2005, 14:17

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?
[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]

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 29 mar 2005, 15:24

beh, lo puoi fare se e solo se $ a $ è invertibile...
comunque è lecito, ed il procedimento è corretto, ed effettivamente $ a^{\phi(n)} $ è l'inverso cercato.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 29 mar 2005, 15:30

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?
C'è da premettere che devi supporre $ (a,b)=1 $, altrimenti l'inverso banalmente non esiste e non c'è Teorema di Euler che tenga.

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."

hexen
Messaggi: 237
Iscritto il: 01 gen 1970, 01:00
Località: polonia
Contatta:

Messaggio da hexen » 29 mar 2005, 15:40

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 :wink:
[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]

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 30 mar 2005, 15:09

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!
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

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 30 mar 2005, 15:38

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 $.
$ n=pq $
$ 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 $

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 30 mar 2005, 15:45

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) $?
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

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 30 mar 2005, 15:47

Dato $ n $ te lo scomponi e ti trovi la $ \phi $ :D:D:D:D:D:D

Avatar utente
pazqo
Messaggi: 155
Iscritto il: 01 gen 1970, 01:00
Località: san giorgio di nogaro
Contatta:

Messaggio da pazqo » 30 mar 2005, 15:52

Boll ha scritto:Dato $ n $ te lo scomponi e ti trovi la $ \phi $ :D:D:D:D:D:D
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.
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

snagg
Messaggi: 70
Iscritto il: 14 mar 2005, 19:38
Contatta:

Messaggio da snagg » 30 mar 2005, 18:32

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`

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 31 mar 2005, 08:38

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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

snagg
Messaggi: 70
Iscritto il: 14 mar 2005, 19:38
Contatta:

Messaggio da snagg » 31 mar 2005, 13:25

chiedo venia

Rispondi