Random Articles
Reseach Article
A Comparison of Several Greatest Common Divisor(GCD)Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 26 - Number 5 |
| Year of Publication: 2011 |
| Authors: Haroon Altarawneh |
10.5120/3099-4253
|
Haroon Altarawneh . A Comparison of Several Greatest Common Divisor(GCD)Algorithms. International Journal of Computer Applications. 26, 5 ( July 2011), 24-31. DOI=10.5120/3099-4253
Abstract
This paper about Greater Common Divisor GCD, the paper shows that there is a lot of algorithms, some of these algorithm is good in timing and make low number of iteration, the other make a lot of iteration with a lot of time! But as we see in the analysis of the algorithms that some of the algorithms is faster than the others in small numbers (like Brute force is faster than Bishop Algorithm in the small numbers, but in the large numbers the Bishop Algorithm is too fast with comparison with the brute force) so the researchers recommend to develop the Bishop algorithm the make it more efficient in computing the GCD for small numbers. In the other hand the Dijkstra algorithm is too close in timing and number of iteration with the Bishop algorithm. But as we see in the analysis the best algorithm to use in computing the GCD in all type of integers is the Extended Euclidean algorithm which makes few loops with small or large numbers.
References
- Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996.
- eLiteral The Moving Constant available at http://services.eliteral.com/digital-certificate-mumbai/chap14.php
- Washington University, St. Louis available at http://www.cs.wustl.edu/~kjg/cs101/Notes/Recursion/recursion.html
- Centre for Information Security and Cryptography available at http://cisac.math.ucalgary.ca/news_events/hugh/talks/sorenson.pdf
- National Institute of Standards and Technology available at http://www.nist.gov/dads/
- Computer Science Ben Gurion University of the Negev available at http://www.cs.bgu.ac.il/~berend/teaching/Intro2CS/examples/main.html
Index Terms
Keywords