Skip to content

feat: baby-bear and koala-bear extensions of degree 4#643

Merged
gbotrel merged 9 commits intomasterfrom
feat/small-fields-extensions
Feb 19, 2025
Merged

feat: baby-bear and koala-bear extensions of degree 4#643
gbotrel merged 9 commits intomasterfrom
feat/small-fields-extensions

Conversation

@yelhousni
Copy link
Copy Markdown
Collaborator

@yelhousni yelhousni commented Feb 18, 2025

Description

This PR implements the arithmetic of finite field extensions of degree 4 over koala-bear and baby-bear fields. The implementation is a quadratic-over-quadratic tower using Karatsuba routines. The parameters are:

baby-bear:
𝔽r²[u] = 𝔽r/u²-11
𝔽r⁴[v] = 𝔽r²/v²-u

koala-bear:
𝔽r²[u] = 𝔽r/u²-3
𝔽r⁴[v] = 𝔽r²/v²-u

TODO:

  • asm 𝔽r² arithmetic
  • implement direct 𝔽r⁴ extension (should be useful soon for cross-checking with gnark implementation)
  • generify code

Type of change

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

How has this been tested?

All relevant tests implemented.

How has this been benchmarked?

TODO

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

@yelhousni yelhousni marked this pull request as draft February 18, 2025 18:52
@yelhousni yelhousni self-assigned this Feb 18, 2025
@yelhousni yelhousni added this to the v0.10.0 milestone Feb 18, 2025
@yelhousni yelhousni marked this pull request as ready for review February 18, 2025 21:05
@yelhousni yelhousni requested a review from gbotrel February 18, 2025 21:05
@yelhousni yelhousni changed the title feat: koala-bear extension 4 feat: baby-bear and koala-bear extensions of degree 4 Feb 18, 2025
Copy link
Copy Markdown
Collaborator

@gbotrel gbotrel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if we remove the MulBy11 the PR will be cleaner.

Plus of course, need to generify that :)

@yelhousni yelhousni requested a review from gbotrel February 19, 2025 21:47
@gbotrel gbotrel merged commit da49c16 into master Feb 19, 2025
@gbotrel gbotrel deleted the feat/small-fields-extensions branch February 19, 2025 22:14
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants