Geodesic
On the generic complexity of the square root modulo~prime problem
Prikladnaâ diskretnaâ matematika, no. 4 (2023), pp. 119-123.

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

We study the generic complexity of the problem of finding a square root modulo a prime number. The question about the computational complexity of this problem is still open. However, there are known algorithms (e.g. Cipolla's algorithm) which are polynomial if the extended Riemann hypothesis holds. We prove that this problem is generically decidable in polynomial time. In fact, this means that Cipolla's algorithm runs in polynomial time for “almost all” inputs. The notion “almost all” is formalized by introducing the asymptotic density on a set of input data.
Keywords: generic complexity, square root modulo prime. 
@article{PDM_2023_4_a8,
     author = {A. N. Rybalov},
     title = {On the generic complexity of the square root modulo~prime problem},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {119--123},
     publisher = {mathdoc},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_4_a8/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On the generic complexity of the square root modulo~prime problem
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 119
EP  - 123
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_4_a8/
LA  - ru
ID  - PDM_2023_4_a8
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On the generic complexity of the square root modulo~prime problem
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 119-123
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_4_a8/
%G ru
%F PDM_2023_4_a8
A. N. Rybalov. On the generic complexity of the square root modulo~prime problem. Prikladnaâ diskretnaâ matematika, no. 4 (2023), pp. 119-123. http://geodesic.mathdoc.fr/item/PDM_2023_4_a8/

[1] Cipolla M., “Un metodo per la risoluzione della congruenza di secondo grado”, Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche. Napoli, 10:3 (1904), 144–150 (in Italian)

[2] Ankeny N. C., “The least quadratic non residue”, Ann. Math., 55 (1952), 65–72 | DOI | MR | Zbl

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

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

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

[6] Erdos P., “Remarks on number theory I”, Mat. Lapok, 12 (1961), 10–17 | MR | Zbl