Logaritmo discreto

estratto dal notebook di Ivo Muccioli (fonte [3])

1 - Radici primitive di p

Funzione per tracciare una tabella con tutte le esponenziazioni modulo p

findGen[p_] := 
      Module[{tabella  = 
            Table[PowerMod[i, j, p],  {i, 2, p - 1}, {j, 1, 
                p - 1}]}, 

prep = 
          Table[k^i  "mod " <> ToString[ p], {k, 2, 
              p - 1}]; 
For[iter = 1, iter < p - 1, 
          iter = iter + 1, 
          tabella[[iter]] = 
            Prepend[tabella[[iter]], 
              prep[[
                iter]]]]; 
tabella =  
          Join[{Prepend[Range[1, p - 1],  "i"]}, 
            tabella]; 
FrameBox[
            GridBox[tabella , 
              RowLines -> True,   ColumnLines -> True]] // 
          DisplayForm]

Esempio: p = 13

findGen[13]

Come si vede i generatori di 13 sono 2, 6, 7  e 11.Il numero di tali generatori è dato dalla funzione Φ di Eulero calcolata in (p-1)

EulerPhi[12]

Un altro modo per trovare un generatore è utilizzare la funzione PowerList. Essa cerca un generatore per il campo passato con la notazione GF[p] e ne riporta tutte le potenze.

<< Algebra`FiniteFields`

PowerList[GF[13]]

le potenze del generatore sono espresse in sequeza a partire da 0. Pertanto il secondo elemento  rappresenta il generatore stesso.

alpha  =  PowerList[
            GF[13]][[2]][[1]]

Costruimo pertanto la funzione

FindAGen[
        p_] :=   PowerList[
            GF[p]][[2]][[1]]

