New Modified Euclidean and Binary Greatest Common Divisor Algorithm

ABSTRACT

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(n²) with respect to the bit-time complexity for two n-bit integers. We also proposed the parallel version of GCD algorithm. The implementation results show that the iteration required to compute GCD using ModEB algorithm are substantially less as compared to different GCD algorithms.

KEYWORDS:

• Binary GCD
• Cryptography
• Euclid's GCD
• Parallel algorithm
• Reduction

ACKNOWLEDGMENTS

The research has been supported by Department of Computer Science and Engineering, Visvesvaraya National Institute of Technology (VNIT), Nagpur, India under TEQIP-II scheme of PhD enrolment 2011–2012.

Additional information

Notes on contributors

Jitendra V. Tembhurne

Jitendra V. Tembhurne completed his ME in computer science and engineering in 2011 and is currently pursuing PhD in the Department of Computer Science and Engineering, VNIT, Nagpur, Maharashtra, India. His area of research is the parallelization of algorithms in cryptography on multi-core and many-core architecture using OpenMP and CUDA.

E-mail: [email protected]

Shailesh R. Sathe

Shailesh R. Sathe completed his MTech from Indian Institute of Technology (IIT), Bombay and PhD from RTM Nagpur University (at VRCE/VNIT). At present, he is a professor in the Department of Computer Science and Engineering, VNIT, Nagpur, India. He has handled projects on information security and parallel processing. His current research interests include parallel processing, information security and algorithms etc. He has published more than 30 papers in various reputed international journals/conferences.

E-mail: [email protected]