gpt4 book ai didi

python - Python 和 Ruby 中的快速模计算

转载 作者:太空狗 更新时间:2023-10-29 22:23:50 27 4
gpt4 key购买 nike

我得到了以下算法,该算法在 Python 中计算 s,其中 s = g^u mod p:

def modexp ( g, u, p ):
"""computes s = (g ^ u) mod p
args are base, exponent, modulus
(see Bruce Schneier's book, _Applied Cryptography_ p. 244)"""
s = 1
while u != 0:
if u & 1:
s = (s * g)%p
u >>= 1
g = (g * g)%p;
return s

但是,当我像这样将代码转换为 Ruby 时:

def modexp ( g, u, p )
s = 1
while u != 0
if u & 1
s = (s * g)%p
end
u >>= 1
g = (g * g)%p
end
return s
end

我得到不同的输出。例如:

Python 2.7 (r27:82500, Oct  6 2010, 12:29:13) 
[GCC 4.5.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import modexp
>>> modexp.modexp(96,25,17)
6

与 Python 代码相比,哪个是正确答案

>> require './modexp.rb'
=> true
>> modexp(96,25,17)
=> 14

谁能解释一下?从我读过的内容来看,Python 和 Ruby 对于代码中使用的位移位和位运算具有相同的语法,所以我不认为是这样。任何人有任何其他想法?

最佳答案

这是因为按位-& 返回一个数字,而 0 在 Python 中是“假”但在 Ruby 中是“真”。

def modexp ( g, u, p )
s = 1
while u != 0
puts "g: #{g}, s: #{s}, u: #{u.to_s(2)}"
if u & 1
s = (s * g)%p
end
u >>= 1
g = (g * g)%p
end
return s
end

irb(main):032:0> modexp(96,25,17)
g: 96, s: 1, u: 11001
g: 2, s: 11, u: 1100
g: 4, s: 5, u: 110
g: 16, s: 3, u: 11
g: 1, s: 14, u: 1
=> 14

请注意,s 在第二行和第三行之间发生了变化,即使 u 在那一点上也是如此。记住 1100 = 12,我们看到 12 & 1 == 0。因此,在 Python 中,测试 if u & 1: 失败;但在 Ruby 中,0 被视为 true 值,if u & 1 成功

尝试用 if u & 1 != 0 替换该行。

关于python - Python 和 Ruby 中的快速模计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5486204/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com