On generic complexity of the integer factorization problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 61. DOI: 10.17223/20710410/61/7

In the paper, we study the generic complexity of the integer factorization problem. This problem, which goes back to Gauss, has important applications in modern cryptography. For example, the cryptographic strength of the famous public key encryption system RSA is based on the assumption of its hardness. We prove that under the condition of worst-case hardness and P = BPP for the problem of integer factorization there is no polynomial strongly generic algorithm. A strongly generic algorithm solves a problem not on the entire set of inputs, but on a subset whose frequency sequence converges exponentially to 1 with increasing size. To prove this theorem, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense. The main component of this method is the cloning technique, which combines problem inputs together into sufficiently large sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.