def clockadd(P1,P2):
  x1,y1 = P1
  x2,y2 = P2
  x3 = x1*y2+y1*x2
  y3 = y1*y2-x1*x2
  return x3,y3

def F(p):
  # caveat: caller must ensure that p is prime
  class F:
    def __init__(self,x):
      self.int = x % p
    def __str__(self):
      return str(self.int)
    __repr__ = __str__
    def __eq__(a,b):
      return a.int == b.int
    def __ne__(a,b):
      return a.int != b.int
    def __add__(a,b):
      return F(a.int + b.int)
    def __sub__(a,b):
      return F(a.int - b.int)
    def __mul__(a,b):
      return F(a.int * b.int)
    def __div__(a,b):
      # caveat: caller must ensure that b is nonzero
      return a*F(pow(b.int,p-2,p))
  return F

def scalarmult(n,P):
  # caveat: caller must ensure that n is nonnegative
  # caveat: n is limited by python's recursion limit
  if n == 0: return (Fp(0),Fp(1))
  if n == 1: return P
  Q = scalarmult(n//2,P)
  Q = clockadd(Q,Q)
  if n % 2: Q = clockadd(P,Q)
  return Q

# examples:
p = 1000003
Fp = F(p)
P = (Fp(1000),Fp(2))
print scalarmult(6,P)
# output: (780000, 1351)
print scalarmult(1000004,P)
# output: (0, 1)
print scalarmult(123456789123456789123456789,P)
# output: (541230, 236193)

# toy example of clock DH:
import random

alicesecret = random.randrange(2**256)
alicepublic = scalarmult(alicesecret,P)

bobsecret = random.randrange(2**256)
bobpublic = scalarmult(bobsecret,P)

aliceshared = scalarmult(alicesecret,bobpublic)
bobshared = scalarmult(bobsecret,alicepublic)
print aliceshared == bobshared