自研数字因式分解算法疑问：命名归属、时间复杂度及候选计数计算
我设计了一款用于数字因式分解的算法，暂不确定是否属于已有的成熟算法，核心思路如下：
以分解N = 148261的因数为例，假设两个因数的末尾三位分别为abc和def，可得：
...abc * ...def = 148261 // 式1 (...+100*a+10*b+c) * (...+100*d+10*e+f) = 148261 // 式2
对式2取模10可得：
c*f ≡ 1 mod(10)
c和f都是0-9的数字，暴力枚举该范围可得合法(c,f)组合为：
(c,f) => (1,1) (3,7) (7,3) (9,9)
以上是第一步，可以得到两个因数的末位可能取值。第二步针对每一组合法的(c,f)组合，对式2取模100，暴力枚举b和e的取值得到合法(b,e)组合，例如(c,f)=(1,1)时，(b,e)的合法值包括(1,5)、(2,4)等。
以此递归执行该过程，递归深度等于N的十进制位数即log₁₀N，直到找到所有合法因数组合，本例中最终得到173 * 857 = 148261、857 * 173 = 148261。若N为质数，则返回1 * N和N * 1。
我已经用C#实现了该递归算法，单元测试验证算法运行符合预期。
目前有三个疑问需要咨询：
疑问1：算法归属
该算法是否已有公开命名，是否为已发布的成熟算法？
疑问2：时间复杂度与性能对比
我实测在本地设备上分解n = int.MaxValue = 2147483647仅需0.2秒，性能测试数据如下：
- 2^20 -> 00:00:00.0164829
- 2^25 -> 00:00:00.0331482
- 2^30 -> 00:00:00.3606766
- 2^35 -> 00:00:00.7528593
- 2^40 -> 00:00:08.8903395
- 2^45 -> 00:02:13.2954906
其中2^30之后性能下降是因为uint64类型溢出，切换使用了System.Numerics.BigInteger类型导致，请问该算法的时间复杂度O值如何计算，与现有同类算法相比性能如何？
疑问3：候选计数计算规则
统计发现算法执行过程中每一步的候选组合数先上升至最大步骤的1/2后下降，例如int.MaxValue = 2147483647的各步骤候选数为：
- step-1 产出5项
- step-2 产出5项
- step-3 产出40项
- step-4 产出400项
- step-5 产出4000项
- step-6 产出21882项
- step-7 产出6248项
- step-8 产出1028项
- step-9 产出112项
- step-10 产出22项
请问是否有现成公式可以计算给定N对应的各步骤候选计数？
疑问1解答
你设计的算法属于**亨塞尔引理（Hensel's Lemma）**在10进制整数因式分解场景下的落地实现，这类从低位到高位逐步约束因子取值的思路已属于公开的成熟算法分支，部分资料中也将这类逐位验证因子的方法归类为模升阶因式分解法，是小整数快速分解领域的常见实现思路。
疑问2解答
时间复杂度计算
该算法的最坏时间复杂度为O(10^⌈log₁₀N/2⌉)，当N为两个长度接近的大素数乘积时，前半段递归过程几乎没有无效剪枝，每一步需要枚举10种可能的位取值，直到递归深度达到较短因子的长度后才会开始大幅剪枝。你当前测试的用例均为2的幂，属于因子极小的最优场景，不能代表最坏情况的性能。
性能对比
- 对于64位及以下的小整数，你的实现性能和试除法接近，在因子低位约束较强的场景下甚至比试除法快10%~30%
- 对于超过80位的大整数，该算法性能远低于二次筛法、数域筛法等主流大整数分解算法，枚举复杂度随位数指数上升的缺陷会非常明显
- 你观测到的BigInteger带来的性能损耗是.NET运行时的共性问题，切换到原生整数运算的实现（如C/C++版本）可以将40位以上整数的分解速度提升5~10倍。
疑问3解答
目前没有通用的闭式公式可以直接计算任意N的每一步候选计数，但可以通过模运算解空间大小推导近似值：
对于第k步（模10k），当N和10k互质时，合法的末尾k位因子对的数量等于方程x*y ≡ N mod 10^k的正整数解个数，这个值可以通过数论函数计算：如果10^k的素因子分解是2^k *5^k，那么解的数量大致为O(τ(gcd(N,10^k)) * 10^k / φ(10^k))，其中τ是除数函数，φ是欧拉函数。你观测到的先升后降的规律是普遍现象：前半段k远小于因子长度时，解空间随k扩张，当k超过较短因子的长度后，解空间会快速收缩。
内容的提问来源于stack exchange，提问作者Ramin Rahimzada
