Solves equations of the form z^(1/q) = x in the cyclic integer group Zp. e.g. 7^(1/3) =x in Z11 group

solveModIntegers.py

from decimal import Decimal

'''
  Hunts for the solution to things like
  7^(1/3) = x  in the group modulo 11
  to solve things like this, you can absorb the modulus into the equation
  e.g. (7+11n)^(1/3) = x

  This script will then rip through that and find the first integer solution to that.

  You could do binary search (but then you stand over-stepping the periodicity), intesting question for another time...
'''

exp = Decimal(1)/3 
def calculate(n):
  # Can't use '^' here as int and Decimal are incompatible
  return (7+11*n)**exp 

n=1
eightPlaces = Decimal(10) ** -8

while True :
  test = calculate(n)
  if (test.quantize(eightPlaces) - test.to_integral()) == 0.00000000 :
    break
  print n, calculate(n)
  n+=1

# If it doesn't complete in a few seconds than its likely there is no integer solution.

print "\nfound: "
print n, calculate(n)