I want to know the best optimal algoritm of gcd with its complexity if you have a any useful source I will be glad to have a look at it.
Current state of the art uses variants of Euclid's algorithm. Yet, it is proven to be non-optimal:
Even though its variants have significant speed improvements, I have not heard of a sequential optimal one. I guess one of the best modifications is Lehmer's algorithm. Extended Euclidean algorithms are also worth mentioning.
Furthermore, I guess optimality, or at least guaranteed bounds are obtained on parallel machines. One of such profound works prove a sequential complexity of O(n^2/log(n)) while achieving a paralel complexity, which is worth taking a look at :