Finding the inverse of a polynomial modulo in the ring Z[X] based on the method of undetermined coefficients

• Autorzy: Yakymenko, Ihor , Kasianchuk, Mykhailo , Karpinski, Mikolaj , Shevchuk, Ruslan , Shylinska, Inna
• Języki publikacji: EN

Abstrakty

EN

This paper presents the theoretical foundations of finding the inverse of a poly-nomial modulo in the ringZ[x]based on the method of undetermined coefficients. The use of the latter makes it possible to significantly reduce the timecomplexity of calculations avoiding the operation of finding the greatest common divisor. An example of calculating the inverse of a polynomial modulo inthe ringZ[x]based on the proposed approach is given. Analytical expressionsof the time complexities of the developed and classical methods depending onthe degrees of polynomials are built. The graphic dependence of the complexityof performing the operation of finding the inverse of a polynomial in the ringZ[x]is presented, which shows the advantages of the method based on unde-termined coefficients. It is found that the efficiency of the developed methodincreases logarithmically with an increase in the degrees of polynomials

Słowa kluczowe

EN

inverse of a polynomial modulo; ring of polynomials; euclidean algorithm; degree of a polynomial; method of undetermined coefficients; time complexity; efficiency

• Czasopismo: Computer Science
• Rocznik: 2024
• Tom: T. 25 (2)
• Strony: 239--252
• Opis fizyczny: Bibliogr. 45 poz., rys., tab.

Twórcy

autor

Yakymenko, Ihor

• West Ukrainian National University, Department of Cyber Security, 46009 Ternopil, Ukraine

autor

Kasianchuk, Mykhailo

• West Ukrainian National University, Department of Cyber Security, 46009 Ternopil, Ukraine

autor

Karpinski, Mikolaj

• University of the National Education Commission, Institute of Security and ComputerScience, 30-084 Krakow, Poland
• Ternopil Ivan Puluj National Technical University, Department of Cyber Security, 46001Ternopil, Ukraine

autor

Shevchuk, Ruslan

• University of Bielsko-Biala, Department of Computer Science and Automatics, 43-309Bielsko-Biala, Poland
• West Ukrainian National University, Department of Computer Science, 46009 Ternopil, Ukraine

autor

Shylinska, Inna

• West Ukrainian National University, Foreign Languages and Information CommunicationTechnologies Department, 46009 Ternopil, Ukraine

Bibliografia

