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)'* 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 α un generatore di Zp* e β un intero ∈Zp*. Il Logaritmo Discreto (DL) di β in base α, indicato con log(α) β, è l’unico intero x, 0 ≤ x ≤ n−1, tale che αx = β.
passi dell'algoritmo:
Dato un generatore α di un gruppo ciclico Zp* ed un elemento β ∈ Zp* determinare il logaritmo discreto y = log(baseα)β.
1. Scegliere un sottoinsieme S = {p1, p2, · · · , pt} di G 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 α(k) alfa elevato alla k.
• Scrivere α(k) come prodotto di elementi di S del tipo :
α(k) =(Simbolo produttoria)piesimi*ci , ci ≥ 0. che stanno in Zp*
Se ciò è possibile portare il numero ai logaritmi: k ≡(simbolo di somma)ci* og(baseα) pi (mod p-1 ).
altrimenti ripetere il punto 2.
• Ripetere il punto 2 fino a quando non si ottengono t+c relazioni lineari (c `e un piccolo intero positivo tale cheil sistema di t + c equazioni ha un’unica soluzione con grande probabilit`a).
3. Lavorando modulo n, risolvere il sistema c equazioni (con t non noto) determinate ottenere i valori di log p , 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 α = 6 `e un generatore di Z229 di ordine n = 228. Consideriamo β = 13. Allora log6 13 `e calcolato come segue:
1. Consideriamo come base i primi 5 primi: S = {2, 3, 5, 7, 11}.
2. Consideriamo le seguenti 6 selazioni:
6(elevato 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(base6) 2 + 2 log(base6) 3 + log(base6) 5 (mod 228)
18 ≡ 4 log6 2 + log6 11 (mod 228)
12 ≡ log6 3 + log6 5 + log6 11 (mod 228)
62 ≡ log6 2 + log6 7 + log6 11 (mod 228)
143 ≡ log6 2 + 2 log6 3 + log6 11 (mod 228)
206 ≡ log6 2 + log6 3 + log6 5 log6 7 (mod 228).
3. Risolvendo il sistema lineare di sei equazioni in cinque indeterminate
(i logaritmi xi = log6 pi) troviamo le soluzioni
log6 2 = 21, log6 3 = 208, log6 5 = 98, log6 7 = 107 e
log6 11 = 162.
ecco qsto è il risultato che non riesco ad ottere... Sigh
