[FEAT]: Utilize glv decomposition to speed up MSM operations

[PatStiles]

Description

Utilizing glv decomposition to decompose scalars into two scalars of half bit length has been shown to significantly improve MSM performance for curves with an efficiently computable endomorphism. Since Icicle supports curves such as BLS12-381 which have efficiently computable endomorphisms I am curious if these savings would translate well on gpu.

Ref:

• Paper: https://www.iacr.org/archive/crypto2001/21390189.pdf
• THE OG THREAD: Towards state-of-the-art multi-scalar-muls privacy-scaling-explorations/halo2curves#163
• GLV Design arkworks-rs/algebra#59
• GLV framework + precomp scripts arkworks-rs/snark#296
• https://hackmd.io/@aztec-network/rJ3VZcyZ9
• Add endo scalar decomposition privacy-scaling-explorations/halo2curves#24
• MSM optimization privacy-scaling-explorations/halo2#40
• https://github.com/demining/Endomorphism-Secp256k1/blob/main/README.md

[DmytroTym]

Thanks for the suggestion. We have a number of MSM optimisations in the pipeline and haven't really tried GLV yet. GPU codebases I know of don't really have it and I think Niall Emmart says that he wasn't able to speed up MSM with cube root endomorphism at some point in this talk (couldn't find the exact timestamp). But we do have -1 endomorphism improvement in progress.