Proprietà congruenze.
Ciao a tutti,
mi trovo in difficoltà nel giustificare un passaggio espresso dal testo su cui sto studiando..
Mi spiego:
Posti p = 2*q + 1 (p e q numeri primi), alpha elemento in Zp di ordine q, a scelto t.c. 1<=a<=q-1 e b = alpha^a mod p :
Il testo afferma che
se b = alpha^a mod p [ = indica congruenza]
allora:
b^((a)^-1) = alpha mod p [ = indica congruenza]
in prima analisi ho giustificato il passaggio in modo semplice, infatti..
se b = alpha^a mod p --> b^((a)^-1) = alpha^(a*((a)^-1)) mod p (lecito per l'invarianza rispetto all'elevazione a potenza di ambo i membri) -->
--> essendo (a*((a)^-1)) = 1 mod p --> b = alpha^1 mod p --> b = alpha^a mod p [in tutti i passaggi = indica congruenza]
ma svolgeno qualche calcolo numerico i conti non mi tornano! ad es.
posti p = 23, q = 11, alpha = 2, a = 5 risulta:
b = 2^5 mod 23 => 9
ed essendo 14 l'inverso di 5 modulo 23 dovrei secondo il ragionamento precedente dovrei ottenere che:
b^(a^-1) = alpha mod p -> 9^14 = 2 mod 23 [ = indica congruenza] .... MA NON E' COSI'
infatti
9^14 = 16 mod 23 ....
Qualcuno mi aiuta a capire dove sbaglio??Sono due giorni che ci sbatto la testa senza uscirne..
Grazie mille!
mi trovo in difficoltà nel giustificare un passaggio espresso dal testo su cui sto studiando..
Mi spiego:
Posti p = 2*q + 1 (p e q numeri primi), alpha elemento in Zp di ordine q, a scelto t.c. 1<=a<=q-1 e b = alpha^a mod p :
Il testo afferma che
se b = alpha^a mod p [ = indica congruenza]
allora:
b^((a)^-1) = alpha mod p [ = indica congruenza]
in prima analisi ho giustificato il passaggio in modo semplice, infatti..
se b = alpha^a mod p --> b^((a)^-1) = alpha^(a*((a)^-1)) mod p (lecito per l'invarianza rispetto all'elevazione a potenza di ambo i membri) -->
--> essendo (a*((a)^-1)) = 1 mod p --> b = alpha^1 mod p --> b = alpha^a mod p [in tutti i passaggi = indica congruenza]
ma svolgeno qualche calcolo numerico i conti non mi tornano! ad es.
posti p = 23, q = 11, alpha = 2, a = 5 risulta:
b = 2^5 mod 23 => 9
ed essendo 14 l'inverso di 5 modulo 23 dovrei secondo il ragionamento precedente dovrei ottenere che:
b^(a^-1) = alpha mod p -> 9^14 = 2 mod 23 [ = indica congruenza] .... MA NON E' COSI'
infatti
9^14 = 16 mod 23 ....
Qualcuno mi aiuta a capire dove sbaglio??Sono due giorni che ci sbatto la testa senza uscirne..
Grazie mille!
Risposte
Ciao.
Come fa $alpha$ ad avere ordine $q$ in $Z_p$ se $p=2q+1$? L'ordine di $alpha$ dovrebbe dividere $p$.
Secondo me il tuo testo sottintende che l'inverso di $a$ va fatto mod $p-1$ (non mod $p$).
Nel tuo esempio l'inverso di $5$ mod $22$ è $9$ e infatti $(2^5)^9 equiv 2$ mod $23$.
Come fa $alpha$ ad avere ordine $q$ in $Z_p$ se $p=2q+1$? L'ordine di $alpha$ dovrebbe dividere $p$.
Secondo me il tuo testo sottintende che l'inverso di $a$ va fatto mod $p-1$ (non mod $p$).
Nel tuo esempio l'inverso di $5$ mod $22$ è $9$ e infatti $(2^5)^9 equiv 2$ mod $23$.
Ciao, grazie per la risposta.
chiedo scusa ma ho sbagliato a scrivere: $alpha$ deve avere ordine $q$ in $Z_p^*$.
Comunque il testo è molto esplicito e dice..
" Since $beta equiv alpha^a mod p$,
implies that
$beta^(a^-1) equiv alpha mod p$ "
Ecco questo è il passaggio che mi blocca.. Non si fa alcuna menzione a $z-1$, anzi la premessa è "the scheme lives in $Z_p$; however, we need to be able to do computations in a multiplicative subgroup $G$ of $Z_p*$ of prime order"..
Non capisco
chiedo scusa ma ho sbagliato a scrivere: $alpha$ deve avere ordine $q$ in $Z_p^*$.
Comunque il testo è molto esplicito e dice..
" Since $beta equiv alpha^a mod p$,
implies that
$beta^(a^-1) equiv alpha mod p$ "
Ecco questo è il passaggio che mi blocca.. Non si fa alcuna menzione a $z-1$, anzi la premessa è "the scheme lives in $Z_p$; however, we need to be able to do computations in a multiplicative subgroup $G$ of $Z_p*$ of prime order"..
Non capisco
"Martino":
Ciao.
Come fa $alpha$ ad avere ordine $q$ in $Z_p$ se $p=2q+1$? L'ordine di $alpha$ dovrebbe dividere $p$.
Secondo me il tuo testo sottintende che l'inverso di $a$ va fatto mod $p-1$ (non mod $p$).
Nel tuo esempio l'inverso di $5$ mod $22$ è $9$ e infatti $(2^5)^9 equiv 2$ mod $23$.
Se si eleva $alpha$ ad un esponente che è $1$ mod $p$ non è detto che si ottenga $alpha$.
Per esempio non c'è nessun motivo per cui si debba avere $alpha^{p+1} equiv alpha$ mod $p$, infatti dato che $alpha$ ha ordine $q$ hai $alpha^{p+1} equiv alpha^2$ mod $p$.
Secondo me la cosa sottintesa è che l'inverso di $a$ va fatto modulo $q$. Infatti si può pensare all'insieme degli esponenti di $alpha$ come a $ZZ_q$ (proprio perché $alpha$ ha ordine $q$). E si ha appunto $alpha^{nq+1} equiv alpha$ mod $p$.
Potresti provare ad adottare questa interpretazione e vedere se è coerente con quello che viene detto dopo nel testo.
Per esempio non c'è nessun motivo per cui si debba avere $alpha^{p+1} equiv alpha$ mod $p$, infatti dato che $alpha$ ha ordine $q$ hai $alpha^{p+1} equiv alpha^2$ mod $p$.
Secondo me la cosa sottintesa è che l'inverso di $a$ va fatto modulo $q$. Infatti si può pensare all'insieme degli esponenti di $alpha$ come a $ZZ_q$ (proprio perché $alpha$ ha ordine $q$). E si ha appunto $alpha^{nq+1} equiv alpha$ mod $p$.
Potresti provare ad adottare questa interpretazione e vedere se è coerente con quello che viene detto dopo nel testo.
Ciao!
Ti ringrazio molto!Penso proprio che tu abbia centrato il nocciolo della questione!Ho cercato di andare avanti e mi sembra tutto coerente con questa chiave di lettura: si sottointende che i moduli siano trattati in $z_q$!!
Non so come mai questo non è specificato (eppure il documento è ben dettagliato!).
Spero di poter essere ugualmente utile ad altri utenti del forum per ricambiare!
Ti ringrazio molto!Penso proprio che tu abbia centrato il nocciolo della questione!Ho cercato di andare avanti e mi sembra tutto coerente con questa chiave di lettura: si sottointende che i moduli siano trattati in $z_q$!!
Non so come mai questo non è specificato (eppure il documento è ben dettagliato!).
Spero di poter essere ugualmente utile ad altri utenti del forum per ricambiare!
"Martino":
Se si eleva $alpha$ ad un esponente che è $1$ mod $p$ non è detto che si ottenga $alpha$.
Per esempio non c'è nessun motivo per cui si debba avere $alpha^{p+1} equiv alpha$ mod $p$, infatti dato che $alpha$ ha ordine $q$ hai $alpha^{p+1} equiv alpha^2$ mod $p$.
Secondo me la cosa sottintesa è che l'inverso di $a$ va fatto modulo $q$. Infatti si può pensare all'insieme degli esponenti di $alpha$ come a $ZZ_q$ (proprio perché $alpha$ ha ordine $q$). E si ha appunto $alpha^{nq+1} equiv alpha$ mod $p$.
Potresti provare ad adottare questa interpretazione e vedere se è coerente con quello che viene detto dopo nel testo.
Prego ciao alla prossima 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo