Enforce `MAX_DEGREE` and create efficient `X^n` methods

Inversed-Tech / eyelid

Private iris matching

Apache License 2.0

0 stars 0 forks source link

Enforce `MAX_DEGREE` and create efficient `X^n` methods #33

Closed teor2345 closed 3 months ago

teor2345 commented 3 months ago

This PR:

ensures MAX_DEGREE is enforced by:
- reducing after all the possible conversions
- using cyclotomic multiplication for Mul implementations
adds efficient implementations for:
- new X^n
- mul X^n
- div X^n
moves modular reduction to its own module file, so private methods can't accidentally be called

Also:

fixes CI spell check behaviour

Close #13.

teor2345 commented 3 months ago

New tests are causing some failures:

---- primitives::poly::test::mul::test_cyclotomic_mul_rand stdout ---- thread 'primitives::poly::test::mul::test_cyclotomic_mul_rand' panicked at eyelid-match-ops/src/primitives/poly/test/mul.rs:33:19: accessed virtual leading zero coefficient: improve performance by stopping at the highest non-zero coefficient note: run with RUST_BACKTRACE=1 environment variable to display a backtrace

https://github.com/Inversed-Tech/eyelid/actions/runs/8639845243/job/23686846926?pr=33#step:5:18

teor2345 commented 3 months ago

This also means I need to fix the workflows to put the actions variables into the workflow script environment: https://github.com/Inversed-Tech/eyelid/settings/variables/actions

teor2345 commented 3 months ago

Compared to the main branch, this doesn't change performance significantly (as expected): https://github.com/Inversed-Tech/eyelid/actions/runs/8638397766/job/23682757451 https://github.com/Inversed-Tech/eyelid/actions/runs/8654320806/job/23731313961?pr=33