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

#ITEM 1- Implement Savas & Koç Montgomery modular inverse algorithm #14

Closed
CPerezz opened this issue May 29, 2019 · 5 comments · Fixed by #26
Closed

#ITEM 1- Implement Savas & Koç Montgomery modular inverse algorithm #14

CPerezz opened this issue May 29, 2019 · 5 comments · Fixed by #26
Assignees
@CPerezz @LukePearson1
Labels
enhancement New feature or request research Need to research about this.

Comments

@CPerezz
Copy link
Contributor

CPerezz commented May 29, 2019 •
edited

This issue is under the item: https://gitlab.dusk.network/dusk-org/tech/issues/1.

The goal is to implement:
Montgomery inversion - Erkay Sava ̧s & Çetin Kaya Koç
J Cryptogr Eng (2018) 8:201–210
https://doi.org/10.1007/s13389-017-0161-x

And benchmark the algo vs. Kalinski's one implemented on #9 .

Addition chais are probably a higher performance solution. Maybe @Bounce23 can bring some light researching a bit.
@CPerezz CPerezz added enhancement New feature or request research Need to research about this. labels May 29, 2019
@LukePearson1
Copy link
Contributor

One thing to bear in mind is that we can use the hardcoded addition chain for the inversion algorithm. The spending for the operations acts as exactly doubling each operation so this can benchmarked against the other two.
The chain template can be found in field.rs of the dalek repo.

@CPerezz
Copy link
Contributor Author

CPerezz commented May 29, 2019

But is it the same? Applies on the same way¿? Or something should be refactored?
I ask that since the prime of the field isn't the same.

PS: You refer to this right?

@LukePearson1
Copy link
Contributor

Yes, you are correct. The need to refactor is why I used the word 'template'.

@CPerezz CPerezz changed the title Implement Savas & Koç Montgomery modular inverse algorithm #ITEM 1- Implement Savas & Koç Montgomery modular inverse algorithm May 29, 2019
This was referenced May 29, 2019
Closed
Closed
CPerezz added a commit to CPerezz/Corretto that referenced this issue Jun 6, 2019
@CPerezz
Comment and stop Kalinski inverse algorithm
22579cb 
Since @Bounce23 said that we could go for an
addition chain algorithm which will enable us
to perform inversion operations in CTime.

So this closes dusk-network#15 dusk-network#17 and dusk-network#14 for now.
@CPerezz
Copy link
Contributor Author

CPerezz commented Jun 6, 2019

As mentioned on last commits this will remain closed until addition chain implementations are found or discarded.

@CPerezz CPerezz closed this as completed Jun 6, 2019
@LukePearson1
Copy link
Contributor

The optimum method of Modular inverse was always this algorithm as using addition chains required defining all of the temporary t value field elements up to and including 2^260.
The tenacity towards a working Kalinsky has paid off as we now have a working implementation of the Kavas and Koç Algorithm for modular inverse. Therefore, this issue can be reopened and the whole modular inverse will be completed in the next 36 hours.

@LukePearson1 LukePearson1 reopened this Jun 13, 2019
CPerezz added a commit to CPerezz/Corretto that referenced this issue Jun 13, 2019
@CPerezz
Implement tests for kalinski_inverse() & doc comments
13b7a28 
This definitely closes: dusk-network#17, dusk-network#15 and #9 and opens the door
for the development of dusk-network#14 .

- Implemented more exhaustive tests for `kalinski_inverse()`
function, which performs the modular inverse of the given
`FieldElement`.

- Added doc comments for `half()` and `plus_p_and_half()`
functions.

- Removed some debugging prints.
@CPerezz CPerezz mentioned this issue Jun 14, 2019
Merged
CPerezz added a commit to CPerezz/Corretto that referenced this issue Jun 14, 2019
@CPerezz
Implement tests for Savas & Koç mod invese
3d92d00 
This closes dusk-network#14 .

Implemented the same test as were implemented
for `kalinski_inverse()`.

All of them passed correctly.
@CPerezz CPerezz mentioned this issue Jun 14, 2019
Merged
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees

@CPerezz CPerezz

@LukePearson1 LukePearson1

Labels
enhancement New feature or request research Need to research about this.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

#ITEM 1- Implement Savas & Koç modular inverse algorithm. CPerezz/Corretto
2 participants
@CPerezz @LukePearson1