Congruenza con potenza

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Congruenza con potenza #70853

avt
damianoct
Punto
Salve, ho un dubbio riguardo ad una congruenza in cui compare una potenza: sto studiando la dimostrazione di un teorema in ambito di crittografia RSA, ma la domanda si riconduce ad un dubbio (probabilmente banale) di aritmetica modulare.


Non riesco a comprendere pienamente la seguente identità.

[(M) (M\sp{\phi(t)})\sp{k(q-1)}]\ \mbox{mod} p = (M\ \mbox{mod} p) [(M\sp{\phi(t)})\ \mbox{mod} p]\sp{k(q-1)}

L'unica proprietà che potrebbe essere stata sfruttata è:

[(a\ \mbox{mod} n) (b\ \mbox{mod} n)]\ \mbox{mod} n = (ab)\ \mbox{mod} n

ma allora, non dovrebbe essere (?)

(M\ \mbox{mod} p) [(M\sp{\phi(t)})\ \mbox{mod} p]\sp{k(q-1)}\ \mbox{mod} p


PS: l' "estendere" l'esponente k(q-1) al modulo è un'altra proprietà?
 
 

Congruenza con potenza #70871

avt
Galois
Amministratore
Ciao damianoct emt

Detto in parole povere il tuo dubbio risiede nella veridicità della seguente uguaglianza:

a^k \ (mod \ p) \overbrace{=}^{?} \left[a \ (mod \ p)\right]^k

con a, \ k, \ p numeri interi.

La risposta è che tale uguaglianza vale! il motivo è semplicissimo e lo hai ricordato tu stesso.

Infatti, come ben dici, in generale si ha:

[a \ (mod \ p)] \cdot [b \ (mod \ p)] = ab \ (mod p)

Pertanto, per definizione di potenza di un numero:

a^k \ (mod \ p) = \underbrace{a \cdot a \dots a}_{k \ \mbox{volte}} \ (mod p) =

Per l'uguaglianza prima ricordata (ma letta al contrario emt )

=\underbrace{[a \ (mod \ p)] \cdot [a \ (mod \ p)] \dots [a \ (mod \ p)]}_{k \ \mbox{volte}} = \left[a \ (mod \ p)\right]^k

emt
Ringraziano: Omega, Pi Greco, Ifrit, CarFaby
  • Pagina:
  • 1
Os