On the Factorizations of Integers via Division Algorithms for Polynomials

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 m∈N and distinct primes p and q with p not dividing m, the existence of a solution to the Fermat equation Xp+Yp=Zp in positive characteristic q such that X+Y≠Z and X,Y and Z are m-th roots of unity implies the factorization of a composite natural number N that is a multiple of pq at the cost of Oϕ(m)[m3+m2(logN)2]M(⌊log2N⌋+1), where ϕ is the Euler’s function and M is the multiplication time function for Z. 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 logN.