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

Modular Square Root (spurious?) failure for FKM12_447 #30

Closed
mratsim opened this issue Jun 4, 2020 · 1 comment · Fixed by #58
Closed

Modular Square Root (spurious?) failure for FKM12_447 #30

mratsim opened this issue Jun 4, 2020 · 1 comment · Fixed by #58
Labels
bug 🪲 Something isn't working has repro 🎯

Comments

@mratsim
Copy link
Owner

mratsim commented Jun 4, 2020

https://travis-ci.com/github/mratsim/constantine/jobs/343752157

image

Random seed for reproduction is 1591293853, as of commit 7c71e65
@mratsim mratsim added the bug 🪲 Something isn't working label Jun 4, 2020
@mratsim mratsim mentioned this issue Jun 4, 2020
Merged
2 tasks
@mratsim mratsim added the heisenbug 🐈 This bug seems random label Jun 7, 2020
@mratsim mratsim mentioned this issue Jun 18, 2020
Closed
@mratsim
Copy link
Owner Author

mratsim commented Jun 19, 2020 •
edited

Minimal reproducing example (with -d:Constantine32):

import  ../constantine/[arithmetic, primitives],
        ../constantine/io/[io_fields],
        ../constantine/config/[curves, common]

var a: Fp[FKM12_447]
a.fromHex("0x406e5e74ee09c84fa0c59f2db3ac814a4937e2f57ecd3c0af4265e04598d643c5b772a6549a2d9b825445c34b8ba100fe8d912e61cfda43d")

a.square()

doAssert: bool a.isSquare()

@mratsim mratsim mentioned this issue Jun 19, 2020
Closed
mratsim added a commit that referenced this issue Jun 20, 2020
@mratsim
Add test case for #30 - Euler's criterion doesn't return 1 for a square
ad3f1a1
This was referenced Jun 20, 2020
Merged
Merged
@mratsim mratsim removed the heisenbug 🐈 This bug seems random label Jun 20, 2020
mratsim added a commit that referenced this issue Jun 20, 2020
@mratsim
Add test case for #30 - Euler's criterion doesn't return 1 for a square
988f6b3
mratsim added a commit that referenced this issue Jun 22, 2020
@mratsim
Fuzzing campaign fixes (#58)
ec76ac5 
* Add test case for #30 - Euler's criterion doesn't return 1 for a square

* Detect #42 in the test suite

* Detect #43 in the test suite

* comment in sqrt tests

* Add #67 to the anti-regression suite

* Add #61 to the anti-regression suite

* Add #62 to anti-regression suite

* Add #60 to the anti-regression suite

* Add #64 to the test suite

* Add #65 - case 1

* Add #65 case 2

* Add #65 case 3

* Add debug check to isSquare/Euler's Criterion/Legendre Symbol

* Make sure our primitives are correct

* For now deactivate montySquare CIOS fix #61 #62

* Narrow down #42 and #43 to powinv on 32-bit

* Detect #42 #43 at the fast squaring level

* More #42, #43 tests, Use multiplication instead of squaring as a temporary workaround, see #68

* Prevent regression of #67 now that squaring is "fixed"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug 🪲 Something isn't working has repro 🎯
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fuzzing campaign fixes mratsim/constantine
1 participant
@mratsim