RSA合数中两素数长度与平方根的关系及因式分解循环边界咨询

关于平方根与最小素数的关系 #

是的，RSA合数N=p*q（p、q为不同的大素数，且p≤q）的平方根始终大于最小素数p。
推导逻辑很直接：假设p>√N，那么q≥p>√N，两者相乘p*q>√N*√N=N，这与N=p*q的定义矛盾。因此必然有p<√N<q（RSA要求p≠q，否则N是平方数，极易被分解，不符合安全性要求）。

基于这个结论，从√N向下遍历寻找因数，确实比从n=1向上遍历高效得多：

• 向上遍历需要检查所有6n±1形式的数直到p，而p≤√N；
• 向下遍历从√N开始，第一个能整除N的6n±1形式的数就是q，随后p=N/q可直接得到，遍历次数远少于向上遍历（尤其是当p和q长度相近时，这也是标准RSA的设计要求）。

素数长度与合数平方根的关系 #

这里的“长度”通常指二进制位数（RSA场景下常用）或十进制位数，两者的关系可以总结为：

• 若p和q都是k位二进制素数：
  则2^(k-1) ≤ p,q < 2^k，因此N=p*q的范围是2^(2k-2) ≤ N < 2^(2k)，对应的√N范围是2^(k-1) ≤ √N < 2^k，即√N的二进制位数也是k位。
• 若用十进制位数：
  k位十进制素数满足10^(k-1) ≤ p,q < 10^k，N的范围是10^(2k-2) ≤ N < 10^(2k)，√N则在10^(k-1) ≤ √N < 10^k之间，即√N的十进制位数同样是k位。

另外，标准RSA会要求p和q的长度相差极小（比如不超过几位），这时候√N的长度和p、q的长度完全一致，且数值上非常接近p和q的中间值。

内容的提问来源于stack exchange，提问作者cpa3