Description

Revisiting quadratic and cubic field extensions using Karatsuba, Toom-Cook-3 and Chung-Hasan (sq). Basically experiments show that Karatsuba is better but this PR just saves some (emulated) subtractions here and there. Direct extensions using Toom-Cook work nice; for example an (unoptimized) version Toom-Cook-6 saves ~2k scs per multiplication (theoretically it saves 7 Fp-mul but uses more adds/subs) . However they are removed from this PR for now because the pairing implementation should be rewritten in the direct extension (Karabina, Granger-Scott, lines...), which will be in a separate PR.

Type of change

• New feature (non-breaking change which adds functionality)

How has this been tested?

Existing tests work.

How has this been benchmarked?

• PLONK verifier circuit on bw6-761:

  • old: 32,145,457 scs
  • new: 32,094,676 scs

• Pairing check circuit e(a,b)e(c,d)==1 on BN254:

  • old: 6,674,047 scs
  • new: 6,620,773 scs

• Pairing check circuit e(a,b)e(c,d)==1 on BLS12-381:

  • old: 8,928,354 scs
  • new: 8,792,606 scs

Checklist:

• I have performed a self-review of my code
• I have commented my code, particularly in hard-to-understand areas
• I have made corresponding changes to the documentation
• I have added tests that prove my fix is effective or that my feature works
• I did not modify files generated from templates
• golangci-lint does not output errors locally
• New and existing unit tests pass locally with my changes
• Any dependent changes have been merged and published in downstream modules