350 rub
Journal Neurocomputers №9 for 2014 г.
Article in number:
Implementation of montgomery algorithm in residue number system based on efficiency algorithms of base extension
Keywords: modular arithmetic arbitrary-precision arithmetic Residue number system mixed radix number system Montgomery multiplication reduction modular exponentiation
Authors:
N.I. Chervyakov - Dr.Sc. (Eng.), Professor, Head of the Department of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol, Russia. E-mail: k-fmf-primath@stavsu.ru
M.A. Deryabin - Post-graduate Student, Junior Research Scientist, Department of Applied Mathematics and Mathematical Modeling, North-Caucasus Federal University, Stavropol, Russia. E-mail: maxim.deryabin@gmail.com
I.N. Lavrinenko - Ph.D. (Phys.-Math.), Associate Professor, Department of High Algebra and Geometry, North-Caucasus Federal University, Stavropol, Russia. E-mail: k-fmf-primath@stavsu.ru
Abstract:
In this paper proposed a method of modular exponentiation based on Montgomery multiplication in the Residue number system. Nonpositional Montgomery multiplication allows to avoid the necessity of using an algorithms of arbitrary-precision arithmetic. The paper presents how to implement basic arithmetic operations for numbers represented in arbitrary-precision arithmetic and in Residue Number System. The comparative analysis of Montgomery multiplication and exponentiation for traditional positional arithmetic and in Residue number system showed high efficiency of modular arithmetic for this task. The experimental data show that an increase in the total bit system obtained through the use of Residue Number System acceleration increases continuously.
Pages: 37-45
References

  1. Montgomery P.L. Modular Multiplication Without Trial Division. Mathematics of Computation. 1985. V. 44. № 170. R. 519-521.
  2. Omondi A., Premkumar B. Residue number systems. Theory and Implementation. London. Imperial College Press. 2007. 295 p.
  3. Chervyakov N.I., Yevdokimov A.A., Galushkin A.I., Lavrienko I.N., Lavrienko A.V. Primenenie iskusstvennykh neyronnykh setey i sistemy ostatochnykh klassov v kriptografii. M.: FIZMATLIT. 2012. 280 s.
  4. Schinianakis D. and Stouraitis T. A RNS Montgomery multiplication architecture // Circuits and Systems (ISCAS). 2011. IEEE International Symposium on, May 2011. R. 1167-1170.
  5. Chervyakov N.I., Sakhnyuk P.A., Shaposhnikov A.V., Makokha A.N. Neyrokomp'yutery v ostatochnykh klassakh. M.: Radiotekhnika. 2003. 272 s.
  6. Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. 1996.
  7. Knuth D.E. The Art of Computer Programming. V. 2. Seminumerical Algorithms. Third Edition. Addison-Wesley. 1998.
  8. Chervyakov N.I. Realizatsiya vysokoeffektivnoy modulyarnoy tsifrovoy obrabotki signalov na osnove programmiruemykh logicheskikh integral'nykh skhem // Neyrokomp'yutery: razrabotka i primenenie. 2006. № 10. S. 24-36.
  9. Chervyakov N.I., Babenko M.G., Lyakhov P.A., Lavrinenko I.N. Effektivnyy algoritm tochnogo opredeleniya universal'noy pozitsionnoy kharakteristiki modulyarnykh chisel i ego primenenie dlya vychisleniya osnovnykh problemnykh operatsiy v sisteme ostatochnykh klassov // Infokommunikatsionnye tekhnologii. 2014. T. 12. № 1. S. 4-18.