Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

small opt.: BN254 ML #82

Merged
merged 1 commit into from
Oct 19, 2021
Merged

small opt.: BN254 ML #82

merged 1 commit into from
Oct 19, 2021

Conversation

yelhousni
Copy link
Collaborator

@yelhousni yelhousni commented Oct 18, 2021

BN optimal ate Miller loop looks like: f_{v,Q} * line1 * line2 which is implemented this way (f_{v,Q} * line1) * line2 costing 2 full-sparse multiplications MulBy034() (2 x 13M = 26M with M in Fp2). This small PR changes it to f_{u,Q} * (line1 * line2) costing 1 sparse-sparse multiplication Mul034By034() and 1 full-sparse multiplication Mul() (6M + 18M = 24M). This might be particularly interesting for multi-pairing as we would multiply the two lines 2-by-2 exploiting full sparsity.

Note: we can save 1M more when multiplying the product of lines by f as the product has always one Fp2 zero, but this is not worth it.

@yelhousni yelhousni changed the base branch from master to develop October 18, 2021 13:49
@gbotrel gbotrel merged commit df9d1b5 into develop Oct 19, 2021
@gbotrel gbotrel deleted the perf/bn254-ML branch October 19, 2021 18:57
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants