bn256 icon indicating copy to clipboard operation
bn256 copied to clipboard

Fuentes et al. algorithm for computing hard part of final exponentiation

Open Raneet10 opened this issue 2 years ago • 0 comments

This PR leverages the Fuentes et al. algorithm for computing the hard part of the final exponentiation based on the fact that f ^ d' is also a pairing and can be computed at least as efficiently as f ^ d where d' is a multiple of d and d = Φk(p)/r = (p⁴ − p² + 1)/r

goos: darwin
goarch: arm64
pkg: github.com/cloudflare/bn256
           │   old.txt   │              new.txt               │
           │   sec/op    │   sec/op     vs base               │
Pairing-10   695.0µ ± 0%   680.5µ ± 0%  -2.09% (p=0.000 n=50)

           │   old.txt    │            new.txt             │
           │     B/op     │     B/op      vs base          │
Pairing-10   38.25Ki ± 0%   38.25Ki ± 0%  ~ (p=1.000 n=50)

           │  old.txt   │            new.txt             │
           │ allocs/op  │ allocs/op   vs base            │
Pairing-10   352.0 ± 0%   352.0 ± 0%  ~ (p=1.000 n=50) ¹
¹ all samples are equal

The benchmark indicates slight improvement but I'd really love to get reviews to see whether further optimizations can be made. Thank you!

Raneet10 avatar Sep 16 '23 20:09 Raneet10