整数因式分解

Question

如果我有一组形式为${ {kp+r}：K\geq0 0}$，p是$\in Z^+$中素数k的一个素数或p的乘积，且r是固定的，那么对其中任何一个数，如果p是很大的> 1000位，在计算上是可行的。

就上下文而言，我在考虑整数分解问题的这个变体是否可以接受。

干杯。

Answer 1

该问题的解是推广的欧几里得算法，这是一个多项式算法。