大家好，我最近在研究一个基于三元分拆的整数因式分解算法，遇到了关于初始分拆选择的困惑，想和各位大佬探讨下。

先给大家铺垫下背景：
之前我在相关问题的研究中，猜想把目标整数N拆成3个整数的分拆是这类算法的合适起点——毕竟二元分拆没法保证生效，比如当N是斐波那契数时，二元分拆会导致递归无限进行，但三元分拆可以借助斐波那契恒等式拆解出至少3个非零项，举个例子：21拆成13+5+3就能在第一次迭代就得到因子3，而拆成13+8的话就会陷入无限递归。

算法核心规则 #

我们定义三元组$(a_k, b_k, c_k)$的递归关系如下：
$$
\begin{align}
a_k&=\min(3a_{k-1},b_{k-1}-a_{k-1},c_{k-1}-a_{k-1}) \
c_k&=\max⁡(3a_{k-1},b_{k-1}-a_{k-1},c_{k-1}-a_{k-1} ) \
b_k&=N-a_k-c_k
\end{align}
$$
需要注意的是，这个三元组始终满足 $\forall k \ge 0, a_k < b_k < c_k$。

初始时我们会选一个满足$a_0 < b_0 < c_0$的随机分拆作为$(a_0,b_0,c_0)$，每次迭代都会检查集合${\gcd(a_k,N),\gcd(b_k,N),\gcd(c_k,N)}$中是否存在大于1的元素（也就是N的非平凡因子），如果有就终止算法，否则继续执行递归步骤。

我已经用这个算法做了实证测试：选取25个大于1000的质数的乘积（包括质数平方）作为测试集，算法确实能有效找到N的非平凡因子。关于算法为什么能生效的证明或反例讨论，我已经在其他地方发起了，这里就不展开了。

我的核心疑问 #

现在我想请教的是：在不知道N的任何因子d，且N本身难以直接分解的前提下，选择什么样的初始三元分拆，能让算法终止所需的迭代次数最少？

（补充一句：如果我们已经知道N的某个因子d，那选$(d, 2d, N-3d)$肯定是最优的，但现在d是未知的，所以需要针对这种“盲选”场景找最优初始分拆）

已做的测试数据 #

我测试了两种初始分拆方案，对应的迭代次数分布有对应的散点图：

• 第一种初始分拆：
  $$(a_0, b_0, c_0) = \big(\lfloor \sqrt{N}/2 \rfloor, \lfloor \sqrt{N} \rfloor, N - \lfloor \sqrt{N}/2 \rfloor - \lfloor \sqrt{N} \rfloor\big)$$
• 第二种初始分拆：
  $$(a_0, b_0, c_0) = (1, 2, N - 1 - 2)$$

这里给大家展示一个具体例子：当N=1402627（即1249×1123）时，用第二种初始分拆的迭代过程部分输出如下（完整迭代了66次才找到因子）：

At iteration 1: (1, 2, 1402624)
At iteration 2: (1, 3, 1402623)
At iteration 3: (2, 3, 1402622)
At iteration 4: (1, 6, 1402620)
At iteration 5: (3, 5, 1402619)
At iteration 6: (2, 9, 1402616)
At iteration 7: (6, 7, 1402614)
At iteration 8: (1, 18, 1402608)
At iteration 9: (3, 17, 1402607)
At iteration 10: (9, 14, 1402604)
At iteration 11: (5, 27, 1402595)
At iteration 12: (15, 22, 1402590)
At iteration 13: (7, 45, 1402575)
At iteration 14: (21, 38, 1402568)
At iteration 15: (17, 63, 1402547)
At iteration 16: (46, 51, 1402530)
At iteration 17: (5, 138, 1402484)
At iteration 18: (15, 133, 1402479)
At iteration 19: (45, 118, 1402464)
At iteration 20: (73, 135, 1402419)
At iteration 21: (62, 219, 1402346)
At iteration 22: (157, 186, 1402284)
At iteration 23: (29, 471, 1402127)
At iteration 24: (87, 442, 1402098)
At iteration 25: (261, 355, 1402011)
At iteration 26: (94, 783, 1401750)
At iteration 27: (282, 689, 1401656)
At iteration 28: (407, 846, 1401374)
At iteration 29: (439, 1221, 1400967)
At iteration 30: (782, 1317, 1400528)
At iteration 31: (535, 2346, 1399746)
At iteration 32: (1605, 1811, 1399211)
At iteration 33: (206, 4815, 1397606)
At iteration 34: (618, 4609, 1397400)
At iteration 35: (1854, 3991, 1396782)
At iteration 36: (2137, 5562, 1394928)
At iteration 37: (3425, 6411, 1392791)
At iteration 38: (2986, 10275, 1389366)
At iteration 39: (7289, 8958, 1386380)
At iteration 40: (1669, 21867, 1379091)
At iteration 41: (5007, 20198, 1377422)
At iteration 42: (15021, 15191, 1372415)
At iteration 43: (170, 45063, 1357394)
At iteration 44: (510, 44893, 1357224)
At iteration 45: (1530, 44383, 1356714)
At iteration 46: (4590, 42853, 1355184)
At iteration 47: (13770, 38263, 1350594)
At iteration 48: (24493, 41310, 1336824)
At iteration 49: (16817, 73479, 1312331)
At iteration 50: (50451, 56662, 1295514)
At iteration 51: (6211, 151353, 1245063)
At iteration 52: (18633, 145142, 1238852)
At iteration 53: (55899, 126509, 1220219)
At iteration 54: (70610, 167697, 1164320)
At iteration 55: (97087, 211830, 1093710)
At iteration 56: (114743, 291261, 996623)
At iteration 57: (176518, 344229, 881880)
At iteration 58: (167711, 529554, 705362)
At iteration 59: (361843, 503133, 537651)
At iteration 60: (141290, 175808, 1085529)
At iteration 61: (34518, 423870, 944239)
At iteration 62: (103554, 389352, 909721)
At iteration 63: (285798, 310662, 806167)
At iteration 64: (24864, 520369, 857394)
At iteration 65: (74592, 495505, 832530)
At iteration 66: (223776, 420913, 757938)
Found factors in 1249x1123 in 66 iterations.
Found factors 1249x1123 = 1402627

想问问各位，有没有什么思路、启发或者已知的结论，能帮助我们找到这种未知因子场景下的最优初始三元分拆？

备注：内容来源于stack exchange，提问作者vvg