Investigate: can we do faster Jacobi symbol calculation with binary GCD?
Closed this issue · 7 comments
Given calculating the Jacobi symbol is a costly part of the Lucas test, it's worth investigating if we can make it faster by applying binary gcd.
For reference, OpenSSL does GCD (although not binary GCD) to compute Jacobi symbol.
https://github.com/openssl/openssl/blob/master/crypto/bn/bn_kron.c
Looks like the same method we use actually. It's not exactly GCD since there's no modulo calculation required (except modulo 4 and 8, which is trivial).
Looks like the same method we use actually. It's not exactly GCD since there's no modulo calculation required (except modulo 4 and 8, which is trivial).
Yeah, @fjarri you're right, but isn't this exactly the step of GCD of Euclidean algorithm?
/* (A, B) := (B mod |A|, |A|) */
err = !BN_nnmod(B, B, A, ctx);
// ...
tmp = A;
A = B;
B = tmp;
// ...https://github.com/openssl/openssl/blob/master/crypto/bn/bn_kron.c#L125
EDIT:
oh, nvm, you were referring to this repo, not OpenSSL one.
Actually, I was mistaken too, we also have modulo calculation here. But either way, I think the algorithm in OpenSSL is the same as the one we use.
FWIW I have benchmarked the approach in this crate against a few others and found this one to have very good performance compared to status quo (e.g. the algo proposed here: https://eprint.iacr.org/2024/1054).
I agree. I think our current implementation is good enough.