Zigterman, Sven (2026) Factoring in Number Rings. Bachelor's Thesis, Mathematics.
|
Text
BScZigtermanfinal.pdf Download (345kB) | Preview |
Abstract
The factorisation problem for integers is assumed to be hard to solve, and many cryptosystems rely on this. Closely related to factorisation is the order finding problem, for which Stange introduced a subexponential algorithm based on the Index Calculus algorithm. In this paper we generalise this by showing that Stange's algorithm can also be used to compute the order of elements for, in theory, any unique factorisation domain with finite quotient groups, and in practice for maximal orders of number fields with class number 1. We show that a multiple of the order can always be obtained given a sufficient factor base. Furthermore, under an adaptation of Stange's heuristic hypothesis, the order can be computed with high probability. Using the order one can obtain a factorisation, for this Shor's reduction is discussed and adapted. Implementations of the resulting algorithms are provided for maximal orders in number fields. Since Stange's algorithm naturally provides a multiple of the order, we also consider Ekerå's variation on an algorithm due to Miller, which can recover a factorisation given a multiple of the order. Additionally, these methods extend to ideal factorisations in Dedekind domains.
| 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: | 16 Jul 2026 12:00 |
| Last Modified: | 16 Jul 2026 12:00 |
| URI: | https://fse.studenttheses.ub.rug.nl/id/eprint/37428 |
Actions (login required)
 |
View Item |