prikaz prve stranice dokumenta Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti
  Preuzmi
PDF 244.99 KB
diplomski rad
Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. urn:nbn:hr:217:380656
Kralj, Kristina
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Kralj, K. (2017). Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:380656

Kralj, Kristina. "Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:380656

Kralj, Kristina. "Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:380656

Kralj, K. (2017). 'Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 04.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:380656

Kralj K. Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2017 [pristupljeno 04.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:380656

K. Kralj, "Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:380656

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:380656
Podaci o radu
NaslovPrimjena verižnih razlomaka u faktorizaciji i testiranju prostosti
AutorKristina Kralj
MentorAndrej Dujella (mentor)
Član povjerenstvaAndrej Dujella (predsjednik povjerenstva)
Član povjerenstvaFilip Najman (član povjerenstva)
Član povjerenstvaSanja Varošanec (član povjerenstva)
Član povjerenstvaPavle Pandžić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2017-11-28, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
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\equiv y^2 \pmod{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.
Sažetak (engleski)
Continued fraction method for factoring large natural numbers was developed in 1975 and it was the fastest factorization method at the time. The basic idea behind this method is finding non-trivial solutions to congruence \(x^2\equiv y^2 \pmod{N}\). After they have been found, there is a chance that a factor of \(N\) will be discovered. To produce a congruence of that form, coefficients from a continued fraction expansion of \(\sqrt{N}\) are used. The way of calculating them is described in this paper. Another application of continued fractions is in primality testing. In this paper, there is a description of using a continued fraction expansion of \(\sqrt{3}\) and the convergents of that fraction. By observing denominators of convergents, certain regularities were found and they were used to describe a primality test. Apart from a general test, a test for Mersenne numbers was also described. In this paper there are various examples of factorization and primality testing with continued fractions.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:380656
Studijski programNaziv: Matematika i informatika; smjerovi: nastavnički
Smjer: nastavnički
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra edukacije matematike i informatike (mag. educ. math. et inf.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-05-25 12:23:11