Primjena verižnih razlomaka u faktorizaciji i testiranju prostosti

master's thesis

• Author: Kristina Kralj
• Mentor: Andrej Dujella (mentor)
• Committee member: Andrej Dujella (predsjednik povjerenstva)
• Committee member: Filip Najman (član povjerenstva)
• Committee member: Sanja Varošanec (član povjerenstva)
• Committee member: Pavle Pandžić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-11-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: faktorizacija velikih prirodnih brojeva; verižni razlomci; testiranje prostosti; Mersennovi brojevi
• Keywords (english): factoring large natural numbers; continued fraction method; primality testing; Mersenne numbers
• Language: croatian
• URN:NBN: urn:nbn:hr:217:380656
• Study programme: Title: Mathematics and Computer Science Education; specializations in: Mathematics and Computer Science Education; Course: Mathematics and Computer Science Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike i informatike (magistar/magistra edukacije matematike i informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-05-25 12:23:11