WisFaq!

Vereenvoudigen van een logaritme modulo c

Hoi

Weten jullie soms ook hoe je de ^aÖb (mod c) en ^a log(b) (mod c) kunt vereenvoudigen?
Met vereenvoudigen bedoel ik dat je a^b (mod c) kunt veranderen in (a (mod c))^p · (a (mod c))^q (mod c) º (a (mod c))^q (mod c)
met p = b (mod f(c)) en q = b - p.

Aris

Aris van Dijk
4-2-2004

Antwoord

De vraag heeft alleen zin als de a-de-machtswortel uit c geheel is, zeg k (mod c), en de logarithme met grondtal a geheel, zeg n (mod c). Men kan het ook zo opvatten dat die wortel en die logarithme niet meteen geheel hoeven te zijn, maar pas als je modulo c gaat rekenen.
Er bestaan geen algemene formules, maar je kunt de volgende berekeningsprocedures volgen:
Stel a=l*F(c)+m met 0mF(c). Dan k^a=k^m (mod c). Zoek dus k met k^m=b (mod c). Zo'n k bestaat echter niet altijd.
Stel n=r*F(c)+s met 0sF(c). Dan aⁿ=a^s (mod c). Zoek dus s met a^s=b (mod c). Dan voldoet n=r*F(c)+s voor elke gehele r.
De oplossingen s en n bestaan ook niet altijd.

hr
5-2-2004