论文标题
使用乘法关系模型$ n $分解：一种受索引微积分启发的亚指数算法
Factoring using multiplicative relations modulo $n$: a subexponential algorithm inspired by the index calculus
论文作者
论文摘要
我们证明了经典索引演算算法的修改可用于因素。更普遍地，我们将保理问题减少到在任何因素基本模型中找到过度确定的乘法关系系统，其中$ n $是寻求分解的整数。该算法具有子指定运行时$ \ Exp（o（\ sqrt {\ sqrt {\ log n \ log \ log n}）））$（或$ \ exp（o（（（（\ log n）^{1/3} {1/3}（\ log log \ log \ log \ \ log \ \ \ log \ \ f \ \ f \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ h）经典索引演算算法的线性代数阶段。该算法肯定比最著名的保理算法要慢，但也许以其简单性和与索引演算的相似性而值得注意。
We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $n$, where $n$ is the integer whose factorization is sought. The algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or $\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$ with the addition of a number field sieve), but requires a rational linear algebra phase, which is more intensive than the linear algebra phase of the classical index calculus algorithm. The algorithm is certainly slower than the best known factoring algorithms, but is perhaps somewhat notable for its simplicity and its similarity to the index calculus.
