Colella, Davide (2024) Integer Factorization via Order Finding. Bachelor's Thesis, Mathematics.
|
Text
bMATH_2024_ColellaD.pdf Download (1MB) | Preview |
|
![[img]](https://fse.studenttheses.ub.rug.nl/style/images/fileicons/text.png) |
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 |