gpt4 book ai didi

python - Python 3 中的模幂实现

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:08:09 25 4
gpt4 key购买 nike

基本上这是一道作业题。我应该在 Python3 中实现这两个伪代码算法。我做错了什么,我不知道是什么(看起来这应该很简单,所以我不确定我在什么地方/哪里搞砸了。这可能是我的算法或我缺乏使用 Python 的经验。我'我不确定是哪个。)。

请告诉我我做错了什么,不要发布任何代码。如果我得到答案的代码,我会被指责为剽窃(我非常不希望这样)。

第一种算法(基数扩展):


procedure base expansion(n, b: positive integers with b > 1)
q := n
k := 0
while q ≠ 0
a<sub>k</sub> := q mod b
q := q div b
k := k + 1
return (a<sub>k-1</sub>, ... , a<sub>1</sub>, a<sub>0</sub>) {(a<sub>k-1</sub> ... a<sub>1</sub> a<sub>0</sub>)<sub>b</sub> is the base b expansion of n}

第二种算法(模展开):


procedure modular exponentiation(b: integer, n = (a<sub>k-1</sub>a<sub>k-2</sub>...a<sub>1</sub>a<sub>0</sub>)<sub>2</sub>, m: positive integers)
x := 1
power := b mod m
for i := 0 to k - 1
if a<sub>i</sub> = 1 then x := (x * power) mod m
power := (power * power) mod m
return x {x equals b<sup>n</sup> mod m}

无论如何看起来很简单,这是我在 Python3 中实现的(我请求所有 Python 程序员的原谅,这对我来说是一种非常新的语言)

def baseExp(n, b):
q = n
a = []
while (q != 0):
a.append(q % b)
q = q // b
pass
return a

def modularExp(b, n, m):
a = baseExp(n, b)
x = 1
power = b % m
for i in range(0, len(a)):
if (a[i] == 1):
x = (x * power) % m
pass
power = (power * power) % m
pass
return x

这看起来应该可行,但是当我尝试解决 7644 mod 645 时,我得到答案 79,但正确答案应该是 436。

如果有人能指出我的错误而不实际给我任何代码,我将非常感激。

最佳答案

您的方法只有在 b 等于 2 时才有效,这与平方取幂相同,但在 b > 2 的情况下会失败。方法如下:

您的字符串 n 可以包含 [0,b-1] 范围内的数字,因为它是以 b 为基数的数字 n 的表示形式。在您的代码中,您只检查数字 1,在 b = 7 的情况下,可以有 [0,6] 范围内的任何数字。您必须按如下方式修改算法:

// take appropriate remainders where required
// Correction 1 :
In the for loop,
Check if a[i] = 1, then x = x * power
else if a[i] = 2, then x = x * power^2
else if a[i] = 3, then x = x * power^3
.
.
.
.
till a[i] = b-1, then x = x * power^(b-1)
// Correction 2 :
After checking a[i]
power = power^b and not power = power^2 which is only good for b = 2

你现在应该得到正确的答案。

关于python - Python 3 中的模幂实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18804958/

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