bn256
bn256 copied to clipboard
Fuentes et al. algorithm for computing hard part of final exponentiation
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!