On the factorizations of integers via division algorithms for polynomials

Authors:
  • GDGuram Donadze
    Guram Donadze
  • AVAdrian Vasiu
    Adrian Vasiu

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. We show that the existence of a specific solution to the Fermat type equation in positive characteristic $p$ implies polynomial-time factorization of a composite natural number that is a multiple of $p$. We also show that such solutions do not exist for many semi-prime integers.
All Related Versions