如何使用python计算巨大的数字

Question

我目前正在尝试找到x的值，

x = (math.log(X) - math.log(math.fabs(p))/math.log(g))

跟：

X = 53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224
p = 79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887
g = 73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241

不幸的是，python无法在本地处理如此大的数字。

有人知道解决这个问题的方法吗？

谢谢你的帮助。

---

编辑

因为很多你想知道我想做什么：

为了能够以安全的方式进行通信，Alice和Bob继续进行Diffie-Hellman密钥交换。为此，他们使用质数 p ：

p = 79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887

和整数 g：

g = 73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241

爱丽丝选择了秘密数字x，她计算了X=g^x mod p，并通过一个不安全的通道将X发送给Bob。鲍勃选择了秘密数字y，他计算Y=g^y mod p，并通过同一个不安全的通道将Y发送给爱丽丝。两者都可以计算值 Z = X^y = Y^x = g^xy mod p

通过监视通道，查理检索了 X 和 Y 的值：

X = 53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224
Y = 17548462742338155551984429588008385864428920973169847389730563268852776421819130212521059041463390276608317951678117988955994615505741640680466539914477079796678963391138192241654905635203691784507184457129586853997459084075350611422541722123509121359133932497700621300814065254996649070135358792927275914472632707420292830992294921992

这个练习的关键是 Z 值的 md5sum

Answer 1

您可以使用十进制库执行此操作：

from decimal import Decimal
X = 53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224
p = 79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887
g = 73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241
X=Decimal(X)
p=Decimal(p)
g=Decimal(g)
print X.ln() - abs(p).ln()/g.ln()

给

769.7443428855116199351294830

Answer 2

Sympy 可能对你来说很有趣。您可以进行符号简化并调整要使用的精度（使用 mpmath）：

import sympy as sy
sy.init_printing() # enable pretty printing in IPython
# Build the expression:
X,p,g = sy.symbols('X,p,g')
expr = (sy.log(X) - sy.log(sy.Abs(p))/sy.log(g))
# expr = expr.simplify()  # doesn't have any benefit in this case
# The values:
vX = 53710695204323513509337733909021562547350740845028323195225592059762435955297110591848019878050853425581981564064692996024279718640577281681757923541806197728862534268310235863990001242041406600195234734872865710114622767319497082014412908147635982838670976889326329911714511434374891326542317244606912177994106645736126820796903212224
vp = 79293686916250308867562846577205340336400039290615139607865873515636529820700152685808430350565795397930362488139681935988728405965018046160143856932183271822052154707966219579166490625165957544852172686883789422725879425460374250873493847078682057057098206096021890926255094441718327491846721928463078710174998090939469826268390010887
vg = 73114111352295288774462814798129374078459933691513097211327217058892903294045760490674069858786617415857709128629468431860886481058309114786300536376329001946020422132220459480052973446624920516819751293995944131953830388015948998083956038870701901293308432733590605162069671909743966331031815478333541613484527212362582446507824584241
# substitute values into variables:
expr2 = expr.subs({X:vX, p:vp,g:vg})
# evaluate to 150 digits with internal precision up to 1000 digits:
print(expr2.evalf(n=150, maxn=1000))

结果给出：

    769.744342885511619935129482917192487900343653888850271462255718268257261969359878869753342583593581927254506121925469662801405523964742213571689617098

更新：正如casevh和David所指出的，在使用sympy时，要注意不要通过使用正常的浮点数作为输入来失去准确性。为了澄清，让我们计算10**log10(10+1e-30)，这显然会导致 10+1e-30：

import sympy as sy
import numpy as np
xf = 1e-30
# numpy with floats:
np_x1 = np.log10(10+ xf)
np_yf = 10**np_x1
# sympy with no extra benefit
sy1_x1 = sy.log(10 + xf) / sy.log(10)
sy1_ye = 10**sy1_x1
sy1_yf = sy1_ye.evalf(n=33)
# sympy, done right:
x = sy.symbols('x')
sy2_x1 = sy.log(10 + x) / sy.log(10)
sy2_ye = 10**sy2_x1
sy2_yf = sy2_ye.evalf(n=33, subs={x:xf})
print("correct answer: 10.0000000000000000000000000000010")
print("        numpy:  {:.31f}".format(np_yf))
print("  naive sympy:  " + repr(sy1_yf))
print("correct sympy:  " + repr(sy2_yf))

给出的结果是：

correct answer: 10.0000000000000000000000000000010
        numpy:  10.0000000000000000000000000000000
  naive sympy:  10.0000000000000017763568394002504
correct sympy:  10.0000000000000000000000000000010

Answer 3

numpy float64 dtype 的 "machine epsilon" 大约是 2.2e-16。这意味着您应该只期望结果中的前 16 位有效数字是准确的，除非您正在执行非常棘手的事情（例如滚动自己的自定义数据类型）。

Dietrich 建议使用 sympy 并设置较高的内部精度，但 sympy 文档证实这并不能逃脱机器 epsilon 问题。

一些 Python 浮点数

仅精确到大约 15 位数字作为输入，而其他浮点数（那些分母为 2 的幂，如 .125 = 1/4）是精确的。

换句话说，要非常警惕处理和你一样大的数字的结果，因为只要你使用 64 位浮点数来做数学运算，只有前 16 位有效数字是有意义的。