[algorithm] Time complexity of Euclid's Algorithm

Gabriel Lame's Theorem bounds the number of steps by log(1/sqrt(5)*(a+1/2))-2, where the base of the log is (1+sqrt(5))/2. This is for the the worst case scenerio for the algorithm and it occurs when the inputs are consecutive Fibanocci numbers.

A slightly more liberal bound is: log a, where the base of the log is (sqrt(2)) is implied by Koblitz.

For cryptographic purposes we usually consider the bitwise complexity of the algorithms, taking into account that the bit size is given approximately by k=loga.

Here is a detailed analysis of the bitwise complexity of Euclid Algorith:

Although in most references the bitwise complexity of Euclid Algorithm is given by O(loga)^3 there exists a tighter bound which is O(loga)^2.

Consider; r0=a, r1=b, r0=q1.r1+r2 . . . ,ri-1=qi.ri+ri+1, . . . ,rm-2=qm-1.rm-1+rm rm-1=qm.rm

observe that: a=r0>=b=r1>r2>r3...>rm-1>rm>0 ..........(1)

and rm is the greatest common divisor of a and b.

By a Claim in Koblitz's book( A course in number Theory and Cryptography) is can be proven that: ri+1<(ri-1)/2 .................(2)

Again in Koblitz the number of bit operations required to divide a k-bit positive integer by an l-bit positive integer (assuming k>=l) is given as: (k-l+1).l ...................(3)

By (1) and (2) the number of divisons is O(loga) and so by (3) the total complexity is O(loga)^3.

Now this may be reduced to O(loga)^2 by a remark in Koblitz.

consider ki= logri +1

by (1) and (2) we have: ki+1<=ki for i=0,1,...,m-2,m-1 and ki+2<=(ki)-1 for i=0,1,...,m-2

and by (3) the total cost of the m divisons is bounded by: SUM [(ki-1)-((ki)-1))]*ki for i=0,1,2,..,m

rearranging this: SUM [(ki-1)-((ki)-1))]*ki<=4*k0^2

So the bitwise complexity of Euclid's Algorithm is O(loga)^2.

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to big-o

Differences between time complexity and space complexity? Determining complexity for recursive functions (Big O notation) What exactly does big ? notation represent? How to merge two sorted arrays into a sorted array? Time complexity of Euclid's Algorithm Are there any worse sorting algorithms than Bogosort (a.k.a Monkey Sort)? Append an object to a list in R in amortized constant time, O(1)? What does O(log n) mean exactly? Is log(n!) = T(n·log(n))? Difference between Big-O and Little-O Notation

Examples related to time-complexity

Find common substring between two strings Why is the time complexity of both DFS and BFS O( V + E ) How to find time complexity of an algorithm Hash table runtime complexity (insert, search and delete) matrix multiplication algorithm time complexity how to calculate binary search complexity What are the time complexities of various data structures? Complexities of binary tree traversals Time complexity of Euclid's Algorithm What does O(log n) mean exactly?

Examples related to iteration

Is there a way in Pandas to use previous row value in dataframe.apply when previous value is also calculated in the apply? How to loop over grouped Pandas dataframe? How to iterate through a list of dictionaries in Jinja template? How to iterate through an ArrayList of Objects of ArrayList of Objects? Ways to iterate over a list in Java Python list iterator behavior and next(iterator) How to loop through an array containing objects and access their properties recursion versus iteration What is the perfect counterpart in Python for "while not EOF" How to iterate over a JavaScript object?