Egyptiläinen murtoluku

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 tunnetaan nimellä Rhindin papyrus ja joka 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:
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ä:
formula_1.
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.
Tässä esitetään kuitenkin eräs nykyajan tietoliikenteen tietoturvaan liittyvä sovellus. 
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 formula_2 on kahden suuren, esimerkiksi 100–200 -numeroisen alkuluvun tulo, formula_3. Jos alkuluvut formula_4 ja formula_5 tunnetaan, salakirjoitusjärjestelmän murtaminen on helposti suoritettavissa.
Oletetaan, että tunnetaan jollakin positiivisella kokonaisluvulla formula_6, missä luku formula_7 ei ole jaollinen 
luvuilla formula_4 tai formula_5, luvun formula_10 egyptiläinen murtolukuesitys.
Olkoon 
formula_11,
missä formula_12.
Tällöin
formula_13
Toisin kirjoittaen
formula_14
Siten formula_4 jakaa välttämättä jonkin luvun formula_16 ja formula_5 jakaa jonkin luvun formula_18.
Jos ko. egyptiläinen murtolukuesitys on satunnaisesti valittu, on hyvin todennäköistä, että formula_19.
Tällöin luvun n alkutekijät saadaan selville laskemalla luvun formula_2 suurimmat yhteiset tekijät kunkin luvuista formula_21 kanssa.
Egyptiläisten murtolukujen tekijöihinjakomenetelmän etuna muihin tekijöihinjakomenetelmiin nähden on se, että
Osoitamme vielä, että luvulla formula_23, missä formula_3 on kahden parittoman alkuluvun tulo, on aina olemassa egyptiläinen murtolukuesitys, joka 'erottelee' tekijät formula_4 ja formula_5. Todetaan nimittäin, että
formula_27,
missä
formula_28
ja
formula_29.