Javascript must be enabled for the correct page display

Integer Factorization via Order Finding

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


Download (1MB) | Preview
[img] Text
Restricted to Registered users only

Download (130kB)


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

Actions (login required)

View Item View Item