Indexcalculusalgoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de groepentheorie, een onderdeel van de wiskunde, is het indexcalculusalgoritme een algoritme om voor sommige groepen het discrete logaritme, h = gn, op te lossen, waar g en h elementen van groep, G, zijn. Een discreet logaritme is gedefinieerd op een eindige groep G. Voor g als voortbrenger van G en h \in G wordt naar de oplossing van h=g^n gevraagd.

Het algoritme[bewerken]

Het indexcalculusalgoritme kan onder andere toegepast worden op eindige lichamen.

De methode voor priemlichamen \mathbb{F}_p en binaire lichamen \mathbb{F}_{2^m} kan als volgt beschreven worden:

In priemlichamen[bewerken]

\langleg\rangle is een subgroep van \mathbb{F}_p^*, h \in \langleg\rangle
Voor welke n \in\mathbb{Z} geldt h=g^n (mod p)

Het algoritme maakt gebruik van een factorbasis van een aantal kleine priemgetallen, B={ (-1), 2, 3, 5, 7,..., r}

Stap 1:
Zoek een aantal elementen van \langleg\rangle die de eigenschap hebben dat ze te ontbinden zijn in priemfactoren uit de verzameling B.
Die groepselementen schrijven we als g^{r_i} =(-1)^{e_1}\cdot p_2^{e_2}\cdot\dots \cdot p_k ^{e_k}

Stap 2:
Neem aan beide zijden de logaritme. Zo ontstaat een stelsel van lineaire vergelijkingen waaruit de discrete logaritmen van de gebruikte priemgetallen op te lossen zijn.

Stap 3:
Zoek vervolgens naar een element g^{i} zodat h \cdot g^{i} te ontbinden is met priemfactoren uit B.
h \cdot (g^{r_i}) = (-1)^{e_1} \cdot p_2^{e_2} \cdot ... \cdot p_k^{e_k}
Door aan beide zijden de logaritme te nemen volgt de waarde van n.
Met behulp van onderstaand voorbeeld zijn de drie stappen van het algoritme uitgewerkt.

In binaire lichamen[bewerken]

De elementen van het eindige lichaam \mathbb{F}_{2^m} worden weergegeven als veeltermen in \mathbb{F}_2[x] met een graad die ten hoogste ( m-1) is. De operatie is vermenigvuldigen modulo een vastgestelde veelterm van de graad n, f(x) in \mathbb{F}_2[x], die niet te ontbinden is.
Kies voor factorbasis B elementen uit de verzameling van alle niet te ontbinden veeltermen in \mathbb{F}_2[x] met als graad niet meer dan een tevoren vastgestelde bovengrens.

Stap 1:
Zoek veeltermen g^k mod f(x), met g als voortbrenger van \mathbb{F}_{2^m} die een product zijn van veeltermen uit B.

Stap 2:
Precies als bij priemlichamen zijn de logaritmen van de veeltermen te vinden door een stelsel vergelijkingen op te lossen.

Stap 3: Zoek vervolgens naar een veelterm g^{i} zodat h \cdot g^{i} te ontbinden is met veeltermen uit B.
Door aan beide zijden de logaritme te nemen volgt de waarde van n.

Voorbeelden[bewerken]

In priemlichamen[bewerken]

We gaan uit van \mathbb{F}_{2003}^*= \langle5\rangle met p=2003.
We kiezen nu h = 543 uit die groep en willen n oplossen uit h = 5^n mod 2003.

Stap 1:
Neem B = {(-1), 2, 3, 5, 7, 11, 13, 19}. Dit is een kleine factorbasis.
Het nadeel daarvan is dat je langer moet zoeken naar getallen die daarmee te ontbinden zijn, het voordeel is dat het op te lossen stelsel beperkt van omvang is.
We kiezen nu willekeurig getallen uit \langle5\rangle en ontbinden die in priemgetallen. Alleen de getallen die m.b.v.B te ontbinden zijn kunnen we gebruiken.

964 = 2^2 \cdot 241^1
zullen we niet gebruiken.

Na een aantal keer proberen hebben we:

\begin{matrix}
5^{37}&=&2^3&\cdot&13^1&\cdot&19^1\\
5^{37}&=&(-1)^1&\cdot&3^3&&&\\ 
5^{1998}&=&2^1&\cdot&7^1&\cdot&19^1\\
5^{21}&=&2^9&&&&\\ 
5^{108}&=&(-1)^1&\cdot&7^1&\cdot&13^2
\end{matrix}

Elk priemgetral komt minstens twee keer voor. De eerste vergelijking schrijven we nu als volgt op:

^5log 5^{37} = ^5log (2^3 \cdot 13^1 \cdot 19^1) = ^5log 2^3 + ^5log13 + ^5log19
37 = 3 \cdot ^5log2 + 1 \cdot ^5log13 + 1 \cdot ^5log19

Voor 108 geldt:
108 = 1 \cdot ^5log(-1) + 1 \cdot ^5log7 + 2 \cdot ^5log13

Omdat 5^{2002} = 1, en dus (5^{1001})^2 = 1, moet gelden dat 5^{1001} = -1 (mod 2002). Elk element van \langle5\rangle is immers uniek.
Daardoor weten we dat
108 = 1001 + 1 \cdot ^5log7 + 2 \cdot ^5log13

Stap 2:
We willen nu de waarde van de gebruikte logaritmen weten. Die vinden we door gebruik te maken van de volgende matrix.

\begin{matrix}
^5\log 2&^5\log 7&^5\log 13&^5\log 19&\\
3&0&1&1&37\\
1&1&0&1&1998\\
0&1&2&0&1109\\
9&0&0&0&21
\end{matrix}

