Add checks to quadratic residue sampling

[doowt]

To sample a quadratic residue mod n uniformly at random, one technique is to sample an integer between 1 and n-1, check that it is invertible, and square it, e.g. see here.

The added code ensures the randomly-sampled element that gets squared is invertible (which also implies it is non-zero, so no need to check it is non-zero separately).

In normal usage of this function for AnonCreds, n = p * q where p and q are large primes, so the probability that an element is not invertible is only 1 - (p-1)*(q-1) / (p*q) = 1/p + 1/q - 1/(p*q), which means the expectation on the number of iterations of the while loop is very close to 1.

(Now with DCO!)

[swcurran]

Thanks!

[doowt]

I have realised this issue has arisen because not all authors require the quadratic residues to be invertible. For confirmation that it is required in a CL signature, note that on page 24 of the CL10 paper the size of QR_n is stated as p' * q', which means it must be excluding non-units.

[mikelodder7]

just get the CI passing but otherwise the code looks good.

[andrewwhitehead]

It looks like rustfmt (cargo fmt) just needs to be run on the modified file.

Edit: I would also need to follow up to bring the native rust backend into alignment.