Utility Functions for the Simulation

The util.cpp file contains functions which are called from shor.cpp. Many of the functions are written to avoid overflow when calculating functions in which there are intermediate steps which may have large values. For example while factoring 15, $x^{255} \bmod 15$ is calculated, but the modular exponentiation function in util.cpp calculates it in such a manner that $x^{255}$ need not be explicitly calculated.