numeri autocifranti nel rsa

[hexen]

(spostato in Matematica non elementare --- EG)
ciao

vorrei calcolare sotto quali condizioni devono essere scelti i numeri primi p e q nel metodo RSA per trovare un numero auto
cifrante
dalla crittografia sappiamo che l'"equazione" di cifratura di un numero m è
$ $$c \equiv m^e \pmod n$$ $

Abbiamo un numero autocifrante quando c=m cioè $ $$m \equiv m^e \pmod n$$ $

(quanto segue è un mio calcolo che al 90% sento sia sbagliato)

Se MCD(n,m)=1 dividiamo per m e rimane modulo n, quindi $ $$m^{e-1} \equiv 1 \pmod n$$ $ Dal teorema di eulero-fermat abbiamo che dev'essere $ $$\Phi(n)=e-1$$ $

Se $ $$\gcd(n,m)=g \neq 1 $$ $ abbiamo che $ $$m^{e-1} \equiv 1 \pmod{\frac n g}$$ $ e che sempre dal teorema di eulero-fermat dev'essere $ $$\Phi(n/g)=e-1$$ $

Ma ora, mettendo che il procedimento finora è corretto e sapendo che $ $$e$$ $ è il primo numero primo con $ $$\Phi(n)$$ $, come continuo?

[frengo]

premetto che di cifratura non ci capisco quasi niente, ma in qualcosa ti posso aiutare:

$ m^{e-1} \equiv 1 \pmod n $ Dal teorema di Eulero-Fermat abbiamo che dev'essere $ \phi(n)=e-1 $

si, il teorema di Fermat dice che se $ \gcd(n,m)=1 $ allora $ m^{\phi(n)} \equiv 1 \pmod n $ , ma ciò non vuol dire che $ \phi(n) $ sia né il primo né il più piccolo.
Esempio:
$ n=7 $
$ \phi(n)=6 $
$ m=4 $
per Fermat abbiamo
$ 4^{\phi(7)} \equiv 4^{6} \equiv 1 \pmod 7 $
però
$ 4^3 \equiv 64 \equiv 1 \pmod 7 $
l'unica cosa che puoi concludere è che (se è $ e-1 $ è il minimo esponente) $ e-1|\phi(n) $

per la domanda "come continuo", non ho capito bene cosa stai cercando.
all'inizio citavi $ p $ e $ q $: cosa rappresentano?$ m $ e $ n $?

Ciao

EDIT:scusate ma Latex non lo proprio usare
edit (mod): corretto un po' il LaTeX, spero che l'autore non se la prenda --federico

[HiTLeuLeR]

Potrebbe tornare utile questo link, magari...

[hexen]

m è il numero da cifrare e n=pq, ho dimenticato di dirlo