Teh­tä­vä:
Bi­nää­ri­po­tens­si

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Tur­val­li­nen asioin­ti verk­ko­pan­kis­sa edel­lyt­tää tie­don sa­laus­ta. Yk­si las­ku­toi­mi­tus, jo­ta ny­ky­ai­kai­sis­sa sa­laus­me­ne­tel­mis­sä tar­vi­taan, on aⁿ mod M, mis­sä kaik­ki kol­me lu­kua ovat iso­ja (esi­mer­kik­si 300-nu­me­roi­sia). Sen suo­rit­ta­mi­nen las­ke­mal­la n − 1 eli noin 10³⁰⁰ ker­to­las­kua ja mo­du­lo-ope­raa­tio­ta vei­si ai­kaa mel­ko mon­ta maail­man­kaik­keu­den ikää. Täs­sä teh­tä­väs­sä tu­tus­tu­taan kei­noon suo­rit­taa las­ku tar­peek­si no­peas­ti. Yk­sin­ker­tai­suu­den vuok­si mo­du­lon ot­ta­mi­nen jä­te­tään näyt­tä­mät­tä, mut­ta se on help­po li­sä­tä al­go­rit­min jo­ka kier­rok­sel­le.

Ker­ra­taan aluk­si pa­ri asiaa.

Bi­nää­ri­po­tens­si näyt­tää täl­tä. Har­maal­la kir­joi­tet­tua ri­viä 4 ei oi­keas­ti tar­vi­ta, mut­ta sen li­sää­mi­nen hel­pot­taa al­go­rit­mis­ta päät­te­le­mis­tä. Sen li­sää­mi­nen ei muu­ta si­tä ar­voa, mi­kä ri­vil­lä 6 si­joi­te­taan n:ään, kos­ka …ri­vin 3 eh­don vuok­si se suo­ri­te­taan vain kun n on pa­ri­ton, ja sil­loin n div 2 = Tä­män näim­me edel­lä. (n − 1) / 2 = Kun ja­ko me­nee ta­san, / tuot­taa sa­man tu­lok­sen kuin div.(n − 1) div 2. (Mik­si yh­tä­suu­ruu­det pä­te­vät?)  Mi­tään muu­ta­kaan vai­ku­tus­ta sen pois jät­tä­mi­sel­lä ei ole jat­koon, kos­ka ri­vien 4 ja 6 vä­lis­sä n:n ar­voa ei käy­te­tä mi­hin­kään.

1  x := 1
2  while n > 0 do
3      if n mod 2 = 1 then
4          n := n − 1
5          x := x · a
6      n := n div 2
7      a := a · a

Al­go­rit­mi on ko­pioi­tu oi­keal­le alas, jot­ta se oli­si kä­sil­lä myös kun yl­lä ole­va ko­pio on ka­don­nut ruu­dun ylä­reu­nan ylä­puo­lel­le.

Mer­ki­tään muut­tu­jien n ja a ar­vo­ja al­go­rit­min alus­sa sym­bo­leil­la N ja A. Al­go­rit­min teh­tä­vä­nä on siis las­kea A^N, mis­sä N on luon­nol­li­nen lu­ku. To­dis­tam­me, et­tä al­go­rit­mi las­kee oi­kean lop­pu­tu­lok­sen ja sel­vi­täm­me, kuin­ka no­peas­ti se toi­mii.

Käy­täm­me sil­mu­koi­den to­dis­ta­mi­ses­sa hy­vin yleis­tä päät­te­ly­ta­paa, jos­sa on vii­si vai­het­ta:

1. Va­li­taan jo­kin väi­te, jol­la päät­te­ly saa­daan on­nis­tu­maan. Si­tä kut­su­taan in­va­rian­tik­si. Bi­nää­ri­po­tens­sin in­va­riant­ti on yh­tä­lö A^N = xaⁿ.
2. Osoi­te­taan, et­tä in­va­riant­ti pä­tee sil­mu­kan alus­sa eli kun ri­vil­le 2 tul­laan en­sim­mäi­sen ker­ran.
3. Osoi­te­taan, et­tä sil­mu­kan var­ta­lon suo­ri­tus ei voi saa­da in­va­riant­tia pois voi­mas­ta (pait­si ken­ties ti­la­päi­ses­ti kes­ken var­ta­lon suo­ri­tuk­sen). Siis osoi­te­taan, et­tä jos A^N = xaⁿ pä­tee ri­vin 3 alus­sa ja sil­mu­kan eh­to n > 0 pä­tee, niin A^N = x­aⁿ pä­tee ri­vin 7 lo­pus­sa. Täs­tä, edel­li­ses­tä ja sii­tä, et­tä ri­vil­lä 2 ei muu­te­ta min­kään muut­tu­jan ar­voa seu­raa, et­tä A^N = x­aⁿ on voi­mas­sa ai­na ri­vin 2 alus­sa.
4. Osoi­te­taan, et­tä sil­mu­kan suo­ri­tus lop­puu jos­kus.
5. Osoi­te­taan, et­tä jos in­va­riant­ti pä­tee ja sil­mu­kan eh­to ei pä­de, niin sil­mu­kan lop­pu­tu­lok­sel­ta ha­lut­tu asia pä­tee, eli et­tä al­go­rit­mi on las­ke­nut oi­kean lop­pu­tu­lok­sen.

