2.1.2 Euclidean Algorithms

2.1.2 Euclidean Algorithms

Let a and b be non-negative integers, each less than or equal to n. The number of bits

in binary representation of n is ln n + 1, and this number is approximated by ln n. The

number of bit operations for the four basic integer operations of addition , subtraction,

multiplication, and division using classical algorithms is summarized in Table 2.1.

Note

that, the above equations about the bit operations are well-known statements which

furture proofs and informaition can be found in references given in [1,2]. The other way

to write the above equations is as following. The notation T ime(A) denotes the number

of bit operations for the job needed in A.

T ime(a + b)=O (log(max(a, b))), bit operations, where a, b Є Z.

T ime(a × b)=O(log a log b), bit operations, where a, b Є Z.

T ime(a/b)=O(log a log b), bit operations, where a, b Є Z.

T ime( √a)=O(log3 a), bit operations, where a Є Z.

T ime(g^a mod b)=O(log a log^2b), where a, b Є Z, for some fixed integer g .

For computing the greatest common divisor of two integers the most e cient algorithm

is the Euclidean Algorithm which is based on the following simple fact.