Function SolveModularQuadraticEquation

src/cryptopp/nbtheory.cpp:623–646

}

bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
{
	Integer D = (b.Squared() - 4*a*c) % p;
	switch (Jacobi(D, p))
	{
	default:
		CRYPTOPP_ASSERT(false);	// not reached
		return false;
	case -1:
		return false;
	case 0:
		r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
		CRYPTOPP_ASSERT(((r1.Squared()*a + r1*b + c) % p).IsZero());
		return true;
	case 1:
		Integer s = ModularSquareRoot(D, p);
		Integer t = (a+a).InverseMod(p);
		r1 = (s-b)*t % p;
		r2 = (-s-b)*t % p;
		CRYPTOPP_ASSERT(((r1.Squared()*a + r1*b + c) % p).IsZero());
		CRYPTOPP_ASSERT(((r2.Squared()*a + r2*b + c) % p).IsZero());
		return true;
	}
}

Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq,
					const Integer &p, const Integer &q, const Integer &u)