# determine if a positive integer is prime

# list of known primes, will be extended whenever new primes are found.
KP = [2,3,5,7,11,13,17,19]

def bin(x,A):  # binary search for x in sorted array A
  ax = False
  min,max = 0,len(A)-1
  while (min<=max and ax==False):
    i = (min+max)/2
    if A[i]==x: ax=True
    else: 
       if x<A[i]: max = i-1
       else: min = i+1
  #
  return ax
# binary search

### sorted insert.
# given array A, A.insert(i,x) inserts x at position x in A, original
# A[i] moves to A[i+1].
### We can also use binary search here but the benefits will be minimal
### since inserting into the middle of an array is costly anyway.
def sinsert(x,A): # assume A sorted, insert x into A in sorted order
  i = 0
  while i<len(A) and x>A[i]: 
      i+=1
  # end while loop
  A.insert(i,x)
#sinsert

def isprime(n):   # determines if n is a prime number
  if bin(n,KP): return True   # known prime
  if n<KP[len(KP)-1]: return False  # less than largest known prime
  if n%2==0: return False  # 2 is only even prime
  ax = True
  i = 3 # test all odd numbers up to sqrt of n
  limit = int(n**0.5) + 1  # precompute for efficiency (value will not change)
  while i<=limit and ax:
    if (n%i==0): ax = False
    i += 2
  #
  if (ax==True and not(bin(n,KP))):
      if n>KP[len(KP)-1]): KP.append(n)  # bigger than all known primes
      else: sinsert(n,KP)
  return ax
#

# find all prime factors of a number n (assume n>=0)

def primefactors(n):
   if isprime(n): return [n]
   F = []  # array to be returned
   if (n%2==0): F.append(2)
   i = 3
   while i <= n/2:
     if isprime(i) and n%i==0: F.append(i)
     i += 2
   #
   return F
#   

############ RSA encrpytion: pick two primes p and q, let n=p*q.  let
# e and d be such that  (e*d) % ((p-1)*(q-1)) == 1.  Then e is the
# public encryption key while d is the private decryption key.

# example:
p,q  = 73,67
e,d = 53,269
n = p*q

# convert string to array of ascii vals
def ords(s):
  A = [0]*len(s)
  i = 0
  while i<len(s):
    A[i] = ord(s[i])
    i += 1
  return A
#

# convert back
def chrs(A):
  S = ""
  i = 0
  while i<len(A):
    S = S+chr(A[i]) 
    i += 1
  return S
#

s = "Matt is not a dozer"

def crypt(key,n,A):  # key could be e or d - so this can decrypt or encrypt
  B = [0]*len(A)
  i = 0
  while i<len(A):
    B[i] = (A[i]**key) % n
    i+=1
  #
  return B

C = crypt(e,n,ords(s))
M = crypt(d,n,C)
print M
print chrs(M)