Revision history [back]

Yes, an algorithm exists called the Tonelli-Shanks algorithm that can find the value of x such that x² ≡ a (mod b) when given a and b, under certain conditions. Specifically, b must be an odd prime number and a must be a quadratic residue modulo b (i.e. a must have a modular square root modulo b). The Tonelli-Shanks algorithm involves several steps of modular arithmetic and is a computationally efficient method for solving this type of equation.