当前位置:  开发笔记 > 编程语言 > 正文

模块化pow()中的负功率

如何解决《模块化pow()中的负功率》经验,为你挑选了1个好方法。

我们如何pow在模块化环境中使用负指数?

pow(x,y,[z])如果存在z,则x和y必须为整数类型,并且y必须为非负数。

>>> pow(11444, -357)
0.0
>>> pow(11444, -357) % 48731
0.0
>>> pow(11444, -357, 48731)
Traceback (most recent call last):
  File "", line 1, in 
TypeError: pow() 2nd argument cannot be negative when 3rd argument specified

在我的用例中,我想使用Schnorr方案对消息进行加密:

y = (g ** -w) mod p

pow此处不接受负数作为第二个参数。例如,从

g = 11444
p = 48731
w = 357

y应该是7355



1> DSM..:

pow不会自动为您计算模块化的乘法逆。相反,我们可以自己计算(例如通过扩展的Eulidean算法),然后重写pow(a,-b,c)pow((a^-1) mod c, b, c)。从这个问题窃取MMI代码:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

我们得到

>>> g = 11444
>>> p = 48731
>>> w = 357
>>> modinv(g, p)
29420
>>> pow(modinv(g, p), w, p)
7355


在“ p”为质数的情况下(如此处所示),“ modinv(a,p)”的更简单实现是“ pow(a,p-2,p)”。
推荐阅读
夏晶阳--艺术
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有