Add: Cairo0 IsQuadResidue Hint

[Tomi-3-0]

Implement Cairo0 isQuadResidue hint #243

This hint checks if an input value x is a quadratic residue and calculates its square root. If x is not a quadratic residue, it computes the square root of the result of dividing x by 3 i.e., √(x/3) or 3 * y² = x;

The hint utilizes Legendre() method which returns 1 if x is a quadratic residue (i.e., z is congruent to x mod q: z ≡ x² (mod q)) and 0 or -1 if it isn't. Additionally, it returns 1 for input values of 1 or 0 for input values of 0, as 0² is always 0, and 1² is always 1, irrespective of the modulus.

Link to other helper methods used:

• Sqrt() function implementation
• Div() function implementation