[Question] Square root within mod

Revision en1, by valeriu, 2023-01-19 10:45:39

Hello codeforces,

Today, I am regretably in math class with the subject of modular arithmetic. While thinking about a problem, I reminded myself of a question I asked myself some time ago.

Given $$$p$$$ and $$$mod$$$, find a $$$q$$$ such that $$$q^2$$$ = $$$p$$$ (modulo $$$mod$$$). $$$mod$$$ is prime and ≫ $$$10^8$$$

Does this admit an online logarithmic-complexity solution?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English valeriu 2023-01-19 10:45:39 389 Initial revision (published)