Proposizione 2.1
 α  è un generatore di \(TraditionalForm\`\(ℤ\_n\%*\)\) se e solo se (α^(((ϕ(n))/q))) ≢ 
        1 (mod n) per ogni divisore primo q di ϕ(n).

Tale proposizione può essere utilizzata per testare se un numero a caso è un generatore:

Esempio

Si supponga di avere n = 239 e di voler testare due α generati a caso come α1=55 e α2 = 7

n =  239;
alpha  = {55, 7}
FactorInteger[n - 1]

PowerMod[alpha, (n - 1)/2, n]
PowerMod[alpha, (n - 1)/7, n]
PowerMod[alpha, (n - 1)/17, n]

Come si vede 7 è un generatore mentre 55 non lo è.

2 - Logaritmo Discreto
Funzione per una ricerca esauriente

ExaustiveLog[alpha_, beta_, p_] := 
      For[i = 1, i < p, i = i + 1, 
        If[PowerMod[alpha, i, p] == beta, Return[i]]]

Esempi

ExaustiveLog[3, 1, 5]

ExaustiveLog[2, 6, 13]
ExaustiveLog[2, 4, 13]
ExaustiveLog[11, 5, 13]
ExaustiveLog[11, 9, 13]

La consultazione della tabella relativa all'esempio 2.5 costituisce una valida verifica dei risultati ottenuti nell'esempio

Algoritmo del Passo del Bambino - Passo del Gigante

L'algoritmo del Passo del Bambino-Passo del Gigante si basa sulla seguente osservazione: siano m = ⌈(n^(1/t))⌉ dove con n si indica il numero di elementi del campo di Galois e con t un parametro settabile all'interno dell'algoritmo e sia inoltre β il risultato di un'operazione di esponenziazione, ossia  β = (α^x) con x incognito. 
x si può anche scrivere come x = im+j con i≥0 e j<m.Da ciò deriva che (α^x) = (α^im) (α^j)e dunque β = \(TraditionalForm\`α\^x => \(β(α\^\(-m\))\)\^i = α\^j\)
Questa proprietà suggerisce che il calcolo di x può essere fatto calcolando i valori di i e j, uniche incognite dell'equazione precedente.

Algoritmo 5.1.1 (algoritmo del Passo del Bambino-Passo del Gigante)
Siano dati in ingresso un generatore α di un campo GF(n) con n primo e un elemento β ϵ GF(n).
1) Si calcola m = ⌈(n^t)⌉ con t ϵ [ 0 ;1 ].
2) Si costruisce una tabella con i valori ( j , (α^j) ) con j ϵ [0;m].
3) Si ordina la tabella per i valori di (α^j)
4) Si calcola χ = (α^(-m))
5) Si pone ξ = β
6) Per i che va da 0 a infinito si eseguono i seguenti passi:
	6a) Si controlla se ξ è presente nella seconda colonna della tabella
	6b) Se questo accade si restituisce x = im+j
	6c) Altrimenti di pone ξ = ξ · (α^(-m))

Al fine di valutare la bontà dell'algoritmo occorre valutane la sua complessità, sia in termini di potenza di calcolo, sia in termini di occupazione di memoria.

Teorema 5.1.2 (complessità dell'algoritmo 5.2)
La complessità dell'algoritmo 5.1.1 è data da:
a) la complessità dei passi iniziali (da 1 a 5) è data da (n^t)·(1 + (Subscript[log, 2]) (n^t)) operazioni.
b) le iterazioni del passo 6 richiedono in totale (n^(1 - t))·(1 + (Subscript[log, 2]) (n^t)) operazioni.
c) l'occopazione in memoria è data da (n^t)·(Subscript[log, 2])  n bit di memoria.

Dimostazione
La costruzione della tabella (passo 2) richiede m = ⌈(n^t)⌉ operazioni, mentre il suo ordinamento, utilizzando uno degli algoritmi di ordinamento più efficienti (ad esempio il merge-sort) richiede m·log m operazioni. La somma di  questi due termini costituisce la complessità di (a).
Per dimostrare la complessità del passo 6 occorre fare alcune considerazioni preliminari:
Dato che j ⩽ m e x = mi+j segue che i ⩽ (x/m) ≤ (n/m)≃ (n^(1 - t)). Pertanto le iterazioni del passo 6 sono dell'ordine di (n^(1 - t)). In ciascuna di esse si esegue una moltiplicazione (passo 6c) ed una ricerca nella tabella ordinata (passa 6a) che con un algoritmo di ricerca dicotomica richiede (Subscript[log, 2]) m operazioni.
Infine ciascun elemento della tabella occupa (Subscript[log, 2]) q bit di memoria e da questo deriva l'occupazione indicata in (c).

□

La presenza dell'algoritmo di un parametro t impostabile dall'utente, consente di ottenere nell'algoritmo stesso un giusto compromesso tra l'impiego di tempo e l'occupazione della memoria.

Osservazione 5.1.3
Ponendo t = (1/2)l'algoritmo si riduce ad una complessità pari a (Sqrt[n])sia per il tempo di calcolo, sia per l'occupazione di memoria.

Esempio 
In questo esempio come nei seguenti si considererà t = (1/2).
Come primo passo costruiamo un problema artificiale.

p =  Prime[81]
alpha  =  FindAGen[p]
x =  Random[Integer, {1, p - 2}]
beta  =  PowerMod[alpha, x, p]

A questo punto il nostro scopo è applicare l'algoritmo per trovare x, noti α, β e p.
▪ Passo 1 : calcolo di m

m =  Ceiling[p^(1/2)]

▪ Passo 2: costruzione della tabella

tabella = 
      Table[{i, PowerMod[alpha, i, p]},  {i, 0, 
          m}]
GridBox[Transpose[tabella], RowLines -> True, 
        ColumnLines -> True]  //  DisplayForm

▪ Passo 3: ordinamento della tabella

sortedTab  =  
      Sort[tabella, #1[[2]] < #2[[2]] &]
GridBox[Transpose[sortedTab], RowLines -> True, 
        ColumnLines -> True]  //  DisplayForm

▪ Passi 4 e 5:  Calcolo di κ e ξ

csi  =  beta;  chi  =  PowerMod[alpha, -m, p]

▪ Passo 6: esecuzione dell'iterazione

For[i = 0, 
      i < m, i++, 
If[
        MemberQ[sortedTab, {_, csi}], 
Return[
          m*i + sortedTab[[Position[
                      sortedTab, {_, 
                        csi}][[1]][[1]]]][[1]]], 
csi = 
          Mod[csi*chi, p]
]
]

Funzione per il calcolo dell'algoritmo passi del bambino, passi del gigante

LstepGstep[alpha_, beta_, p_] := 
      Block[{m = Ceiling[p^(1/2)], tabella, sortedTab, csi, chi}, 
        tabella = Table[{i, PowerMod[alpha, i, p]},  {i, 0, m}]; 
        sortedTab  =  
          Sort[tabella, #1[[2]] < #2[[2]] &]; 
csi  =  
          beta;  chi  =  PowerMod[alpha, -m, p]; 
        For[i = 0, i < m, i++, 
          If[MemberQ[sortedTab, {_, csi}], 
            Return[m*
                  i + sortedTab[[Position[
                          sortedTab, {_, 
                            csi}][[1]][[1]]]][[1]]], 
            csi = Mod[csi*chi, 
                p]]
]
]

Esempio

p =  114113; alpha  =  3;
x =  Random[Integer, {1, p - 2}]
beta  =  PowerMod[alpha, x, p]

LstepGstep[alpha, beta, p]

Tempi d'esecuzione
A questo punto possiamo fare una confronto sul tempo impiegato da questo algoritmo e dalla ricerca esaustiva

Timing[LstepGstep[alpha, beta, p]]
Timing[ExaustiveLog[alpha, beta, p]]

3 - Individuazione di un primo dallo standard SKIP (g = 2 e 512 bit)

alpha = 2;

primeEx = {15, 5, 2, 10, 15, 15, 3, 12, 14, 1, 11, 1, 2, 9, 4, 0, 1, 
          8, 1, 1, 8, 13, 7, 12, 8, 4, 10, 7, 0, 10, 7, 2, 13, 6, 8, 6, 12, 
          4, 0, 3, 1, 9, 12, 8, 0, 7, 2, 9, 7, 10, 12, 10, 9, 5, 0, 12, 13, 
          9, 9, 6, 9, 15, 10, 11, 13, 0, 0, 10, 5, 0, 9, 11, 0, 2, 4, 6, 13, 
          3, 0, 8, 3, 13, 6, 6, 10, 4, 5, 13, 4, 1, 9, 15, 9, 12, 7, 12, 11, 
          13, 8, 9, 4, 11, 2, 2, 1, 9, 2, 6, 11, 10, 10, 11, 10, 2, 5, 14, 
          12, 3, 5, 5, 14, 9, 2, 10, 0, 5, 5, 15};

Per prima cosa ricostruiamo la sua forma decimale e verifichiamo che sia realmente primo

p = FromDigits[primeEx, 16]
PrimeQ[p]

Scambio DH

mA =  Random[Integer, {1, p - 2}]
cA  = PowerMod[alpha, mA, p]
mB =  Random[Integer, {1, p - 2}]
cB  = PowerMod[alpha, mB, p]

kA = PowerMod[cB, mA, p]

kB = PowerMod[cA, mB, p]

kA == kB