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 de discrete logaritme, h = gn, op te lossen, waar g en h elementen van groep, G, zijn. Een discrete logaritme is gedefinieerd op een eindige groep G. Voor g als voortbrenger van G en h G wordt naar de oplossing van gevraagd.

Het algoritme[bewerken]

Het indexcalculusalgoritme kan onder andere toegepast worden op eindige lichamen.

De methode voor priemlichamen en binaire lichamen kan als volgt beschreven worden:

In priemlichamen[bewerken]

g is een subgroep van , h g
Voor welke n geldt (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 g die de eigenschap hebben dat ze te ontbinden zijn in priemfactoren uit de verzameling B.
Die groepselementen schrijven we als

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 zodat h te ontbinden is met priemfactoren uit B.
h (g) = (-1) ...
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 worden weergegeven als veeltermen in [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 [x], die niet te ontbinden is.
Kies voor factorbasis B elementen uit de verzameling van alle niet te ontbinden veeltermen in [x] met als graad niet meer dan een tevoren vastgestelde bovengrens.

Stap 1:
Zoek veeltermen mod f(x), met g als voortbrenger van 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 zodat h 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 = 5 met p=2003.
We kiezen nu h = 543 uit die groep en willen n oplossen uit h = 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 5 en ontbinden die in priemgetallen. Alleen de getallen die m.b.v.B te ontbinden zijn kunnen we gebruiken.

964 =
zullen we niet gebruiken.

Na een aantal keer proberen hebben we:

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

log = log ( ) = log + log13 + log19
37 = 3 log2 + 1 log13 + 1 log19

Voor 108 geldt:
108 = 1 log(-1) + 1 log7 + 2 log13

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

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

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

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

Stap 3:
We zoeken nu naar een geschikte ontbinding van getallen van de volgende vorm: 543
Na een paar keer proberen hebben we

543 = (-1)

Daaruit volgt de vergelijking

log 543 = log(-1) + 2 log2 + 2 log19
log 543 +433 = 1001 + 2 1337 + 2 538

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

In binaire lichamen[bewerken]

We gaan uit van mod f(x) = + x + 1
De elementen van zijn alle veeltermen in van ten hoogste de graad 6. De operatie is vermenigvuldigen mod f(x). De orde van is 128 - 1 = 127
De veelterm g = x is voortbrenger van
We kiezen nu h = + + + x + 1 uit die groep en willen n oplossen uit
+ + + x + 1 = mod f(x)

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

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

Dit geeft

Omdat = 1 is dit te vereenvoudigen tot

Hieruit volgt = 7, dus = 90, = 56 en = 31

Stap 3:
We zoeken nu naar een geschikte ontbinding van veeltermen van de vorm h mod f(x) die te ontbinden is met veeltermen uit B.
Dat lukt voor i = 66
( + + + x + 1) mod f(x) = + + x = x( + x + 1)
Dus log( + + + x + 1) = ( + 2 -66) ( mod 127) = 47
de oplossing: n = 47

Zie ook[bewerken]

Referenties[bewerken]