Timeline for Modular square roots problem which is $NP$ hard
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 2, 2023 at 9:32 | history | edited | Thomas Preu | CC BY-SA 4.0 |
added 6 characters in body
|
| Aug 2, 2023 at 9:31 | comment | added | Thomas Preu | @GerryMyerson thank you for pointing out my sloppiness. This seems to make the case where $\alpha$ and $\beta$ have several prime factors in common a lot more complicated. Any useful remarks on this "fixed number of items modular knapsack problem" are appreciated. | |
| Aug 2, 2023 at 9:25 | history | edited | Thomas Preu | CC BY-SA 4.0 |
Corrected a false claim pointed out in the comments and making the claim weaker. Added Euler's criterion for the decision problem.
|
| Aug 2, 2023 at 3:56 | comment | added | Gerry Myerson | "Since the number of square roots modulo a prime power is at most $2$...." $x^2\equiv1\bmod8$ has four solutions. $x^2\equiv0\bmod{p^k}$ has $p^{[k/2]}$ solutions. | |
| Aug 1, 2023 at 17:24 | history | edited | Thomas Preu | CC BY-SA 4.0 |
added 12 characters in body
|
| Aug 1, 2023 at 16:43 | history | answered | Thomas Preu | CC BY-SA 4.0 |