Dimostrazione calcolo inverso in aritmetica modulo n

[hexen]

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?

[ma_go]

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

[Marco]

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.

[hexen]

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

[pazqo]

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!

[Boll]

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 $

[pazqo]

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

[Boll]

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

[pazqo]

Dato $ n $ te lo scomponi e ti trovi la $ \phi $ :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?

[snagg]

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`

[Marco]

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.

[snagg]

chiedo venia