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/