The current GLV implementation may not be correct

[weikengchen]

I tested on BN254 with Fr = 14226294082152339227274917010873249985458047913852393750281719691125978796426, the algorithm decomposes it into two numbers, one is 128 bits, but the other one is 191 bits. The computation result is correct, but this is clearly suboptimal.

It appears that the issue is due to the wrong sign of beta_2. Flipping its sign fixes the issue for BN254.

I find the tricky part is here.
https://github.com/arkworks-rs/algebra/blob/master/curves/bn254/src/curves/g1.rs#L60
https://github.com/arkworks-rs/algebra/blob/master/ec/src/scalar_mul/glv.rs#L40

A little bit uncertain how the GLV basis shall be presented.

Another issue is that the original GLV algorithm requires "rounded division" rather than simple division that the codebase currently uses. This would affect the result of one of the inequality in the GLV paper, where the rounded division (implying that the gap is smaller than "1/2") does have an impact on the decomposition quality.

Needs input from @simonmasson, @Pratyush, and @mmagician.

In addition, I think it helps to strength the GLV test by checking if the decomposition result is as expected.

[weikengchen]

I think we just need to implement this overdue code:

f293ae8#diff-d8344ecc09cd2bfaca236326b07295b62d2834de6561c999546f683ca49488e3R31

// could be nice to check if k1 and k2 are indeed small.

[weikengchen]

Let me submit a PR for test-template first to see how the issue can be handled.

[weikengchen]

Can confirm that BN254 failed the test:

---- curves::tests::g1_glv::test_scalar_decomposition stdout ----
thread 'curves::tests::g1_glv::test_scalar_decomposition' panicked at /home/ubuntu/Rustrover/algebra/test-templates/src/glv.rs:35:9:
k2 has 187 bits
note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

---- curves::tests::g2_glv::test_scalar_decomposition stdout ----
thread 'curves::tests::g2_glv::test_scalar_decomposition' panicked at /home/ubuntu/Rustrover/algebra/test-templates/src/glv.rs:35:9:
k2 has 187 bits