On the generic complexity of the square root modulo prime problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 62. DOI: 10.17223/20710410/62/9

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.
  • Title On the generic complexity of the square root modulo prime problem
  • Headline On the generic complexity of the square root modulo prime problem
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 62
  • Date:
  • DOI 10.17223/20710410/62/9
Keywords
generic complexity, square root modulo prime
Authors
References
Erdos Р. Remarks on number theory I // Mat. Lapok. 1961. V. 12. P. 10-17.
Рыбалов A. H. О генерической сложности проблемы распознавания квадратичных вычетов // Прикладная дискретная математика. 2015. №2(28). С. 54-58.
Adleman L. M. and McCurley K. S. Open problems in number theoretic complexity, II // LNCS. 1994. V.877. P.291-322.
Kapovich L, Miasnikov A., Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Ankeny N. C. The least quadratic non residue // Ann. Math. 1952. V. 55. P. 65-72.
Cipolla М. Un metodo per la risoluzione della congruenza di secondo grado // Rendiconto dell' Accademia delle Scienze Fisiche e Matematiche. Napoli, 1904. V. 10. No. 3. P.144-150, (in Italian).
 On the generic complexity of the square root modulo prime problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 62. DOI: 10.17223/20710410/62/9
On the generic complexity of the square root modulo prime problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 62. DOI: 10.17223/20710410/62/9
Download full-text version
Counter downloads: 86