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

Remove Ord, PartialOrd bounds from Field and ProjectiveCurve/AffineCurve traits #226

Closed
Pratyush opened this issue Mar 9, 2021 · 2 comments · Fixed by #246
Closed

Remove Ord, PartialOrd bounds from Field and ProjectiveCurve/AffineCurve traits #226

Pratyush opened this issue Mar 9, 2021 · 2 comments · Fixed by #246

Comments

@Pratyush
Copy link
Member

Pratyush commented Mar 9, 2021

There is no universal ordering on finite field or group elements. This is exemplified right now by the fact that our Fp elements impose a lexicographic ordering by enforcing representatives to be in the range 0..(p-1). However, an equally natural representation would be -(p-1)/2..(p_1)/2, and the ordering on this representation is different from the first one. This is especially problematic for extension fields: is (-1, 1) > (0, 0)?

What should we do here?

@burdges
Copy link
Contributor

burdges commented Mar 9, 2021

There exist many handy trait impls that do not exactly make sense or do not provide exactly the assurances one desires. In this case, I'd just give doc comments on the impls saying /// Arbitrary ordering implemented for `BTreeMap` users and then continuing with exactly what you wrote here.

As an aside, I think HashMap: Clone provides about the best example: We clearly want HashMap: Clone sometimes, but it avoids rehashing by cloning the randomness, which risks DoS attacks. There are two flavors of possible solutions, either add a HashMap::clone_fast method and make HashMap: Clone create new randomness, or else add a clippy lint that suggests iter().collect::<..>() whenever using HashMap: Clone. I'd vote for the clippy lint against HashMap: Clone since so many users do not require DoS protection.

@Pratyush
Copy link
Member Author

That makes sense; I'll add that documentation now.

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 a pull request may close this issue.

2 participants