Egyptiläinen murtoluku

Egyptiläiset esittivät murtolukuja Horuksen silmä-hieroglyfin osilla.

Egyptiläinen murtoluku on rationaaliluku, joka esitetään ykkösen tasaosien eli resiprookkimurtolukujen summana. Egyptiläiset murtoluvut ovat yli 4 000 vuotta vanhaa matematiikkaa Niilin alueelta.

Vuonna 1858 skotlantilainen nuorukainen Henry Rhind osti Egyptistä torikauppiaalta thebalaisesta haudasta löydetyn papyruskäärön, joka myöhemmin Rhindin kuoleman jälkeen ajautui British Museumiin Lontooseen. Käärössä esitellään egyptiläisten käyttämä murtolukujärjestelmä, joka on vertailun kannalta ja monissa käytännön tilanteissa yksinkertaisempi kuin nykymatematiikan käyttämä rationaalinen muoto. Muinaiset egyptiläiset tunsivat murtoluvuista vain ykkösen tasaosat, kuten luvut 1/2, 1/3 ja 1/4. He ilmaisivat kaikki murtoluvut tällaisten egyptiläisten murtojen summina, vieläpä niin, että yhteenlaskettavat olivat aina keskenään erilaisia. Esimerkiksi:

$\frac{3}{4}$	$=$	$\frac{1}{2} + \frac{1}{4}$ ja
$\frac{3}{7}$	$=$	$\frac{1}{3} + \frac{1}{11} + \frac{1}{231}$.

Apuna käytettiin erilaisia taulukoita.

Eräs tapa muuntaa tavallinen ykköstä pienempi (positiivinen) murto edellä mainitunlaiseksi summaksi on ahne algoritmi: Murrosta erotetaan ensimmäiseksi yhteenlaskettavaksi mahdollisimman suuri murto 1/m, jäännöksestä toinen mahdollisimman suuri murto 1/n ja niin edelleen niin kauan, ettei mitään jää. Menettely todella päättyy aina jossain vaiheessa, minkä todisti vuonna 1202 italialainen Fibonacci. Seuraavana esimerkki ahneen algoritmin tuottamasta esityksestä:

$\frac{99}{100} = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{73} + \frac{1}{9 \, 018} + \frac{1}{230 \, 409 \, 900}$.

Kuten esityksestä ilmenee, ei ahne algoritmi ole aina kaikkein lyhin tapa esittää rationaaliluku resiprookkimuodossa.

Egyptiläisten murtolukuesitysten käyttö kokonaislukujen tekijöihinjaossa

Egyptiläiset murtolukuesitykset voivat nykyajan matematiikan harrastajan tai tutkijan mielestä tuntua lähinnä historialliselta kuriositeetilta. Niillä voisi kuitenkin olla nykyajan tietoliikenteen tietoturvan kannalta erittäin ajankohtainen merkitys.

Monet julkisen avaimen infrastruktuurin (PKI) salakirjoitusmenetelmät nojautuvat siihen, että suurten kokonaislukujen kertominen keskenään on tietokoneilla erittäin helposti suoritettavissa, kun taas päinvastainen operaatio, suurten kokonaislukujen tekijöihinjako on erittäin vaikeaa. Tunnetuin esimerkki tällaisesta algoritmista on RSA.

RSA-menetelmän julkisen avaimen moduuliosa $n$ on kahden suuren, esimerkiksi 100-200 -numeroisen alkuluvun tulo, $n=pq$. Jos alkuluvut $p$ ja $q$ tunnetaan, salakirjoitusjärjestelmän murtaminen on helposti suoritettavissa.

Oletetaan, että tunnetaan jollakin positiivisella kokonaisluvulla $k \geq 2$, missä luku $k$ ei ole jaollinen luvuilla $p$ tai $q$, luvun ${k\over n}$ egyptiläinen murtolukuesitys.

Olkoon

${k\over n} = {k\over pq} = {1\over r_1} + {1\over r_2} + ... + {1\over r_m}$,

missä $m > 1$.

Tällöin

${pq\over k} = {1\over {1\over r_1} + {1\over r_2} + ... + {1\over r_m}}$

ts.

$pq= k {r_1r_2...r_m\over \sum_{i=1}^m\prod_{j=1,j\not=i}^m r_j}$

Siten $p$ jakaa välttämättä jonkin luvun $r_i$ ja $q$ jakaa jonkin luvun $r_j$.

Jos ko. egyptiläinen murtolukuesitys on satunnaisesti valittu, on hyvin todennäköistä, että $i\not=j$.

Tällöin luvun n alkutekijät saadaan selville laskemalla luvun $n$ suurimmat yhteiset tekijät kunkin luvuista $r_1,...,r_m$ kanssa.

Egyptiläisten murtolukujen tekijöihinjakomenetelmän etuna muihin tekijöihinjakomenetelmiin nähden on se, että

-murtolukuesitysten laskemiseen ei tarvita luvun $n$ tekijöihinjakoa

-menetelmä hyödyntää sitä, että peruslaskutoimitukset (samoin kuin modulaariaritmetiikan perusoperaatiot) ovat helposti suoritettavissa normaalipituisia RSA-avaimia huomattavastikin suuremmilla (esimerkiksi kymmeniätuhansia numeroita sisältävillä) kokonaisluvuilla.

Osoitamme vielä, että luvulla $2/n$, missä $n=pq$ on kahden parittoman alkuluvun tulo, on aina olemassa egyptiläinen murtolukuesitys, joka 'erottelee' tekijät $p$ ja $q$. Helposti todetaan nimittäin, että

${2\over n} = {2\over pq} = {1\over ({p+q\over 2})p}+{1\over ({p+q\over 2})q}$,

missä

$\left (n,({p+q\over 2})p\right )=p$

ja

$\left (n,({p+q\over 2})q\right )=q$.

Aiheesta muualla

• Kevin Gong. Egyptian Fractions (PDF-tiedosto) Useita algoritmeja egyptiläisten murtolukujen määrittämiseksi, jotkut niistä ovat tehokkaita ja jotkut hankalampia
• Dr Ron Knott. Egyptian Fractions Yleistä tietoa egyptiläisistä murtoluvuista