Semotiuk M.V.
Number-theoretical methods for factorization of composite numbers and calculation of the discrete logarithm

The article is devoted to the new application of number-theoretic transforms. Representing number systems by these transforms allows us to create fundamentally new and efficient algorithms for factoring numbers and to calculate period of the exponential function and of the discrete logarithm. The factorization algorithm allows us to decompose any finite product into factors in one run, it is an exact test of number simplicity. This algorithm is based on representing number systems by a number-theoretic transforms and has no analogs in the world since it uses only simple arithmetic operations. Properties of number simplicity or other number properties are not applied. Thus, number factoring and calculations of the exponential function period and of the discrete logarithm are simple arithmetic operations that are performed in a finite time and belong to the complexity class P. © 2022, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: algebra, arithmetic operation, axiomatics of integers, discrete logarithm, exponential function period, faces of a set, factorization, modulus, number system, number-theoretic transformation, radix, residue ring, set, Exponential functions, Factorization, Arithmetic operations, Axiomatic of integer, Axiomatics, Discrete logarithms, Exponential function period, Face of a set, Modulus, Number system, Number-theoretic transformation, Radix, Residue rings, Set, Numbering systems

Cite:
Semotiuk M.V. (2022). Number-theoretical methods for factorization of composite numbers and calculation of the discrete logarithm. Cybernetics and Systems Analysis, 58 (2), 178–188. doi: https://doi.org/10.1007/s10559-022-00463-0 http://jnas.nbuv.gov.ua/article/UJRN-0001313072 [In Ukrainian].