Naslov
Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti
(Applications of continued fractions in factorization and primality testing)

Autori
Kralj, Kristina

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Prirodoslovno-matematički fakultet - Matematički odsjek

Mjesto
Zagreb

Datum
28.11

Godina
2017

Stranica
35

Mentor
Dujella, Andrej

Ključne riječi
verižni razlomci, prosti brojevi
(continued fractions, primes)

Sažetak
Metoda faktorizacije velikih prirodnih brojeva pomoću verižnih razlomaka (CFRAC) razvijena je 1975. godine te je u to vrijeme bila najbrža metoda faktorizacije. Osnovna ideja ove metode je traženje netrivijalnog rješenja kongruencije x^2 = y^2 (mod N). Pomoću njega može se dobiti neki faktor broja N. U ovom radu opisan je način na koji se različiti koeficijenti iz razvoja broja sqrt(N) u verižni razlomak koriste za dobivanje kongruencije navedenog oblika. Opisana je i primjena verižnih razlomaka pri testiranju prostosti. U tom slučaju bio je korišten razvoj broja sqrt(3) u verižni razlomak te konvergente tog verižnog razlomka. Proučavanjem nazivnika konvergenti uočene su neke pravilnosti pomoću kojih je dobiven test prostosti. Osim općenitog slučaja, opisan je i način testiranja prostosti Mersennovih brojeva. U radu su navedeni i različiti primjeri faktorizacije i testiranja prostosti pomoću verižnih razlomaka.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA