A general method for to decompose modular multiplicative inverse operators over Group of units.
Keywords:
Descomposition laws, Group of units, Bezout’s theorem, Modular multiplicative inverse operator, Algorithmic functional technique, Chinese remainder theoremAbstract
In this article, the notion of modular multiplicative inverse operator (MMIO)
ℐϱ : (Z/ϱZ)* → Z/ϱZ, ℐϱ (a) = a-1,
where ϱ=b × d >3 with b, d ∈ N, is introduced and studied. A general method to decompose (MMIO) over group of units of the form (Z/ϱZ)* is also discussed through a new algorithmic functional version of Bezout's theorem. As a result, interesting decomposition laws for (MMIO)'s over (Z/ϱZ)* are obtained. Several numerical examples confirming the theoretical results are also reported.
References
H. M. AL-Matari, S. J. Aboud, N. F. Shilbayeh, Fast Fraction-Integer Method for Computing Multiplicative Inverse, J. of Computing, 1, pp. 131—135, (2009).
O. Arazi, H. Qi, On calculiting multiplicative inverses modulo 2m, IEEE Trans. Comput 57, pp. 1435—1438, (2008).
J—C. Bajard, L. Imbert, A full RNS implementation of RSA, IEEE Trans. Comput 53, pp. 769—774, (2004).
J. W. Bos, Constant time modular inversion, J Cryptogr Eng 4, pp. 275—281, (2014).
L. A. Cortés—Vega, A functional technique based on the Euclidean algorithm with applications to 2-D acoustic diffractal diffusers, J. Phys.: Conf. Ser 633, pp. 1—6, (2015).
L. A. Cortés Vega, D. E. Rojas-Castro, Y.S. Santiago Ayala and S. C. RojasRomero, A technique based on the Euclidean algorithm and its applications to Cryptography and Nonlinear Diophantine Equations, Proyecciones. J. Math., 26, pp. 309-333, (2007).
T. J. Cox, P. D’Antonio, Acoustic Absorbers and Diffusers: Theory, Design and Application Spon Press, (2004).
Y. Dai, A. B. Borisov, K. Boyer, C. K. Rhodes, Computation with inverse states in a Finite Field FPα : The muon neutrino mass, the Unified-Strong-Electroweak coupling constant, and the Higgs mass, Sandia National Laboratory, Report SAND2000-2043, pp. 1—11, (2000).
Y. Dai, A.B. Borisov, K. Boyer, C.K. Rhodes, A p-Adic metric for particle mass scale organization with genetic divisors, Sandia National Laboratory, Report SAND2001-2903, pp. 1—12, (2001).
C. Ding, D. Pey, A. Salomaa, Chinese remainder Theorem: Applications in Computing, Coding, Cryptography, Singapure; World Scientific, (1999).
J-G. Dumas, On Newton-Rapshon iteration for multiplicative inverses modulo prime power, IEEE Trans. Comput 63, pp. 2106—2109, (2014).
J. Eichenauer, J. Lehn, A. Topuzoglu, A Nonlinear congruential pseudorandom numer generator with power two modulus, Math of Compt 51, pp. 757—759, (1988).
Y. Elrich, K. Chang, A. Gordon, R. Ronen, O. Navon, M. Rooks, G.J. Hanon, DNA Sudoku-harnessing high-throughput sequencing for multiplexed specimen analysis, Genome Res 19, pp. 1243—1253, (2009).
M. A. Fiol, Finite Abelian groups and the Chinese remainder theorem, Discrete Math 67, pp. 101—105, (1987).
L. Hars, Modular inverse algorithms without multiplications for cryptographic applications, J Embedded Systems 032192, pp. 1—13, (2006).
M. Joye and P. Paillier, GCD-Free algorithms for computing modular inverses, C.D. Walter et. al. (Eds.):CHES 2003, LNCS 2779. Springer-Verlag Berlin Heidelberg, pp. 243-253, (2003).
B. S. Jr. Kaliski, The montgomery inverse and its applications, IEEE Trans. Comput 44, pp. 1064—1065 (1995).
D. E. Knuth, The art of computer programming, 2, Semi-Numerical Algorithms, 3rd Edition, Addison-Wesley, Reading, MA, (1997).
W. H. Ko, Modular inverse and reciprocity formula, arXiv:1304.6778v1, pp. 1-7, (2013).
R. Lórencz, New algorithm for classical modular inverse, in Kaliski, B.S., Jr., Ko ̧c, C.K., and Paar, C. (Eds.):CHES 2002, LNCS Springer-Verlag Berlin, pp. 57—70, (2003).
D. R. Hankerson, A. J. Menezes, S. A. Vanstone, Guide to Elliptic curve cryptography, Springer, New York, N.Y, USA (2004).
L. P. Montgomery, Modular multiplication without trial division, Math. Comp 44, pp. 519—52, (1985).
T. Niven, S. H. Zuckerman, H. Montgomery, An introduction to the theory of numbers, 5nd ed. Jhon Wiley-Sons, Inc. (1991).
S. Parthasarathy, An interesting property of multiplicative inverse in mod(M), Algologic Tech. Reports, pp. 1—3, (2012).
E. Sava ̧s, C. K. Ko ̧c, The montgomery modular inverse revisited, IEEE Trans. Comput 49, pp. 763—766, (2000).
E. Sava ̧s, M. Nasser, A. A-A Gutub, C. K. Ko ̧c, Efficient unified Montgomory inversion with multibit shifting, IEEE Proc. Comput. Digit. Tech 152, pp. 489—498, (2005).
M. R. Schroeder, Number theory and in Science and comunication, 3rd ed. Springer, Berlin, (1997).
R. J. Sullivan, Microwave Radar Imaging and Advanced Concepts, 2nd ed. Scitech Pub Inc., (2004).
C. E. Towers, D. P. Towers, J. D. C. Jones, Time efficient Chinese remainder theorem algorithm for full-field fringe phase analysis in multiwavelenght interferometry, Optics Express 12, pp. 1136—1143, (2004).
S. B. Verkhovsky, Enhanced Euclid algorithm for modular multiplicative inverse and its application in Cryptographic protocols, Int. J. Commun. Network and System Sc 3, pp. 901—906, (2010).
S. Vollala, B.S. Degum, N. Ramasubramanian, Hardware desing for multiplicative modular inverse based on table look up technique, IEEE Computing and Network Commun (CoCoNet), pp. 520—523, (2015).
Y. Wang, Residue to binary converters based on net Chinese remainder theorems, IEEE Trans Circuits Syst. 47, pp. 197—204, (2000).
S. Wei, Computation of modular multiplicative inverse using residue signed-digit additions, IEEE Conf. Pub :2016 International SoC Design Conference (ISOCC), pp. 85—86, (2016).
Published
How to Cite
Issue
Section
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
