Colella, Davide (2024) Integer Factorization via Order Finding. Bachelor's Thesis, Mathematics.

Text
bMATH_2024_ColellaD.pdf Download (1MB)  Preview 

Text
toestemming.pdf Restricted to Registered users only Download (130kB) 
Abstract
Integer factorization is a challenge that forms the basis of many cryptography systems. These systems rely on the difficulty of factorizing large composites rapidly. The problem of factoring an integer n is closely related to the problem of computing the order of a residue in the ring of integers modulo n. In this thesis, we consider an algorithm developed by Stange that computes the order of a residue. We discuss approaches to increase the efficiency of Stange’s algorithm. To show the relation between integer factorization and order finding, we present a polynomial time algorithm due to Miller to compute the factorization of n from the order of residues modulo n. Furthermore, we explore two algorithms that use the order of a residue modulo n to compute a factorization of n, inspired by Shor and Ekerå. Similarly as before, we consider techniques to increase the efficiency of the algorithms and compare their implementations.
Item Type:  Thesis (Bachelor's Thesis) 

Supervisor name:  Muller, J.S. and Top, J. 
Degree programme:  Mathematics 
Thesis type:  Bachelor's Thesis 
Language:  English 
Date Deposited:  28 Feb 2024 08:20 
Last Modified:  28 Feb 2024 08:21 
URI:  https://fse.studenttheses.ub.rug.nl/id/eprint/31985 
Actions (login required)
View Item 