# Examples of Algorithms that rely on Binary Factorization.

# The following function commutes m**e where e is a non-negative integer.
# This function is useful because sometimes (as in RSA encryption), we
# only need the last few digits of a number, not the entire number which
# could be very large.  This function computes the value in log(n) steps
# using binary factorization on n.  The reason binary factorization is
# an important algorithm is that it reduces time complexity from n to log(n).

def expmod(m,e,n):  # returns (m**e)%n in log(e) steps.
   if (e<0 or type(e) != type(1)): 
     raise Exception("Invalid exponent for expmod")
   ax = 1  # accumulator
   factor = m%n  # base factor
   while e>0:
     if e%2==1: ax = (ax*factor) %n
     factor = (factor*factor) % n
     e = e//2
   # while n>0
   return ax
#expmod


### The following function converts DNA symbols A, C, G, T into binary form,
# so that two bits are used to represent each symbol.  In other words,
# DNA sequences are interpreted as base-4 numbers.

DNACODE = "ACGT"
CODEDNA = {'A':0, 'C':1, 'G':2, 'T':3}
def dnaEncode(DnaStr):
    n = 0  # numerical value to be returned
    i = len(DnaStr)-1 # start at last digit
    power = 1  # this is 4**0
    while i>=0:
        code = CODEDNA[DnaStr[i]]
        n += code*power
        power *= 4  # power=power*4, next power of 4
        i -= 1
    #while
    return n
#

def dnaDecode(n):
    DnaStr = "" # string to be returned
    while n>0:
        code = n%4 # last 2 digits
        DnaStr = DNACODE[code] + DnaStr # construct backwards
        n = n//4  # shift 2 bits right
    #
    return DnaStr
#
print(dnaDecode(dnaEncode("GCATGAC"))) # should return same string