On the Factorizations of Integers via Division Algorithms for Polynomials
Open Access
- 3 July 2026
- journal article
- research article
- Published by MDPI AG in Mathematics
- Vol. 14 (13) , 2378
Abstract
We introduce and study several conditions related to the factorization problem of composite numbers. For this purpose, we employ cyclotomic polynomials, Sylvester resultants, and the Fermat equation. For instance, we show that for and distinct primes p and q with p not dividing m, the existence of a solution to the Fermat equation in positive characteristic q such that and and Z are m-th roots of unity implies the factorization of a composite natural number N that is a multiple of at the cost of , where is the Euler’s function and M is the multiplication time function for . We also show that such solutions do not exist for many semiprime integers N, provided that m is required to have a fixed polynomial upper bound in .
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Understanding Cryptography2024
- A log-log speedup for exponent one-fifth deterministic integer factorisationMathematics of Computation, 2021
- An exponent one-fifth algorithm for deterministic integer factorisationMathematics of Computation, 2021
- A time-space tradeoff for Lehman’s deterministic integer factorization methodMathematics of Computation, 2021
- Modern Computer Algebra2013
- On Vanishing Sums of Roots of UnityJournal of Algebra, 2000
- Vanishing Sums ofmth Roots of Unity in Finite FieldsFinite Fields and Their Applications, 1996
- Modifications to the Number Field SieveJournal of Cryptology, 1993
- A Course in Computational Algebraic Number Theory1993
- Factoring integers with the number field sieve1993