Esimerkki: Nopeus
Verkkopankkiin tunnistautumisessa lasketaan potenssilaskuja isoilla luvuilla.
- esim. 300-numeroisilla:
194 625 ⋯ 385
- laskut tehdään modulo jokin iso luku
Jos oletamme utopistisen nopean tietokoneen …
- 10 000 ⋯ (43 nollaa) ⋯ 000
kertolaskua sekunnissa
- vertaa Planckin aika
… joka laskee tutulla tavalla …
- luku · luku · … (10300
kertolaskua) … · luku
- ojelmana an
x := 1
for i := 1 to n do
x :=
x · a
… niin aikaa kuluu suunnilleen
100 000 ⋯ (239 nollaa) ⋯ 000
aikayksikköä.
Mikä aikayksikkö?
Verkkopankkiin tunnistautuminen ei kuitenkaan yleensä vie näin kauaa.
⇒ Tunnistautumisohjelma laskee jotenkin fiksummin.
x := 1
while n > 0 do
if n on pariton
then
x :=
x · a
n :=
n − 1
a :=
a · a
n :=
n / 2
Fiksummin laskemisella voi siis olla valtava merkitys.
[ ylös ] •
[ seuraava ]