WisFaq!

Modulus grote integers

Ik wil uitrekenen de modulus van een groot getal:
N=182316110684665468232161 mod 97.
Wat is de snelste oplossing? Ik las ergens:
Neem de eerste 9 cijfers van N mod 97 = r₁
Zet deze r₁ voor de 2e reeks 9 cijfers van N en mod 97 = r₂
Zet deze r₂ voor de laatste 5 cijfers van N en mod 97 = antw.
Maar op welke wiskundige theorie is dit gebaseerd waardoor dit werkt?

Herman
18-12-2017

Antwoord

Dat is gewoon modulair rekenen: je schrijft je getal van 24 cijfers als
$$
a\cdot10^{15} + b\cdot10^6+c
$$Hier is $a$ het getal gevormd door de eerste negen cijfers, $b$ door de volgende negen cijfers, en $c$ de laatste zes cijfers.
Als $a\equiv r_1 \pmod{97}$ dan geldt ook $a\cdot10^{15}\equiv r_1\cdot10^{15}$ dus als je de eerste zes cijfers vervangt door de twee cijfers van $r_1$ zijn het oude en nieuwe getal equivalent modulo $97$.
De tweede stap kijkt naar
$$
r_1\cdot10^9+b
$$als je daarbij $r_2$ vindt geldt
$$
(r_1\cdot 10^9 +b)\cdot10^6 \equiv r_2\cdot10^6 \pmod{97}
$$en dus geeft vervanging van de cijfers van $r_1$ en $b$ door $r_2$ weer een equivalent getal.

Het idee is wellicht dat modulo rekenen met getallen van negen cijfers wat minder werk is dat in een keer het hele getal te nemen. Je kunt ook kleinere groepjes cijfers nemen (zes cijfers bijvoorbeeld) dat kost meer stappen maar misschien toch wat minder rekenwerk.

kphart
18-12-2017