MathAlgorithms

def gcdDef(a,b):
    if a % b == 0:
        result = b
    else:
        r = a % b
        result = gcd(b,r)
    return result
   
def ext_euclid(a,b):
  u,v, x,y = 1,0, 0,1  
  while a != 0:        
    quotient = b // a 
    remainder = b % a  
    new_u = x - u * quotient
    new_v = y - v * quotient
    b,a, x,y, u,v = a, remainder, u,v, new_u, new_v 
  return (b,x,y)       
  
def primeFactors(n): 
    q = []  
    while n % 2 == 0: 
        q.append(2), 
        n = n / 2
    for i in range(3,int(n**.5)+1,2): 
          while n % i== 0: 
            q.append(i), 
            n = n / i 
    if n > 2: 
        q.append(n)
    return q 
    
def euler_phi_calc(n):
  q = primeFactors(n)
  if len(q)==1:
    return n - 1
  phi = 1
  counted = []
  for p in q:
    unique = True
    for j in counted:
      if p == j:
        unique = False
    if unique == True:    
      counted.append(p)
      exp = q.count(p)
      phi = phi * ((p**exp)-(p**(exp-1)))
  return phi
  
def fast_power_alg(a,e,n):
    remainder = 1
    while e > 0:
        if e % 2 == 1:
            remainder = (remainder * a) % n
        e = e // 2
        a = (a * a) % n
    return remainder

def primRoots(p):
    relative_primes = {i for i in range(1, p) if gcdDef(i, p) == 1}
    return [g for g in range(1, p) if relative_primes == {(g**exp)%p for exp in range(1, p)}]
primRoots(13)

def pollardFact(N):
  List =[]
  while(N%2==0):
    N=N/2
    List.append(2)
  while(N!=1):
    p = pollardCalc(int(N))
    List.append(p)
    N = N/p
  return List
  
def pollardCalc(N): 
  a = 2
  n = 1
  fact=1
  while(fact==1): 
    a = (a**(n)) % N 
    fact = gcdDef((a-1), N) 
    if (fact != 1): 
      return fact
    n += 1