C&SA | Contents

Volume 58 >>> № 2 MARCH — APRIL 2022

-->

UDC 511 UDC 519.6

М.V. Semotiuk¹

¹ V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

NUMBER-THEORETICAL METHODS FOR FACTORIZATION
OF COMPOZITE NUMBERS AND CALCULATION OF THE DISCRETE LOGARITHM

Abstract. The article is devoted to a new application of number-theoretic transformations. Representation of number systems by these transformations allows creating fundamentally new and efficient algorithms for factorizing numbers, calculating the period of the exponential function and the discrete logarithm. The factorization algorithm allows you to decompose any finite product into factors in one pass, and is also an exact test of the simplicity of numbers. Based on the representation of number systems by number-theoretic transformation, these algorithms have no analogs in the world, since they only use simple arithmetic operations. Information about the simplicity of numbers or other properties of numbers is not applied; therefore, factorization of numbers, calculations of the period of the exponential function and of the discrete logarithm are simply arithmetic operations, are performed in finite time, and belong to the P-class of complexity.

Keywords: set, faces of a set, algebra, residue ring, modulus, axiomatics of integers, number-theoretic transformation, number system, radix, factorization, arithmetic operation, exponential function period, discrete logarithm.

FULL TEXT

REFERENCES

Ishmukhamedov Sh.T., Rubtsova R.G. On the complexity of the problem of factorization of natural numbers. Kazan: Bulletin of the TSGPU. 2007. N 2–3. P. 4–6.

Semotiuk M.V. On the analytical method of factorization of composite numbers. Kiev: V.M. Glushkov Institute of Cybernetics, NAS of Ukraine. Komp’yuterní zasoby, merezhí ta sistemy. 2013. N 12. P. 5–10.

Semotiuk M.V. Notes on machine algebra [in Russian]. Kiev: Stal, 2012. 250 p.

Semotiuk M.V. Generalized number-theoretic transformation. Kiev: V.M. Glushkov Institute of Cybernetics, NAS of Ukraine. 1994. 29 p. (Prepr. / National Academy of Sciences of Ukraine, V.M. Glushkov Institute of Cybernetics, 94–8).

Semotiuk M.V. Number-theoretic representations of number systems. Kiev: USiM, 2004. N 5. P. 36–42.

Van der Waerden B.L. Algebra [Russian translation]. Moscow: Nauka, 1979. 624 p.

Nogin V.D. Introduction to mathematical analysis [in Russian]. SPb.: St. Petersburg. state polytechnic university., 1994. 62 p.

Olds C.D., Lax A., Davidoff G.P. The geometry of numbers. Washington, DC: Mathematical association of America, 2000. ISBN 0-88385-643-3.

Koblitz N. A course in number theory and cryptography [Russian translation]. Moscow: Scientific publishing house TVP, 2001. 254 p.

UDC 511 UDC 519.6

NUMBER-THEORETICAL METHODS FOR FACTORIZATION OF COMPOZITE NUMBERS AND CALCULATION OF THE DISCRETE LOGARITHM

REFERENCES

NUMBER-THEORETICAL METHODS FOR FACTORIZATION
OF COMPOZITE NUMBERS AND CALCULATION OF THE DISCRETE LOGARITHM