On the generic complexity of the square root modulo prime problem

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.