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

Add normalization to FpConfig for PartialEq and Eq #800

Open
weikengchen opened this issue Mar 6, 2024 · 3 comments
Open

Add normalization to FpConfig for PartialEq and Eq #800

weikengchen opened this issue Mar 6, 2024 · 3 comments

Comments

@weikengchen
Copy link
Member

weikengchen commented Mar 6, 2024

Some software optimization for special primes uses unnormalized representations. For example, when two numbers are added together, the number does not always be smaller than the modulus. The same can hold for multiplication. In such situations, 1 and p+1 may both be valid results.

FpConfig allows certain level of flexibility.

We can make sure serialization always handles the normalized representation, by implementing the into_bigint in some special way.

But the problem rests on PartialEq and Eq.

Currently, PartialEq and Eq are auto-derived in Fp, which is auto-derived in BigInt as well. It examines the u64 limbs and require each limb to be the same. If we have 1 and p+1, PartialEq and Eq will return negative for them.

To solve this problem, it is advisable to add a method in FpConfig, likely called normalize, which supposedly modify p+1 into 1. Instead of auto-deriving the PartialEq and Eq, we implement them manually with normalize.

@weikengchen
Copy link
Member Author

Related: https://github.com/l2iterative/ark-bn254-r0/blob/main/src/fields/fr.rs

Currently, without this flexibility in FpConfig, one would likely need to implement Fp anew.

@mmagician
Copy link
Member

Sounds reasonable. Plonky2/3 does this for small prime fields, and holds a potentially non-canonical representation.

@Pratyush
Copy link
Member

This is reasonable

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

No branches or pull requests

3 participants