International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 8, No. 11, 8 Nov. 2016
Cover page and Table of Contents: PDF (size: 620KB)
The Analysis and Investigation of Multiplicative Inverse Searching Methods in the Ring of Integers Modulo M
Full Text (PDF, 620KB), PP.9-18
Views: 0 Downloads: 0
Author(s)
Zhengbing Hu
1,*
I. A. Dychka
2
Onai Mykola
2
Bartkoviak Andrii
2
Index Terms
Integers modulo m, Error control coding, Data security, Euclidean algorithm
Abstract
In this article an investigation into search operations for the multiplicative inverse in the ring of integers modulo m for Error Control Coding tasks and for data security is shown. The classification of the searching operation of the multiplicative inverse in the ring of integers modulo m is provided. The best values of parameters for Joye-Paillier method and Lehmer algorithm were also found. The improved Bradley modification for the extended Euclidean algorithm is also offered, which gives the operating speed improvement for 10-15%. The integrated experimental research of basic classes of searching methods for multiplicative inverse in the ring of integers modulo m is conducted for the first time and the analytical formulas for these calculations of random access memory necessary space when operated at k-ary RS-algorithms and their modifications are shown.
Cite This Paper
Zhengbing Hu, I. A. Dychka, Onai Mykola, Bartkoviak Andrii, "The Analysis and Investigation of Multiplicative Inverse Searching Methods in the Ring of Integers Modulo M", International Journal of Intelligent Systems and Applications (IJISA), Vol.8, No.11, pp.9-18, 2016. DOI:10.5815/ijisa.2016.11.02
Reference
[1]Darrel Hankerson Guide to EllipticCurve Cryptography / Hankerson Darrel, Menezes Alfred, Vanstone Scott // Springer-Verlag New York, USA. — 2004. — 311 p.
[2]Richard Crandall Prime Numbers A Computational Perspective / Crandall Richard, Pomerance Carl// Springer-Verlag New York, USA. — 2005. — 597 p.
[3]Guerric Meurice de Dormale, Philippe Bulens, Jean-Jacques Quisquater Efficient Modular Division Implementation ECC over GF(p) Affine Coordinates Application / Meurice de Dormale Guerric, Bulens Philippe, Quisquater Jean-Jacques // The 14th International Conference on Field Programmable Logic and Applications, FPL 2004, Volume 3203 of Lecture Notes in Computer Science. — 2004. — Pp. 231-240.
[4]Donald E. Knuth Art of Computer Programming, Volume 2: Seminumerical Algorithms / Knuth Donald // 3rd Edition by Addison-Wesley Professional, Canada. — 1997. — 784 p.
[5]Richard E. Blahut Theory and Practice of Error Control Codes / Blahut Richard E. // Addison-Wesley. — 1983. — 500 p.
[6]Henri Cohen A Course in Computational Algebraic Number Theory / Cohen Henri // Springer Science & Business Media. — 1993. — 534 p.
[7]S. Parthasarathy Multiplicative inverse in mod(m) / Parthasarathy S. // Algologic Technical Report #1/2012. — 2012. — P. 1-3.
[8]Robert Lorencz New Algorithm for Classical Modular Inverse/ Lorencz Robert // Cryptographic Hardware and Embedded Systems. International Workshop. — 2002. — P. 57-70.
[9]WolframMathWorld: http://mathworld.wolfram.com/CarmichaelFunction.html
[10]W. Fischer Note on fast computation of secret RSA exponents / Fischer W., Seifert J.-P. // Information Security and Privacy (ACISP 2002), vol. 2384 of Lecture Notes in Computer Science, Springer-Verlag. — 2002. — Pp. 136–143.
[11]Marc Joye GCD-Free Algorithms for Computing Modular Inverses / Joye Marc, Paillier Pascal // CHES 2003: Cologne, Germany. — 2003. — Pp. 243-253.
[12]Jonathan Sorenson Two fast GCD algorithms / Sorenson Jonathan // Journal of Algorithms 16 (1). — 1994. — Pp. 110-144.
[13]A.W. Bojanczyk A systolic algorithm for extended GCD / BojanczykA.W., BrentR.P. // Comput. Math. Applic. Vol. 14, No. 4. — 1987. — Pp. 233-238.