# Alfonso Cevallos. May 19 2015.
# Please report any mistakes.
# We work with Python numbers, and built-in elementary operations.
# We implement the simplified HNF algorithm, where the numbers can
# potentially grow exponentially large.
# The goal here is simply to understand the higher level idea of the algorithms.
import math
import os
import random
import time
def div(a,b): #computes (q,r) such that a = qb + r, with r < b
r = a%b
q = (a-r)/b
return q,r
def exgcd(a,b): #computes (g,x,y) such that gcd(a,b) = g = xa + yb
if a