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

#ITEM 1 - Review Phase 1 of Kalinski's algorithm. #15

Closed
CPerezz opened this issue May 29, 2019 · 5 comments
Closed

#ITEM 1 - Review Phase 1 of Kalinski's algorithm. #15

CPerezz opened this issue May 29, 2019 · 5 comments
Assignees

Comments

@CPerezz
Copy link
Contributor

CPerezz commented May 29, 2019

Since the algorithm implemented on #9 was passing the tests, we thought that Phase I was working correctly.

But while working on #14 we realized the function only works for the tested value surprisingly ..

So now it's time to find the bug that it's affecting Phase I of the Kalinski's algorithm.

@CPerezz CPerezz self-assigned this May 29, 2019
@CPerezz CPerezz added the bug Something isn't working label May 29, 2019
@CPerezz
Copy link
Contributor Author

CPerezz commented May 31, 2019

Phase I is working correctly working now since the tests performed by @Bounce23 and me in 035777b.

But an error has appeared on the Phase II while we perform the addition for rr + p since it should give an even number but gives an odd one.
Due to this. half() function does not do the job correctly since it's dividing odd numbers and the decimals should be rounded, not truncated.
Will open a new issue for it.

@CPerezz
Copy link
Contributor Author

CPerezz commented Jun 6, 2019

Reopened since errors still appearing on the implementation.
They were found on: 638a41f

@LukePearson1 LukePearson1 self-assigned this Jun 6, 2019
@LukePearson1
Copy link
Contributor

Errors are seemingly inexplicable. Alongside this, there is no working example of the Kalinski algorithm, nor any means to contact him. I will build an inversion on double chain addition for use instead. Although this is relatively more difficult than the Algorithm, it WILL work and it provides us with constant time operations, meaning no need for later optimisation in that regard.

CPerezz added a commit to CPerezz/Corretto that referenced this issue Jun 6, 2019
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

LukePearson1 commented Jun 13, 2019

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 Kalinski 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
@LukePearson1 LukePearson1 removed the bug Something isn't working label Jun 13, 2019
CPerezz added a commit to CPerezz/Corretto that referenced this issue Jun 13, 2019
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 closed this as completed Jun 14, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants