Assert is not square

[Sarkoxed]

Problem

Add an assert_is_not_square method to BigNum (from Zac’s old TODO).

This method should assert that a private input is not a quadratic residue in the BigNum field.

Happy Case

Can be done via something like

/// Compute a non-square parameters
///
/// Find a square root of (multiplier * input), where
///       input is not a quadratic residue
///       multiplier is not a quadratic residue (constant)
///       hence multiplier * input is a quadratic residue
///       
///       next we can create an assertion: multiplier^2 * (input)^2  - result == 0 (mod MOD)
pub(crate) unconstrained fn __not_square_params<let N: u32, let MOD_BITS: u32>(
    params: BigNumParams<N, MOD_BITS>,
    input: [u128; N],
) -> ([u128; N], [u128; N]) {
    // Note: we could use -1 for p % 4 == 3, but it would leak the second bit of a prime (yikes)
    // however the multiplier itself can leak some negligible probabilities anyway
    let multiplier: [u128; N] = __quadratic_non_residue(params);
    let quadratic_residue: [u128; N] = __mul(params, multiplier, input);
    (multiplier, __sqrt(params, quadratic_residue).unwrap())
}

Should make the multiplier public, at least for comptime BigNum. Maybe precompute it into params or return it as a public output.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Nice-to-have

Blocker Context

No response

Would you like to submit a PR for this Issue?

Maybe

Support Needs

No response