Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

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)

hk
dinsdag 4 januari 2005

©2001-2024 WisFaq