Implement curve BW6-761

[ggutoski]

Here's the paper: 2020/351 - Optimized and secure pairing-friendly elliptic curves suitable for one layer proof composition
Links to reference implementations in C++ and sage within.

This issue is a place to collect notes on development.

Branches

Work has already begun on branch feature/bw6-761. While working here, I re-designed the template generator to better facilitate new curves. This re-design is in experimental-pairing-gen, which is branched from feature/bw6-761. There's an active PR to merge experimental-pairing-gen back into feature/bw6-761: #5

It was decided during offline discussion that work on BW6-761 would continue on experimental-pairing-gen, and that branch will be merged into develop only once BW6-761 is complete.

Tests for the field tower, Frobenius, final exponentiation

Tests for the field tower (including Frobenius, final exponentiation) for existing curves (BLS12-377, BLS12-381, BN256) were generated using a template before gurvy was split from gnark. That template was removed from both gnark and gurvy, but the tests generated by it are still used.

In order to get things done as quickly as possible, I dug up this template in order to generate new tests for BW6-761.

• The old gnark commit with the testpoint generator: gnark@7dcd496ba42799bf1d4b695226ce6cc4c1f48792
• I added some new commits to gnark with fresh code for BW6-761: gnark@f1c4c75b9e0cd3e1b48e22f3d30dfa9a3543c9b7
• These commits are in an orphan branch of gnark that might be deleted in the future. gnark@bw6-tower-tests

I used a throwaway sage script to assist in debugging the final exponentiation for BW6-761 and for comparison against the sage reference implementation cited above. I put that script into git so that it can be found in the future and then deleted it from the repo. It can be found here: 6c7511c

[ggutoski]

Summary from #5 (comment) : BW6-761 now has a working pairing merged into develop. Several optimizations remain TODO:

• Fully optimized Miller loop with 127-bit loop length
• Hard-code the non-residue constants.
• Several clean-up tasks

[ggutoski]

Optimized Miller loop with 127-bit loop length working as of commit 5cb7d98