• [1] Abdulazeez S.T., Hussein A.M.: The Existence of a Polynomial Inverse Integrating Factors and Studies About the Limit Cycles for Cubic, Quartic and Quintic Polynomial Systems, Baghdad Science Journal, vol. 18(2), pp. 0322–0322, 2021. doi: 10.21123/bsj.2021.18.2.0322.
• [2] Aho A.V., Hopcroft J.E.: The design and analysis of computer algorithms, Pearson Education India, 1974.
• [3] Andrijchuk V.A., Kuritnyk I.P., Kasyanchuk M.M., Karpinski M.P.: Modern algorithms and methods of the person biometric identification. In: 2005 IEEE Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, pp. 403–406, IEEE, 2005. doi: 10.1109/idaacs.2005.283012.
• [4] Ashraphijuo M., Madani R., Lavaei J.: Inverse function theorem for polynomial equations using semidefinite programming. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 6589–6596, IEEE, 2015. doi: 10.1109/ cdc.2015.7403257.
• [5] Beyer W.H.: CRC standard mathematical tables. 25th Edition, CRC Press, West Palm Beach, 1978.
• [6] Boucher D., Ulmer F.: Linear codes using skew polynomials with automorphisms and derivations, Designs, Codes and Cryptography, vol. 70, pp. 405–431, 2014. doi: 10.1007/s10623-012-9704-4.
• [7] Calvez L.C., Azou S., Vilb´e P.: Variation on Euclid’s algorithm for polynomials, Electronics Letters, vol. 33(11), 1997. doi: 10.1049/el:19970658.
• [8] Chu J., Benaissa M.: GF(2m) multiplier using Polynomial Residue Number System. In: APCCAS 2008 – 2008 IEEE Asia Pacific Conference on Circuits and Systems, pp. 1514–1517, IEEE, 2008. doi: 10.1109/APCCAS.2008.4746320.
• [9] Dadkhahi H., Gotchev A., Egiazarian K.: Inverse polynomial reconstruction method in DCT domain, EURASIP Journal on Advances in Signal Processing, vol. 2012, pp. 1–23, 2012. doi: 10.1186/1687-6180-2012-133.
• [10] De Leon D.: Using Undetermined Coefficients to Solve Certain Classes of Variable-Coefficient Equations, The American Mathematical Monthly, vol. 122(3), pp. 246–255, 2015. doi: 10.4169/amer.math.monthly.122.03.246.
• [11] Drucker N., Gueron S., Kostic D.: Fast polynomial inversion for post quantum QC-MDPC cryptography, Information and Computation, vol. 281, 104799, 2021. doi: 10.1016/j.ic.2021.104799.
• [12] Dubeau F.: The method of undetermined coefficients: general approach and optimal error bounds, Journal of Mathematical Analysis, vol. 5(4), pp. 1–11, 2014. http://www.ilirias.com/jma/repository/docs/JMA5-4-1.pdf.
• [13] Gonz´alez-Cardel M.F., D´ıaz-Uribe R.: An analysis on the inversion of polynomials, Revista Mexicana de F´ısica, vol. 52(2), pp. 163–171, 2006. https: //rmf.smf.mx/ojs/index.php/rmf-e/article/view/4522.
• [14] Goupil A., Palicot J.: Variation on variation on Euclid’s algorithm, IEEE Signal Processing Letters, vol. 11(5), pp. 457–458, 2004. doi: 10.1109/lsp.2004.824053.
• [15] Harvey D., Hoeven van der J.: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Journal of Complexity, vol. 54, 101404, 2019. doi: 10.1016/j.jco.2019.03.004.
• [16] Ivasiev S., Kasianchuk M.M., Yakymenko I.Z., Shevchuk R., Karpinski M., Gomotiuk O.: Effective algorithms for finding the remainder of multi-digit numbers. In: 2019 9th International Conference on Advanced Computer Information Technologies (ACIT), pp. 175–178, IEEE, 2019. doi: 10.1109/acitt.2019.8779899.
• [17] Jassim W.A., Raveendran P., Mukundan R.: New orthogonal polynomials for speech signal and image processing, IET Signal Processing, vol. 6(8), pp. 713–723, 2012. doi: 10.1049/iet-spr.2011.0004.
• [18] Karpinski M., Rajba S., Zawislak S., Warwas K., Kasianchuk M.M., Ivasiev S., Yakymenko I.: A Method for Decimal Number Recovery from its Residues Based on the Addition of the Product Modules. In: 2019 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), pp. 13–17, IEEE, 2019. doi: 10.1109/idaacs.2019.8924395.
• [19] Kasianchuk M., Yakymenko I., Pazdriy I., Zastavnyy O.: Algorithms of findings of perfect shape modules of remaining classes system. In: The Experience of Designing and Application of CAD Systems in Microelectronics, pp. 316–318, IEEE, 2015. doi: 10.1109/cadsm.2015.7230866.
• [20] Kasianchuk M.M., Nykolaychuk Y.N., Yakymenko I.Z.: Theory and methods of constructing of modules system of the perfect modified form of the system of residual classes, Journal of Automation and Information Sciences, vol. 48(8), 2016. doi: 10.1615/jautomatinfscien.v48.i8.60.
• [21] Kasianchuk M.M., Yakymenko I.Z., Nykolaychuk Y.M.: Symmetric Cryptoalgorithms in the Residue Number System, Cybernetics and Systems Analysis, vol. 57(2), pp. 329–336, 2021. doi: 10.1007/s10559-021-00358-6.
• [22] Katagiri Y., Iwamura K., Nakanishi Y., Takano S., Suzuki R.: Arbitrary polynomial chaos expansion and its application to power flow analysis-Fast approximation of probability distribution by arbitrary polynomial expansion, Journal of Physics: Conference Series, vol. 1780, 012025, 2021. doi: 10.1088/1742-6596/ 1780/1/012025.
• [23] Kozaczko D., Ivasiev S., Yakymenko I., Kasianchuk M.: Vector module exponential in the remaining classes system. In: 2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), vol. 1, pp. 161–163, IEEE, 2015. doi: 10.1109/ idaacs.2015.7340720.
• [24] Krausz M., Land G., Richter-Brockmann J., G¨uneysu T.: Efficiently masking polynomial inversion at arbitrary order. In: International Conference on PostQuantum Cryptography, pp. 309–326, Springer, 2022. doi: 10.1007/978-3-031- 17234-2 15.
• [25] Kro´o A., Szabados J.: Inverse polynomial mappings and interpolation on several intervals, Journal of Mathematical Analysis and Applications, vol. 436(2), pp. 1165–1179, 2016. doi: 10.1016/j.jmaa.2015.12.032.
• [26] Kwasniewski L.: An Improved Method of Undetermined Coefficients, The Open Applied Mathematics Journal, vol. 3(1), pp. 33–39, 2009. doi: 10.2174/ 1874114200903010033.
• [27] Lasserre J.B.: Inverse polynomial optimization, Mathematics of Operations Research, vol. 38(3), pp. 418–436, 2013. doi: 10.1287/moor.1120.0578.
• [28] Liu C.L., Horng G., Liu H.Y.: Computing the modular inverses is as simple as computing the GCDs, Finite Fields and Their Applications, vol. 14(1), pp. 65–75, 2008. doi: 10.1016/j.ffa.2007.08.004.
• [29] Logan J.D.: A First Course in Differential Equations, Springer, New York, NY, 2006. doi: 10.1007/978-1-4419-7592-8.
• [30] Lombardi H., Quitt´e C.: The Method of Undetermined Coefficients. In: Commutative Algebra: Constructive Methods: Finite Projective Modules, pp. 77–172, Springer, 2015. doi: 10.1007/978-94-017-9944-7 3.
• [31] Milne J.S.: Algebraic Number Theory (v3.08), 2020, https://wwwjmilneorg/ math/CourseNotes/ANTpdf.
• [32] Moreno J., Saiz A.: Inverse functions of polynomials and its applications to initialize the search of solutions of polynomials and polynomial systems, Numerical Algorithms, vol. 58(2), pp. 203–233, 2011. doi: 10.1007/s11075-011-9453-x.
• [33] Nykolaychuk Y.M., Kasianchuk M.M., Yakymenko I.Z.: Theoretical foundations for the analytical computation of coefficients of basic numbers of Krestenson’s transformation, Cybernetics and Systems Analysis, vol. 50, pp. 649–654, 2014. doi: 10.1007/s10559-014-9654-0.
• [34] Nykolaychuk Y.M., Yakymenko I.Z., Vozna N.Y., Kasianchuk M.M.: Residue Number System Asymmetric Cryptoalgorithms, Cybernetics and Systems Analysis, vol. 58(4), pp. 611–618, 2022. doi: 10.1007/s10559-022-00494-7.
• [35] Nyokabi G.J., Salleh M., Mohamad I.: NTRU inverse polynomial algorithm based on circulant matrices using gauss-jordan elimination. In: 2017 6th ICT International Student Project Conference (ICT-ISPC), pp. 1–5, IEEE, 2017. doi: 10.1109/ict-ispc.2017.8075326.
• [36] Paliouras V., Skavantzos A., Stouraitis T.: Low power convolvers using the Polynomial Residue Number System. In: 2002 IEEE International Symposium on Circuits and Systems. Proceedings (Cat. No. 02CH37353), vol. 2, pp. II–II, IEEE, 2002.
• [37] Park C.M.: A Study on Constructing the Inverse Element Generator over GF (3 m), Journal of Information and Communication Convergence Engineering, vol. 8(3), pp. 317–322, 2010.
• [38] Puchinger S., Wachter-Zeh A.: Fast operations on linearized polynomials and their applications in coding theory, Journal of Symbolic Computation, vol. 89, pp. 194–215, 2018. doi: 10.1016/j.jsc.2017.11.012.
• [39] Rajba T., Klos-Witkowska A., Ivasiev S., Yakymenko I.Z., Kasianchuk M.M.: Research of time characteristics of search methods of inverse element by the module. In: 2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), vol. 1, pp. 82–85, IEEE, 2017. doi: 10.1109/idaacs.2017.8095054.
• [40] Rosen K.H.: Handbook of discrete and combinatorial mathematics, CRC Press, 1999.
• [41] Shams M., Rafiq N., Kausar N., Ahmed S.F., Mir N.A., Chandra Saha S.: Inverse Family of Numerical Methods for Approximating All Simple and Roots with Multiplicity of Nonlinear Polynomial Equations with Engineering Applications, Mathematical Problems in Engineering, vol. 2021, pp. 1–9, 2021. doi: 10.1155/ 2021/3124615.
• [42] Xiao F., Lu D., Wang D.: Solving multivariate polynomial matrix Diophantine equations with Gr¨obner basis method, Journal of Systems Science and Complexity, vol. 35(1), pp. 413–426, 2022.
• [43] Yakymenko I., Kasianchuk M., Shylinska I., Shevchuk R., Yatskiv V., Karpinski M.: Polynomial Rabin Cryptosystem Based on the Operation of Addition. In: 2022 12th International Conference on Advanced Computer Information Technologies (ACIT), pp. 345–350, IEEE, 2022. doi: 10.1109/acit54803.2022.9913089.
• [44] Yakymenko I., Kasyanchuk M., Nykolajchuk Y.: Matrix algorithms of processing of the information flow in computer systems based on theoretical and numerical Krestenson’s basis. In: 2010 International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET), pp. 241–241, IEEE, 2010.
• [45] Zheng Y., Wang Q., Wei W.: On inverses of permutation polynomials of small degree over finite fields, IEEE Transactions on Information Theory, vol. 66(2), pp. 914–922, 2019. doi: 10.1109/tit.2019.2939113.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).

Identyfikatory

DOI

10.7494/csci.2024.25.2.5740