20-05-2013, 04:25 PM
Number Theory Algorithms and Cryptography Algorithms
Theory Algorithms.ppt (Size: 774 KB / Downloads: 26)
Number Theory Algorithms (cont’d)
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations. The best known problem in the field is integer factorization.
The running time of Euclid’s algorithm
We analyze the worst-case running time of EUCLID as a function of the size of a
And b. We assume with no loss of generality that a>b≥0.
The overall running time of EUCLID is proportional to the number of recursive
calls it makes. Our analysis makes use of the Fibonacci numbers.