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.

Sign up for GitHub

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

Jump to bottom

Review of ressol #14

Closed
ilyas675 opened this issue Jul 20, 2021 · 3 comments
Closed

Review of ressol #14

ilyas675 opened this issue Jul 20, 2021 · 3 comments
Assignees
@Zerg1996
Labels
bug Something isn't working

Comments

@ilyas675
Copy link
Contributor

Ressol implementation seems to have a bug. Incorrect Shanks-Tonnelli algorithm implementation could be a reason.

Test data:
modulus = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0x6650aa44bf64a7e4a62402a88eed89b9c269af6839db7142cb40bb0b6f558063
expected_a_sqrt = 0xbb53444d14f93d9305e2e4d3e3a76639c20aa9f2a87483c6aba0ffb9bf31e48
produced_a_sqrt = 0xf44acbbb2eb06c26cfa1d1b2c1c5899c63df5560d578b7c39545f003640cdde7
@ilyas675 ilyas675 added the bug Something isn't working label Jul 20, 2021
@ilyas675 ilyas675 self-assigned this Jul 20, 2021
@ilyas675 ilyas675 mentioned this issue Jul 20, 2021
Closed
@ilyas675
Copy link
Contributor Author

Implementation of Shanks-Tonnelli algorithm is correct.

@Zerg1996
Copy link
Contributor

Zerg1996 commented Nov 8, 2021

Think about the correctness of ressol tests.
In some of them p - isn't primary number. Add check of this to tommath::mp_sqrtmod_prime default function and Shanks-Tonnelli gmp implementation or change tests.

@Zerg1996 Zerg1996 reopened this Nov 8, 2021
@Zerg1996 Zerg1996 self-assigned this Nov 8, 2021
@Zerg1996
Copy link
Contributor

Fixed in #8

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Zerg1996 Zerg1996

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@Zerg1996 @ilyas675