Geodesic
On the generic complexity of the problem of~computing~the Euler function
Prikladnaâ diskretnaâ matematika, no. 3 (2024), pp. 110-117.

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

We study the generic complexity of the problem of the Euler function computation. This problem 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}$ there is no polynomial strongly generic algorithm for this problem. For a strongly generic polynomial algorithm, there is no efficient method for random generation of inputs on which the algorithm cannot solve the problem. Thus, this result justifies the application of the problem of computing the Euler function in public key cryptography. To prove this theorem, we use the method of generic amplification, which allows us to construct generically hard problems from the problems that are hard in the classical sense. The main feature of this method is the cloning technique, which combines the input data of a problem into sufficiently large sets of equivalent input data. Equivalence is understood in the sense that the problem is solved in a similar way for them.
Keywords: generic complexity, Euler function. 
@article{PDM_2024_3_a5,
     author = {A. N. Rybalov},
     title = {On the generic complexity of the problem of~computing~the {Euler} function},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {110--117},
     publisher = {mathdoc},
     number = {3},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_3_a5/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On the generic complexity of the problem of~computing~the Euler function
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 110
EP  - 117
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_3_a5/
LA  - ru
ID  - PDM_2024_3_a5
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On the generic complexity of the problem of~computing~the Euler function
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 110-117
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_3_a5/
%G ru
%F PDM_2024_3_a5
A. N. Rybalov. On the generic complexity of the problem of~computing~the Euler function. Prikladnaâ diskretnaâ matematika, no. 3 (2024), pp. 110-117. http://geodesic.mathdoc.fr/item/PDM_2024_3_a5/

[1] 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

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

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

[4] 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)

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

[6] 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

[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

[8] Vyalyy M., Kitaev A., and Shen' A., Classical and Quantum Computations, MCCME, CheRo, M., 1999, 192 pp. (in Russian)

[9] Agrawal M., Kayal N., and Saxena N., “PRIMES is in P”, Ann. Math., 160:2 (2004), 781–793 | DOI | MR | Zbl