RSA大整数开平方后平方结果与原数不符问题求助

我正在开展RSA相关工作，需要分解一个308位的超大整数N（N为两个质数p和q的乘积），尝试通过整数平方根相关方法分解p和q。

我的N值：

20254083928313901046078299908836135556415829454193867459405514358320313885965296062600909040071281223146837763723113350068483510086809787065437344845044248205975654791622356467691953988928774211033663314876745580293750456921795999384782277674803240671474563131823612882192899349325870727676292313218782419561

对N取平方根后得到：

4500453746936401829977490795263804776361530154559603855210407318900755249674017838942492466443373259250056015327414929135301293865748694108450793034088448

但将该平方根平方后，结果与原N不一致：

20254083928313899038600080147064458144896171593553283932412228091641105206147936089547530020826698707611325067918592113664216112071557998883417732874096894330570809935758528713783460134686650819864956839352000831110894044634083630533310853814832242550420262010702947392454262240042077177552422858018628042752

我无法确定问题原因，寻求帮助。

我的代码：

import math

modulo = 20254083928313901046078299908836135556415829454193867459405514358320313885965296062600909040071281223146837763723113350068483510086809787065437344845044248205975654791622356467691953988928774211033663314876745580293750456921795999384782277674803240671474563131823612882192899349325870727676292313218782419561

sqrt = math.sqrt(modulo)
print('%i' %(sqrt))
print('%i' %(sqrt*sqrt))

问题原因 #

math.sqrt返回的是浮点数，而浮点数的精度有限（Python中浮点数通常是64位双精度，最多只能精确表示53位整数）。你的N是308位超大整数，远超过浮点数的精确表示范围，所以用math.sqrt计算时会丢失大量精度，转换为整数后已经不是真实的平方根，平方后自然和原N不符。

解决方法 #

使用Python专门用于整数平方根计算的方法：

1. Python 3.8+：使用math.isqrt()，它会返回不大于输入整数的最大整数平方根，全程保持整数精度。
2. 手动实现牛顿迭代法求整数平方根，避免浮点数精度损失。

修正后的代码示例：

import math

modulo = 20254083928313901046078299908836135556415829454193867459405514358320313885965296062600909040071281223146837763723113350068483510086809787065437344845044248205975654791622356467691953988928774211033663314876745580293750456921795999384782277674803240671474563131823612882192899349325870727676292313218782419561

# 使用math.isqrt获取精确的整数平方根
sqrt = math.isqrt(modulo)
print(sqrt)
print(sqrt * sqrt)

# 验证差值，因为N=p*q，p和q接近的话，sqrt(N)和p/q的差很小
print(modulo - sqrt * sqrt)

运行这段代码后，你会得到精确的整数平方根，平方后的结果和原N的差值会很小（符合你参考的分解方法中p和q接近的场景），可以继续后续的分解步骤。

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