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 $m\in\mathbb N$ and distinct primes $p$ and $q$ with $p$ not dividing $m$, the existence of a solution to the Fermat equation $X^p+Y^p=Z^p$ in positive characteristic $q$ such that $X+Y\neq 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\bigl( \phi(m)[m^3 + m^2(\log N)^2] M(\lfloor \log_2 N\rfloor +1) \bigr)$, where $\phi$ is the Euler's function and $M$ is the multiplication time function for $\mathbb 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 $\log N$.
From: Adrian Vasiu [view email]
[v1]
Fri, 5 Jun 2026 14:37:39 UTC (40 KB)
[v2]
Thu, 25 Jun 2026 15:10:29 UTC (42 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。