from random import randint, choice
import math


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

# Define a Peer object
class Peer(object):

	# Construct a new peer
	# @param crush bool Whether peer has crush or not
	# @param peer  Peer Reference to other peer
	def __init__(self, crush=False, peer=None):
		self.__crush = crush
		self.__N = 0
		self.__peer = peer
		self.__r = 0

	def setPeer(self, peer):
		self.__peer = peer

	def setN(self, N):
		self.__N = N

	def __residue(self, a):
		i = choice(range(1000, 100000))
		return a + self.__N * i

	def __step1(self):
		# Generate an RSA 
		a = 13
		b = 11
		self.__rsa = self.__residue(a*b)
		# Reveals N to untrusted peer
		self.__peer.setN(self.__N)

	def __step2(self):
		y = 15 if self.__crush else 0
		y = self.__residue(y)
		x = self.__residue(0)

		self.__peer.step4(x**3, y**3)

	def step4(self, x3, y3):
		i = choice(range(1, 100))
		r = self.__residue(i)
		self.__r = r
		
		a3r3 = y3*r**3 if self.__crush else x3*r**3
		self.__peer.step5(a3r3)


	def step5(self, a3r3):
		print a3r3
		ar = cuberoot(a3r3, self.__N)
		print ar
		self.__peer.step6(ar)

	def step6(self, ar):
		print ar / self.__r



	def run(self):
		self.__step1()
		self.__step2()

alice = Peer(crush=True)
bob = Peer(crush=True)
bob.setPeer(alice)
alice.setPeer(bob)
alice.setN(13)

alice.run()