Cubo raíz módulo P – ¿Cómo hago esto?

Estoy tratando de calcular la raíz cúbica de un número P de cientos de dígitos en Python, y estoy fallando miserablemente.

Encontré el código para el algoritmo de Tonelli-Shanks, que supuestamente es fácil de modificar de raíz cuadrada a raíz cúbica, pero esto se me escapa. He rastreado las bibliotecas web y matemáticas y algunos libros en vano. El código sería maravilloso, igual que un algoritmo explicado en un lenguaje sencillo.

Aquí está el código de Python (2.6?) Para encontrar raíces cuadradas:

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 (ie # 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 

Fuente: Computación de raíces cuadradas modulares en Python.

Nota agregada más adelante: en el algoritmo de Tonelli-Shanks y aquí se supone que p es primo. Si pudiéramos calcular las raíces cuadradas modulares a módulos compuestos rápidamente, en general, podríamos factorizar los números rápidamente. Me disculpo por suponer que sabía que p era primordial.

Ver aquí o aquí . Tenga en cuenta que los números módulo p son el campo finito con p elementos.

Edit: Ver esto también (este es el abuelo de esos papeles.)

La parte fácil es cuando p = 2 mod 3, entonces todo es un cubo y la raíz cúbica de a es solo a**((2*p-1)/3) %p

Agregado: Aquí está el código para hacer todo excepto los números primos 1 mod 9. Intentaré llegar este fin de semana. Si nadie más lo hace primero

 #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"