Kos­ka po­tens­si­las­ku ei ole mää­ri­tel­ty esi­mer­kik­si sil­loin kun kan­ta­lu­ku on nol­la ja eks­po­nent­ti ne­ga­tii­vi­nen, mei­dän on pi­det­tä­vä tark­kaan huol­ta, et­tä väit­teis­säm­me eks­po­nen­tit ovat ai­na ei-ne­ga­tii­vi­sia.

Koh­dan 3 hoi­ta­mi­sek­si ole­tam­me, et­tä in­va­riant­ti ja sil­mu­kan eh­to pä­te­vät ri­vin 3 alus­sa, ja to­dis­tam­me, et­tä in­va­riant­ti pä­tee ri­vin 7 lo­pus­sa. Tä­män teh­däk­sem­me alam­me käy­dä sil­muk­kaa lä­pi.

Vas­ta­tes­sa­si edel­li­seen koh­taan huo­ma­sit eh­kä, et­tä tä­män muo­don voi pää­tel­lä suo­raan, mut­ta voi ol­la vai­keaa miet­tiä pi­tää­kö si­joi­tuk­sen n := n − 1 vai­ku­tus ot­taa huo­mioon li­sää­mäl­lä vai vä­hen­tä­mäl­lä in­va­rian­tis­sa n:ään yk­kö­nen. Jos si­joi­tus­lau­seen oi­keal­la puo­lel­la on jo­tain mo­ni­mut­kai­sem­paa, vai­keus kas­vaa. Sik­si opet­te­lem­me ki­kan. En­nen si­joi­tus­lau­set­ta pä­te­vä kaa­va kan­nat­taa muut­taa muo­toon, jos­sa si­joi­tus­lau­seen oi­kea puo­li esiin­tyy sel­lai­se­naan. Tyy­pil­li­ses­ti se esiin­tyy yh­den ker­ran, mut­ta muut­kin mää­rät ovat mah­dol­li­sia. Si­joi­tuk­sen koh­tee­na ole­va muut­tu­ja ei saa esiin­tyä muual­la kuin näis­sä oi­keis­sa puo­lis­sa. Si­joi­tus­lau­seen jäl­kei­nen ti­lan­ne saa­daan kor­vaa­mal­la ne muut­tu­jal­la, jo­hon si­joi­te­taan.

Si­joi­tus­lau­seen n := 2n + 1 ja kaa­van 4n = k ta­pauk­ses­sa se tar­koit­taa, et­tä en­sin kaa­va muu­te­taan muo­toon 2(2n + 1) − 2 = k. Tä­mä on loo­gi­ses­ti yh­tä­pi­tä­vä al­ku­pe­räi­sen kaa­van kans­sa, kos­ka 2(2n + 1) − 2 = 4n. Sit­ten 2n + 1 kor­va­taan n:llä, jol­loin saa­daan 2n − 2 = k. Tu­lok­sek­si saa­tiin, et­tä jos en­nen si­joi­tus­ta n := 2n + 1 pä­ti 4n = k, niin si­joi­tuk­sen jäl­keen pä­tee 2n − 2 = k.

Olem­me to­dis­ta­neet, et­tä jos in­va­riant­ti on voi­mas­sa sil­mu­kan var­ta­lon alus­sa, se on voi­mas­sa myös sil­mu­kan var­ta­lon lo­pus­sa. Siis koh­ta 3 on val­mis.

Kos­ka kum­pi­kin kah­teen edel­li­seen laa­tik­koon kir­joit­ta­mis­ta­si lau­sek­keis­ta on yh­tä­suu­ri lau­sek­keen xaⁿ kans­sa, ne ovat yh­tä­suu­ret myös kes­ke­nään, jo­ten al­go­rit­min tuot­ta­ma vas­taus on oi­kein. Koh­ta 5 ja si­tä myö­ten ko­ko to­dis­tus on val­mis.

Tä­mä al­go­rit­mi mo­ti­voi­tiin lu­pauk­sel­la no­peu­des­ta, jo­ten nyt on ai­ka kat­soa kuin­ka no­pea se on. Al­go­rit­min käyt­tä­mis­sä pe­rus­ope­raa­tiois­sa ei ole mi­tään ker­to­las­kua mo­ni­mut­kai­sem­paa. Kol­me­sa­taa­nu­me­rois­ten lu­ku­jen ker­to­las­ku ei ole yh­tä pie­ni hom­ma kuin kym­men­nu­me­rois­ten, jo­ten tar­kas­sa las­kel­mas­sa kiin­ni­tet­täi­siin huo­mio­ta pe­rus­ope­raa­tioi­den hin­taan. Nyt em­me kui­ten­kaan ole niin tark­ko­ja, vaan kat­som­me ai­noas­taan sil­mu­kan kier­ros­ten mää­rää.

Kol­me­sa­taa­nu­me­roi­sil­la lu­vuil­la tu­lee siis hiu­kan al­le tu­hat kier­ros­ta. Tie­to­ko­neel­le se on koh­tuul­li­nen työ­mää­rä sii­tä­kin huo­li­mat­ta, et­tä pe­rus­las­ku­toi­mi­tuk­set teh­dään 300-nu­me­roi­sil­la lu­vuil­la.