Risolvere sistema lineare nell'anello modulo n
Salve volevo proporre il seguente quesito:
dato l'anello Zn ed il sistema lineare congruenzale $Ax$= b (mod n) per n non primo,
calcolare X= $A^(-1)* B$.
Se fossimo in Zp, p (primo) si ricorre alla vecchia cara Eliminazione di Gauss-Jordan, mentre se p non è primo e
dunque siamo in Zn...ke si fa???
Con quale algoritmo si può risolvere??
Il suggerimento che mi hanno dato era basato sul fatto che:
- se i coefficienti in A erano definiti secondo il prodotto di numeri primi in un insieme
S={2,3,5,7,11,13,17,.....etc}, allora potevo adottare gauss-jordan normalmente e poi con il risultato che avevo in
X, ad uno ad uno mi calcolavo l'inverso...che ne dite???
Per completezza, l'insieme S è suggerito dal fatto che sto cercando di realizzare un classe java che mi consenta
dato un generatore nel campo del gruppo moltiplicativo Zp* , sia $\alpha$ un generatore di Zp* e $\beta$ un
intero in Zp*. I lLogaritmo Discreto (DL) di $\beta$ in base $\alpha$ , indicato con$ log_\alpha * \beta $, è
l’unico intero x, 0 = x = n-1, tale che $\alpha ^(x) = \beta$.
passi dell'algoritmo:
Dato un generatore a di un gruppo ciclico Zp* ed un elemento $ \beta$ ? Zp* determinare il logaritmo discreto y =
$ log_\alpha * \beta $.
1. Scegliere un sottoinsieme S = {p1, p2, · · · , pt} di Zp* tale che un significativo numero di elementi di Zp*
possano essere espressi come prodotto di elementi di S.
2. Determinare relazioni lineari che portino a logaritmi elementi di S nel modo seguente:
• Scegliere un intero casuale k, 0 = k = n -1 e calcolare a(k) alfa elevato alla k.
• Scrivere $\alpha ^(k) $ come prodotto di elementi di S del tipo :
$\alpha ^(k)$ =$\prod_{i=1}^t p_i^(c_i) con c_i >=0$ che stanno in Zp*
Se ciò è possibile portare il numero ai logaritmi: k $-=$ $\sum_{i=1}^t c_i *log_\alpha* p_i (mod p-1 )$.
altrimenti ripetere il punto 2.
• Ripetere il punto 2 fino a quando non si ottengono t+c relazioni lineari .
3. Lavorando modulo n, n non primo, risolvere il sistema c equazioni (con t non noto) determinate nel punto 2 per
ottenere
i valori $ log_\alpha * p_i $ , $ 1 <= i <= t $
Ekko il mio problema è proprio risolvere il sistema in Zp-1, poichè qui siamo in Zn e non so che fare...
KM POSSO FARE HELLPPPP!!???
Esempio
Sia p = 229. L’elemento $\alpha$ = 6 e un generatore di Z229 di ordine n = 228. Consideriamo$\beta$ = 13. Allora $
log_\alpha *13 $
calcolato come segue:
1. Consideriamo come base i primi 5 primi: S = {2, 3, 5, 7, 11}.
2. Consideriamo le seguenti 6 selazioni:
$6^(100)$ mod 229 = 180 = $2^(2) * 3^(2) * 5$
$6^(18) mod 229 = 176 = 2^(4) * 11 $
$6^(12) mod 229 = 165 = 3 * 5 * 11$
$6^(62) mod 229 = 154 = 2 * 7 * 11$
$6^(143) mod 229 = 198 = 2 * 3^(2) * 11$
$6^(206) mod 229 = 210 = 2 * 3 * 5 * 7$
Queste relazioni possono essere riscritte, considerando i logaritmi degli elementi di S, nel modo seguente:
$100 = 2 *log_6 2 + 2 *log_6 3 +log_6 5 (mod 228) $
$18 = 4 *log_6 2 + log_6 11 (mod 228) $
$12 = log_6 3 + log_6 5 + log6 11 (mod 228)$
$62 = log_6 2 + log_6 7 + log6 11 (mod 228)$
$143 = log_6 2 + 2 log_6 3 + log_6 11 (mod 228)$
$206 = log_6 2 + log_6 3 + log_6 5+ log_6 7 (mod 228)$
3. Risolvendo il sistema lineare di sei equazioni in cinque indeterminate
(i logaritmi xi = log6 pi) troviamo le soluzioni
$log_6 2 = 21, log_6 3 = 208, log_6 5 = 98, log_6 7 = 107 e$
$log_6 11 = 162$
ecco qsto è il risultato che non riesco ad ottere... Sigh
dato l'anello Zn ed il sistema lineare congruenzale $Ax$= b (mod n) per n non primo,
calcolare X= $A^(-1)* B$.
Se fossimo in Zp, p (primo) si ricorre alla vecchia cara Eliminazione di Gauss-Jordan, mentre se p non è primo e
dunque siamo in Zn...ke si fa???
Con quale algoritmo si può risolvere??
Il suggerimento che mi hanno dato era basato sul fatto che:
- se i coefficienti in A erano definiti secondo il prodotto di numeri primi in un insieme
S={2,3,5,7,11,13,17,.....etc}, allora potevo adottare gauss-jordan normalmente e poi con il risultato che avevo in
X, ad uno ad uno mi calcolavo l'inverso...che ne dite???
Per completezza, l'insieme S è suggerito dal fatto che sto cercando di realizzare un classe java che mi consenta
dato un generatore nel campo del gruppo moltiplicativo Zp* , sia $\alpha$ un generatore di Zp* e $\beta$ un
intero in Zp*. I lLogaritmo Discreto (DL) di $\beta$ in base $\alpha$ , indicato con$ log_\alpha * \beta $, è
l’unico intero x, 0 = x = n-1, tale che $\alpha ^(x) = \beta$.
passi dell'algoritmo:
Dato un generatore a di un gruppo ciclico Zp* ed un elemento $ \beta$ ? Zp* determinare il logaritmo discreto y =
$ log_\alpha * \beta $.
1. Scegliere un sottoinsieme S = {p1, p2, · · · , pt} di Zp* tale che un significativo numero di elementi di Zp*
possano essere espressi come prodotto di elementi di S.
2. Determinare relazioni lineari che portino a logaritmi elementi di S nel modo seguente:
• Scegliere un intero casuale k, 0 = k = n -1 e calcolare a(k) alfa elevato alla k.
• Scrivere $\alpha ^(k) $ come prodotto di elementi di S del tipo :
$\alpha ^(k)$ =$\prod_{i=1}^t p_i^(c_i) con c_i >=0$ che stanno in Zp*
Se ciò è possibile portare il numero ai logaritmi: k $-=$ $\sum_{i=1}^t c_i *log_\alpha* p_i (mod p-1 )$.
altrimenti ripetere il punto 2.
• Ripetere il punto 2 fino a quando non si ottengono t+c relazioni lineari .
3. Lavorando modulo n, n non primo, risolvere il sistema c equazioni (con t non noto) determinate nel punto 2 per
ottenere
i valori $ log_\alpha * p_i $ , $ 1 <= i <= t $
Ekko il mio problema è proprio risolvere il sistema in Zp-1, poichè qui siamo in Zn e non so che fare...
KM POSSO FARE HELLPPPP!!???
Esempio
Sia p = 229. L’elemento $\alpha$ = 6 e un generatore di Z229 di ordine n = 228. Consideriamo$\beta$ = 13. Allora $
log_\alpha *13 $
calcolato come segue:
1. Consideriamo come base i primi 5 primi: S = {2, 3, 5, 7, 11}.
2. Consideriamo le seguenti 6 selazioni:
$6^(100)$ mod 229 = 180 = $2^(2) * 3^(2) * 5$
$6^(18) mod 229 = 176 = 2^(4) * 11 $
$6^(12) mod 229 = 165 = 3 * 5 * 11$
$6^(62) mod 229 = 154 = 2 * 7 * 11$
$6^(143) mod 229 = 198 = 2 * 3^(2) * 11$
$6^(206) mod 229 = 210 = 2 * 3 * 5 * 7$
Queste relazioni possono essere riscritte, considerando i logaritmi degli elementi di S, nel modo seguente:
$100 = 2 *log_6 2 + 2 *log_6 3 +log_6 5 (mod 228) $
$18 = 4 *log_6 2 + log_6 11 (mod 228) $
$12 = log_6 3 + log_6 5 + log6 11 (mod 228)$
$62 = log_6 2 + log_6 7 + log6 11 (mod 228)$
$143 = log_6 2 + 2 log_6 3 + log_6 11 (mod 228)$
$206 = log_6 2 + log_6 3 + log_6 5+ log_6 7 (mod 228)$
3. Risolvendo il sistema lineare di sei equazioni in cinque indeterminate
(i logaritmi xi = log6 pi) troviamo le soluzioni
$log_6 2 = 21, log_6 3 = 208, log_6 5 = 98, log_6 7 = 107 e$
$log_6 11 = 162$
ecco qsto è il risultato che non riesco ad ottere... Sigh
Risposte
benvenuto/a nel forum.
credo che tu abbia qualche problema con apostrofi o accenti che la tua tastiera confonde con il simbolo di dollaro (\$) e che il sistema legge come inizio o fine di formule matematiche. fai caso a che cosa succede, controllando il messaggio in "anteprima" prima di inviarlo, e confrontando i caratteri usati, cercando di individuare quelli da non usare.
nel frattempo, ti consiglio di dare un'occhiata al regolamento e al modo di scrivere le formule (che trovi nella sezione "il nostro forum"). ciao.
credo che tu abbia qualche problema con apostrofi o accenti che la tua tastiera confonde con il simbolo di dollaro (\$) e che il sistema legge come inizio o fine di formule matematiche. fai caso a che cosa succede, controllando il messaggio in "anteprima" prima di inviarlo, e confrontando i caratteri usati, cercando di individuare quelli da non usare.
nel frattempo, ti consiglio di dare un'occhiata al regolamento e al modo di scrivere le formule (che trovi nella sezione "il nostro forum"). ciao.
ok.... modificherò il messaggio..
grazie per i suggerimenti.
ciao
grazie per i suggerimenti.
ciao
1)Crandall, Pomerance - Prime Numbers A Computational Perspective (2Ed , Springer, 2005)
2)Springer-Verlag An Introduction to Mathematical Cryptography
Nel primo libro suggerisce appunto di fattorizzare p-1, e risolvere il sistema per ogni primo q nella fattorizzazione. Infatti in java ho implementato Il metodo di gauss-jordan modulo p e funziona alla grande. Purtroppo quando ho a che fare con primi nella fattorizzazione di qualche poteza i= 1,2.....n non so che fare. Nel 2) suggerisce che quando si ha a che fare con un primo q elevato ad un i-esimo esponente per i= 1, 2, ..n, si può procedere trattando il metodo prima in q Z/qZ e poi le soluzioni che ho trovato di riportale in Z/$q^(i)$ q elevato alla i=1,2,...n. MA secondo te è lecito???
Cioè se ho p= 229, p-1= 228= $2^(2)*3*19$ da effettivamente 228, ora risolvo il sistema lineare per ogni fattore individuato in p-1,come anche tu stesso hai suggerito..Ma il mio dubbio è quando a che fare con il primo fattore ovvero $4= 2^(2)$;ke si fa??
risolvo il sistema modulo 2 con il mitico gauss e poi la soluzione che ottengo la elevo al quadrato??? E poi una volta che ho risolto il sistema con i vari moduli, nel primo e nel secondo libro dice di utilizzare il teorema cinese dei resti..detto fatto ho implementato anche quello soltnato che sempre nell'esempio di 229 con p-1. Visto che ho risolto modulo 2 il sistema,
ed elevato al quadrato le soluzioni ottenute, quando devo combinare queste soluzioni con le altre ottenuto con gli altri moduli devo farlo modulo 2 o modulo 4???
grazie per il prezioso aiuto.
2)Springer-Verlag An Introduction to Mathematical Cryptography
Nel primo libro suggerisce appunto di fattorizzare p-1, e risolvere il sistema per ogni primo q nella fattorizzazione. Infatti in java ho implementato Il metodo di gauss-jordan modulo p e funziona alla grande. Purtroppo quando ho a che fare con primi nella fattorizzazione di qualche poteza i= 1,2.....n non so che fare. Nel 2) suggerisce che quando si ha a che fare con un primo q elevato ad un i-esimo esponente per i= 1, 2, ..n, si può procedere trattando il metodo prima in q Z/qZ e poi le soluzioni che ho trovato di riportale in Z/$q^(i)$ q elevato alla i=1,2,...n. MA secondo te è lecito???
Cioè se ho p= 229, p-1= 228= $2^(2)*3*19$ da effettivamente 228, ora risolvo il sistema lineare per ogni fattore individuato in p-1,come anche tu stesso hai suggerito..Ma il mio dubbio è quando a che fare con il primo fattore ovvero $4= 2^(2)$;ke si fa??
risolvo il sistema modulo 2 con il mitico gauss e poi la soluzione che ottengo la elevo al quadrato??? E poi una volta che ho risolto il sistema con i vari moduli, nel primo e nel secondo libro dice di utilizzare il teorema cinese dei resti..detto fatto ho implementato anche quello soltnato che sempre nell'esempio di 229 con p-1. Visto che ho risolto modulo 2 il sistema,
ed elevato al quadrato le soluzioni ottenute, quando devo combinare queste soluzioni con le altre ottenuto con gli altri moduli devo farlo modulo 2 o modulo 4???
grazie per il prezioso aiuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo