Skip to content
This repository has been archived by the owner on Nov 9, 2023. It is now read-only.

Implement CT evenness checking using subtle's Choice. #58

Closed
CPerezz opened this issue Jul 15, 2019 · 0 comments · Fixed by #72
Closed

Implement CT evenness checking using subtle's Choice. #58

CPerezz opened this issue Jul 15, 2019 · 0 comments · Fixed by #72
Assignees
Labels
speed_improvement New implementation or changes that speed up existing processes.

Comments

@CPerezz
Copy link
Contributor

CPerezz commented Jul 15, 2019

Since is_even() function calls inside the primitive type u64 is_even() function, it will be faster to take a workaround to enable even faster even numbers checking.ç

The workaround will be something similar to:

Let a be a Scalar or FieldElement which we don't know if it's even or not.

It'll be something similar to:

// Check even by applying an AND logical operator, to see if the last bit of `a` is set
// to `1` or `0`. 
pub fn is_even(&self) -> Choice {
   Choice::from((a[0] & 1u64) as u8)
}

Then, with the result, return a Choice which is a subtle type implemented by Isis Agora Lovecruft and Henry de Valence.

@CPerezz CPerezz self-assigned this Jul 15, 2019
@CPerezz CPerezz added the speed_improvement New implementation or changes that speed up existing processes. label Jul 15, 2019
CPerezz added a commit that referenced this issue Jul 25, 2019
Compare the last bit of the first limb to check evenness.
0b0 -> true
0b1 -> false

This is done in constant time since the op performed
is a logical AND operator with the first limb and
then a comparaison.

This closes #58.
This almost closes #70.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
speed_improvement New implementation or changes that speed up existing processes.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant