素模平方根的Tonelli-Shanks算法实现
我实现了维基百科上定义的Tonelli-Shanks算法。我把它放在这里是为了复习和分享。
def legendre_symbol(a, p):
"""
Legendre symbol
Define if a is a quadratic residue modulo odd prime
http://en.wikipedia.org/wiki/Legendre_symbol
"""
ls = pow(a, (p - 1)/2, p)
if ls == p - 1:
return -1
return ls素模平方根 (我刚刚将解决方案变量R重命名为x，n重命名为a)：
def prime_mod_sqrt(a, p):
"""
Square root modulo prime number
Solve the equation
x^2 = a mod p
and return list of x solution
http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
"""
a %= p
# Simple case
if a == 0:
return [0]
if p == 2:
return [a]
# Check solution existence on odd prime
if legendre_symbol(a, p) != 1:
return []
# Simple case
if p % 4 == 3:
x = pow(a, (p + 1)/4, p)
return [x, p-x]
# Factor p-1 on the form q * 2^s (with Q odd)
q, s = p - 1, 0
while q % 2 == 0:
s += 1
q //= 2
# Select a z which is a quadratic non resudue modulo p
z = 1
while legendre_symbol(z, p) != -1:
z += 1
c = pow(z, q, p)
# Search for a solution
x = pow(a, (q + 1)/2, p)
t = pow(a, q, p)
m = s
while t != 1:
# Find the lowest i such that t^(2^i) = 1
i, e = 0, 2
for i in xrange(1, m):
if pow(t, e, p) == 1:
break
e *= 2
# Update next value to iterate
b = pow(c, 2**(m - i - 1), p)
x = (x * b) % p
t = (t * b * b) % p
c = (b * b) % p
m = i
return [x, p-x]如果您有任何优化或发现任何错误，请报告。
回答 3
Code Review用户
发布于 2014-03-03 01:17:50
做得好!在这段代码中，我没有什么可评论的。您已经编写了简单明了的代码，其唯一的复杂性直接来自于它正在执行的操作的复杂性。最好在代码本身中包含一些外部评论(比如R和n的名称)，以便更容易地跟踪维基百科上的文档。您可能也希望包括其中的一些文档。
作为参考，本评论的其余部分假设代码的功能正确；我今晚没有讨论我的数学问题。
似乎有一种冗余代码，除非m可以是1，从而导致一个空范围，因此无法重新分配i。否则，您可以跳过分配给i的以下内容：
i, e = 0, 2
for i in xrange(1, m):
...您可能会考虑一些小的强度减缩优化，但在Python中，它们的影响很可能被最小化--在深入优化路径之前，绝对是概要文件。例如，在下面的while循环中：
# Factor p-1 on the form q * 2^s (with Q odd)
q, s = p - 1, 0
while q % 2 == 0:
s += 1
q //= 2q上的这两种操作都可以减少。模数可以重写为二进制和q & 1，除法为二进制移位q >>= 1。或者，您可以使用divmod同时执行这两个操作。
同样，对于非负指数，2**(m - i - 1)与1 << (m - i - 1)是完全相同的.
Code Review用户
发布于 2016-09-20 15:54:20
要增强python 3的可移植性，可以在代码中到处使用//而不是/。您已经在像q //= 2这样的行中这样做了，但是在像x = pow(a, (p + 1)/4, p)这样的行中没有这样做。事实上，考虑包括from __future__ import division。
而且，在我所做的一些基准测试中，计算2**x比计算等效的1<<x要慢得多。因此，这是另一个小的优化，可以进行。
最后，对于python 3的可移植性，您可以将xrange的一次性使用替换为range。在这种情况下，我不认为python 2会有任何显著的性能损失。
Code Review用户
发布于 2018-09-27 06:35:44
我知道，现在有点晚了，但我有一些小建议：
- 在
legendre_symbol实现中，计算pow(a, (p - 1)/2, p)。您不需要从1中减去p，因为p很奇怪。此外，您还可以用p/2替换p >> 1，这样速度更快。 - 在简单的案例处理中，您可以将
p % 4替换为p & 3，pow(a, (p + 1)/4, p)也可以替换为pow(a, (p + 1) >> 2, p)。既然您已经检查过p & 3 == 3，一个等价的解决方案将是pow(a, (p >> 2) + 1, p)，我会选择这个方案。当正确的移位有效地减少了p的字节大小时，它可以产生不同的效果。 - 还有一种简单的情况可以检查：
p % 8 == 5或等效的p & 7 == 5。在这种情况下，您可以计算pow(a, (p >> 3) + 1, p)，检查它是否是一个解(它是一个解当且仅当a是四次余模p)，否则用pow(2, p >> 2, p)乘以它就可以得到一个有效的解(当然，在乘法后不要忘记计算% p)。 - 在你的
while-loop中，你需要找到一个合适的i。让我们看看如果i是4的话: pow(t，2，p) pow(t，4，p) #计算pow(t，2，p) pow(t，8，p) #计算pow(t，4，p)，它计算pow(t，2，p) pow(t，16，p)，计算pow(t，4，p)，计算pow(t，4，p)，计算pow(t，2，p)，看到冗余了吗？随着i的增加，乘法次数呈二次增长，而在(1，m)：t2i = t2i * t2i %p(1，m)范围内，它只会线性增长: i，t2i，= 0，t。 - 最后一个优化非常简单:我只需将t= (t *b* b) %p= (b * b) %p替换为c= (b * b) %p= (t * c) %p，这样可以节省一次乘法。
https://codereview.stackexchange.com/questions/43210
复制相似问题
腾讯云开发者
