De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Hoe bereken je ge mod m?

Hoe bereken je:

6843 (mod 341) d.m.v. binair rekenen?

thomas
Leerling bovenbouw havo-vwo - dinsdag 4 januari 2005

Antwoord

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

De berekening verloopt nu als volgt:

681 mod 314=68
682 mod 341=68·68 mod 341=4624 mod 341=191
684 mod 341=191·191 mod 341=36481 mod 341=335
688 mod 341=335·335 mod 341=112225 mod 341=36
6816 mod 341=36·36 mod 341=1296 mod 341=273
6832 mod 341=273·273 mod 341=74529 mod 341=191.

Dus 6843 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)

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 4 januari 2005



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3