New Modified Euclidean and Binary Greatest Common Divisor Algorithm
| Autor: | Shailesh R. Sathe, Jitendra V. Tembhurne |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
021103 operations research Binary GCD algorithm Euclidean division Division algorithm 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Lehmer's GCD algorithm Euclidean algorithm 010201 computation theory & mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Greatest common divisor Euclidean domain Electrical and Electronic Engineering Algorithm Time complexity Mathematics |
| Zdroj: | IETE Journal of Research. 62:852-858 |
| ISSN: | 0974-780X 0377-2063 |
| DOI: | 10.1080/03772063.2016.1216809 |
| Popis: | The greatest common divisor (GCD) computation of non-negative integers are the open problem in arithmetic calculations such as cryptography, and factorization attacks. The integer GCD algorithm applies one or more different transformations to reduce the size of input integers a and b at each step performed. Such kinds of transformations are called as reduction. Based on the different reductions, we proposed an efficient implementation of Modified Euclid-Binary (ModEB) algorithm. The ModEB algorithm is based on modular reduction of Euclid's algorithm and the reduction based on the Binary GCD algorithm, where it reduces the integers by the largest powers of two and avoids multiplication and division, except by the powers of two, and hence it is potentially faster than the Euclid's and Binary algorithms. The worst case time complexity of the proposed algorithm is O(n2) with respect to the bit-time complexity for two n-bit integers. We also proposed the parallel version of GCD algorithm. The implement... |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |