WisFaq!

Hoe bereken je g^e mod m?

Hoe bereken je:

68⁴³ (mod 341) d.m.v. binair rekenen?

thomas
4-1-2005

Antwoord

De truc voor snelle exacte machtsverheffing modulo m is de volgende:
Bekijk eens je voorbeeld:
43=1+2+8+32, dus 68⁴³=68×68²×68⁸×68³².
Hoe kom je nu aan die 1+2+8+32?
Wel de binaire schrijfwijze van 43=101011!

De berekening verloopt nu als volgt:

68¹ mod 314=68
68² mod 341=68·68 mod 341=4624 mod 341=191
68⁴ mod 341=191·191 mod 341=36481 mod 341=335
68⁸ mod 341=335·335 mod 341=112225 mod 341=36
68¹⁶ mod 341=36·36 mod 341=1296 mod 341=273
68³² mod 341=273·273 mod 341=74529 mod 341=191.

Dus 68⁴³ mod 341=68·191·36·191 mod 341=316.

Het definitieve algoritme ziet er dan zo uit:
(de binaire schrijfwijze van de exponent wordt al doende bepaald!)

//Bereken g^e mod m:

resultaat:=1
herhaal
  als (e is oneven) dan resultaat:=resultaat·g mod m
  e:=e div 2
  //div is de gehele deling!
  g:=g·g mod m
totdat e=1
resultaat:=resultaat·g mod m

//einde algoritme

Deze berekening heet in de praktijk meestal modpow(g,e,m) of powmod(g,e,m) of modular_exponentiation(g,e,m)

hk
4-1-2005