The computational complexity of the extended Euclidean algorithm is $O(log(b)^2)$ ($b$ being the second integer) as referenced by Wikipedia. How to compute the complexity of the modified extended Euclidean algorithm for basis reduction? I know that complexity is equal to the number of iterations multiplied by the cost of iterations. I can compute the cost of iteration but I am not sure how to deal with the number of iterations? enter image description here

  • $\begingroup$ I'm voting to close this question as off-topic because it appears to be a question about mathematics and/or computer science with no immediate relevance to cryptography. $\endgroup$ – Ella Rose Sep 11 '18 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.