Tuyển tập báo cáo các nghiên cứu khoa học quốc tế ngành hóa học dành cho các bạn yêu hóa học tham khảo đề tài: Modular Inverse Algorithms Without Multiplications for Cryptographic Applications | Hindawi Publishing Corporation EURASIP Journal on Embedded Systems Volume 2006 Article ID 32192 Pages 1-13 DOI ES 2006 32192 Modular Inverse Algorithms Without Multiplications for Cryptographic Applications Laszlo Hars Seagate Research 1251 Waterfront Place Pittsburgh PA 15222 USA Received 19 July 2005 Revised 1 December 2005 Accepted 17 January 2006 Recommended for Publication by Sandro Bartolini Hardware and algorithmic optimization techniques are presented to the left-shift right-shift and the traditional Euclidean-modular inverse algorithms. Theoretical arguments and extensive simulations determined the resulting expected running time. On many computational platforms these turn out to be the fastest known algorithms for moderate operand lengths. They are based on variants of Euclidean-type extended GCD algorithms. On the considered computational platforms for operand lengths used in cryptography the fastest presented modular inverse algorithms need about twice the time of modular multiplications or even less. Consequently in elliptic curve cryptography delaying modular divisions is slower affine coordinates are the best and the RSA and ElGamal cryptosystems can be accelerated. Copyright 2006 Laszlo Hars. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use distribution and reproduction in any medium provided the original work is properly cited. 1. INTRODUCTION We present improved algorithms for computing the inverse of large integers modulo a given prime or composite number without multiplications of any kind. In most computational platforms they are much faster than the commonly used algorithms employing multiplications therefore the multiplier engines should be used for other tasks in parallel. The considered algorithms are based on different variants of the Euclidean-type greatest common divisor algorithms. They are iterative gradually decreasing the length of the operands and .
