Geodesic
On generic complexity of the integer factorization problem
Prikladnaâ diskretnaâ matematika, no. 3 (2023), pp. 121-126.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\text{P} = \text{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.
Keywords: generic complexity, integer factorization. 
@article{PDM_2023_3_a6,
     author = {A. N. Rybalov},
     title = {On generic complexity of the integer factorization problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {121--126},
     publisher = {mathdoc},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_3_a6/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic complexity of the integer factorization problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 121
EP  - 126
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_3_a6/
LA  - ru
ID  - PDM_2023_3_a6
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic complexity of the integer factorization problem
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 121-126
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_3_a6/
%G ru
%F PDM_2023_3_a6
A. N. Rybalov. On generic complexity of the integer factorization problem. Prikladnaâ diskretnaâ matematika, no. 3 (2023), pp. 121-126. http://geodesic.mathdoc.fr/item/PDM_2023_3_a6/

[1] Adleman L. M. and McCurley K. S., “Open problems in number theoretic complexity, II”, LNCS, 877, 1994, 291–322 | MR | Zbl

[2] Rivest R., Shamir A., and Adleman L., “A method for obtaining digital signatures and public-key cryptosystems”, Commun. ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

[3] Rybalov A. N., “On generic complexity of the quadratic residuosity problem”, Prikladnaya Diskretnaya Matematika, 2015, no. 2(28), 54–58 (in Russian) | MR

[4] Rybalov A. N., “On generic complexity of the discrete logarithm problem”, Prikladnaya Diskretnaya Matematika, 2016, no. 3(33), 93–97 (in Russian) | Zbl

[5] Rybalov A. N., “On generic complexity of the problem of finding roots in groups of residues”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 95–100 (in Russian)

[6] Kapovich I., Miasnikov A., Schupp P., and Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[7] Impagliazzo R. and Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC (El Paso), ACM, 1997, 220–229 | MR