立方根模p - 我该怎么办呢？ [英] Cube root modulo P -- how do I do this?
问题描述
我试图来计算Python中的许多百位数模P的立方根，而失败了。
I am trying to calculate the cube root of a many-hundred digit number modulo P in Python, and failing miserably.
我发现code为托内利 - 尚克斯算法据称是简单的平方根修改为立方根，但这种逃避我。我已经冲刷网络和数学库和几本书都无济于事。 code将是美好的，所以将算法用简单的英语解释说。
I found code for the Tonelli-Shanks algorithm which supposedly is simple to modify from square roots to cube roots, but this eludes me. I've scoured the web and math libraries and a few books to no avail. Code would be wonderful, so would an algorithm explained in plain English.
下面是Python（2.6？）code查找平方根：
Here is the Python (2.6?) code for finding square roots:
def modular_sqrt(a, p):
""" Find a quadratic residue (mod p) of 'a'. p
must be an odd prime.
Solve the congruence of the form:
x^2 = a (mod p)
And returns x. Note that p - x is also a root.
0 is returned is no square root exists for
these a and p.
The Tonelli-Shanks algorithm is used (except
for some simple cases in which the solution
is known from an identity). This algorithm
runs in polynomial time (unless the
generalized Riemann hypothesis is false).
"""
# Simple cases
#
if legendre_symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return n
elif p % 4 == 3:
return pow(a, (p + 1) / 4, p)
# Partition p-1 to s * 2^e for an odd s (i.e.
# reduce all the powers of 2 from p-1)
#
s = p - 1
e = 0
while s % 2 == 0:
s /= 2
e += 1
# Find some 'n' with a legendre symbol n|p = -1.
# Shouldn't take long.
#
n = 2
while legendre_symbol(n, p) != -1:
n += 1
# Here be dragons!
# Read the paper "Square roots from 1; 24, 51,
# 10 to Dan Shanks" by Ezra Brown for more
# information
#
# x is a guess of the square root that gets better
# with each iteration.
# b is the "fudge factor" - by how much we're off
# with the guess. The invariant x^2 = ab (mod p)
# is maintained throughout the loop.
# g is used for successive powers of n to update
# both a and b
# r is the exponent - decreases with each update
#
x = pow(a, (s + 1) / 2, p)
b = pow(a, s, p)
g = pow(n, s, p)
r = e
while True:
t = b
m = 0
for m in xrange(r):
if t == 1:
break
t = pow(t, 2, p)
if m == 0:
return x
gs = pow(g, 2 ** (r - m - 1), p)
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
def legendre_symbol(a, p):
""" Compute the Legendre symbol a|p using
Euler's criterion. p is a prime, a is
relatively prime to p (if p divides
a, then a|p = 0)
Returns 1 if a has a square root modulo
p, -1 otherwise.
"""
ls = pow(a, (p - 1) / 2, p)
return -1 if ls == p - 1 else ls
来源：<一href="http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python/comment-page-1/#comment-624163"相对=nofollow>模块化计算平方根在Python
推荐答案
请注意后来补充：在托内利 - 香克利的算法，并在此假设 P 是素数。如果我们能够在一般的快速计算模块化平方根复合模量，我们可以迅速因子的数字。我的假设，你知道是p是素道歉。
Note added later: In the Tonelli-Shanks algorithm and here it is assumed that p is prime. If we could compute modular square roots to composite moduli quickly in general we could factor numbers quickly. I apologize for assuming that you knew that p was prime.
See here or here. Note that the numbers modulo p are the finite field with p elements.
编辑：请参见这个也（这是爷爷这些论文。）
See this also (this is the grandfather of those papers.)
最简单的部分是当p = 2的mod 3，那么一切都是一个立方体的athe立方根就是 A **（（2 * P-1）/ 3）％，P
The easy part is when p = 2 mod 3, then everything is a cube and athe cube root of a is just a**((2*p-1)/3) %p
补充：这里是code做的一切，但质数1mod9.我会尽力去本周末。如果没有人得到它首先
Added: Here is code to do all but the primes 1 mod 9. I'll try to get to it this weekend. If no one else gets to it first
#assumes p prime returns cube root of a mod p
def cuberoot(a, p):
if p == 2:
return a
if p == 3:
return a
if (p%3) == 2:
return pow(a,(2*p - 1)/3, p)
if (p%9) == 4:
root = pow(a,(2*p + 1)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
if (p%9) == 7:
root = pow(a,(p + 2)/9, p)
if pow(root,3,p) == a%p:
return root
else:
return None
else:
print "Not implemented yet. See the second paper"
这篇关于立方根模p - 我该怎么办呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
