Timeline for Defining a sign of square roots in GF(p)
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2023 at 1:17 | answer | added | Oleksandr Kulkov | timeline score: 0 | |
| Nov 25, 2023 at 0:59 | vote | accept | Oleksandr Kulkov | ||
| Nov 24, 2023 at 2:34 | answer | added | KConrad | timeline score: 2 | |
| Nov 24, 2023 at 0:41 | comment | added | Oleksandr Kulkov | Yes, of course, positive integers. Edited the question to reflect it more clearly. | |
| Nov 24, 2023 at 0:41 | history | edited | Oleksandr Kulkov | CC BY-SA 4.0 |
added 47 characters in body
|
| Nov 23, 2023 at 22:57 | comment | added | Gerry Myerson | I assume the $a_i$ are all integers, maybe positive integers. | |
| Nov 23, 2023 at 16:07 | comment | added | Aleksei Kulikov | No, I just meant the question of the count (or even existence) in the original problem (over $\mathbb{R}$). | |
| Nov 23, 2023 at 15:34 | comment | added | Oleksandr Kulkov | I'm sorry, I might have misunderstood your comment. By the first question, you mean that even if we know a combination of square roots that gives $0$ modulo $p$, it is still an NP-complete problem to match them back to known integer square roots? Is there a simple proof for it? | |
| Nov 23, 2023 at 15:18 | comment | added | Oleksandr Kulkov | Sure. Still, when $n$ is small, using this allows to solve the problem in $O(2^{n/2})$, even when the integers are very large. | |
| Nov 23, 2023 at 14:55 | comment | added | Aleksei Kulikov | Just a note: the first question is NP-complete even if we know that all $a_k$ are squares (and it's not too hard to reduce the general case to this case). | |
| Nov 23, 2023 at 14:15 | history | edited | LSpice | CC BY-SA 4.0 |
`\DeclareMathOperator`
|
| Nov 23, 2023 at 13:46 | history | asked | Oleksandr Kulkov | CC BY-SA 4.0 |