Deel in de onderste rij door 9.
21 representeert een getal (21 + k \cdot 2002)
Voor k = 6 levert dat 12033 en dat is deelbaar door 9.
Nu weten we dat
^5log2 = 1337 (mod 2002).

\begin{matrix}
^5\log 2&^5\log 7&^5\log 13&^5\log 19&\\
0&0&1&1&37 - 3 \cdot 1337 = 30\\
0&1&0&1&1998 -1337 = 661\\
0&1&2&0&1109\\
1&0&0&0&1337
\end{matrix}

\begin{matrix}
^5\log 7&^5\log 13&^5\log 19&\\
0&1&1&30\\
1&0&1&661\\
1&2&0&1109
\end{matrix}

\begin{matrix}
^5\log 7&^5\log 13&^5\log 19&\\
0&1&1&30\\
1&-1&0&661 - 30 = 631\\
1&2&0&1109
\end{matrix}

\begin{matrix}
^5\log 7&^5\log 13&^5\log 19&\\
0&1&1&30\\
1&-1&0&631\\
3&0&0&1109 + 2\cdot 631 = 369
\end{matrix}

Nu volgt ^5log7 = 123 ( mod 2002)
^5log13 = 123 - 631 + 1494 ( mod 2002)
^5log19 = 30 - 1494 = 538 ( mod 2002)

Stap 3:
We zoeken nu naar een geschikte ontbinding van getallen van de volgende vorm: 543 \cdot 5^{i}
Na een paar keer proberen hebben we

543 \cdot 5^{433} = (-1) \cdot 2^2 \cdot 19^2

Daaruit volgt de vergelijking

^5log 543 \cdot 5^{433} = ^5log(-1) + 2 \cdot ^5log2 + 2 \cdot ^5log19
^5log 543 +433 = 1001 + 2 \cdot 1337 + 2 \cdot 538

Hieruit volgt ^5log 543 = 314,
de oplossing: n = 314

In binaire lichamen[bewerken]

We gaan uit van \mathbb{F}_{2^7} mod f(x) = x^7 + x + 1
De elementen van \mathbb{F}_{2^7} zijn alle veeltermen in \mathbb{F}_2 van ten hoogste de graad 6. De operatie is vermenigvuldigen mod f(x). De orde van \mathbb{F}_{2^7} is 128 - 1 = 127
De veelterm g = x is voortbrenger van \mathbb{F}_{2^7}
We kiezen nu h = x^4 + x^3 +x^2 + x + 1 uit die groep en willen n oplossen uit
x^4 + x^3 +x^2 + x + 1 =x^n mod f(x)

Stap 1:
Kies als factorbasis de verzameling van alle niet te ontbinden veeltermen in \mathbb{F}_2[x] van ten hoogste de graad 3.
B = { x, x + 1, x^2 + x + 1, x^3 + x + 1, x^3 + x^2 + 1}
Zoek nu veeltermen die te ontbinden zijn met veeltermen uit B. Hieronder staan er vijf waarbij dat lukt.

\begin{matrix}
x^{18}&\bmod f(x)&=&x^6 + x^4&=&x^4(x + 1)^2\\
x^{105}&\bmod f(x)&=&x^6 + x^5 + x^4 + x&=&x(x + 1)^2(x^3 + x^2 + 1)\\
x^{72}&\bmod f(x)&=&x^6 + x^5 + x^3 + x^2&=&x^2(x + 1)^2(x^2 + x + 1)\\
x^{45}&\bmod f(x)&=&x^5 + x^2 + x + 1&=&(x + 1)^2(x^3 + x + 1)\\
x^{121}&\bmod f(x)&=&x^6 + x^5 + x^4 + x^3 + x^2 + x + 1&=&(x^3 + x + 1)(x^3 + x^2 + 1)
\end{matrix}

Stap 2:
We willen nu de waarde van de gebruikte logaritmen weten.
stel

\begin{matrix}
p_1&=&^x\log x\\
p_2&=&^x\log(x + 1)\\
p_3&=&^x\log(x^2 + x + 1)\\
p_4&=&^x\log(x^3 + x + 1)\\
p_5&=&^x\log(x^3 + x^2 + 1)
\end{matrix}

Dit geeft

\begin{matrix}
18&=&4p_1 + 2p_2&\bmod 127\\
105&=&p_1 + 2p_2 + p_5&\bmod 127\\
72&=&2p_1 + 2p_2 + p_3&\bmod 127\\
45&=&2p_2 + p_4&\bmod 127\\
121&=&p_4 + p_5&\bmod 127
\end{matrix}

Omdat p_1 = 1 is dit te vereenvoudigen tot

\begin{matrix}
14&=&2p_2&\bmod 127\\
104&=&2p_2 + p_5&\bmod 127\\
70&=&2p_2 + p_3&\bmod 127\\
45&=&2p_2 + p_4&\bmod 127\\
121&=&p_4 + p_5&\bmod 127
\end{matrix}

Hieruit volgt p_2 = 7, dus p_5 = 90, p_3 = 56 en p_4 = 31

Stap 3:
We zoeken nu naar een geschikte ontbinding van veeltermen van de vorm h \cdot x^{i} mod f(x) die te ontbinden is met veeltermen uit B.
Dat lukt voor i = 66
(x^4 + x^3 + x^2 + x + 1) x^{66} mod f(x) = x^5 + x^3 + x = x(x^2 + x + 1)^2
Dus ^xlog(x^4 + x^3 + x^2 + x + 1) = ( p_1 + 2 \cdot p_3 -66) ( mod 127) = 47
de oplossing: n = 47

Zie ook[bewerken]

Referenties[bewerken]