Talk:Cipolla's algorithm
Something seems to be missing here...
We're supposed to solve x² ≡ n (mod p) but step 3 has us solving for ω given ω² in Fp². But if we could solve for ω given ω² in Fp² why do we need this algorithm? --Rdm (talk) 04:34, 26 March 2016 (UTC)
- Precision added to step 3 . The result is x + 0 * ω in Fp2 , that is x in Fp. The 'value' of ω is not needed.Same thing : we do'nt need the 'value' of i when dealing with complex numbers. Thx. --G.Brougnard (talk) 08:56, 26 March 2016 (UTC)
- Ah, now it's Step 2. Let ω² = a² - n. Compute, in Fp2 : (a + ω) ^ ((p + 1)/2) (mod p) where we need to find ω given ω².
- But that does not eliminate the problem of how do we find ω given ω². (Ok, granted, if we had a way of finding a+ω, that would suffice, but I'm not seeing that at the moment -- and if there's an obvious way of finding that value, I think that that should be specified as a part of the algorithm. If not, I imagine that that should be eliminated from the algorithm.) --Rdm (talk) 17:42, 26 March 2016 (UTC)
- You do not have to find a value for ω. This is impossible (since ω² is not a square) and not requested by the task . For example, say ω² = -6 . (3 + ω) ^ 2 = 9 - 6 + 3 ω + 3 ω = 3 + 6 ω . --G.Brougnard (talk) 18:21, 26 March 2016 (UTC)
Copying the Wikipedia example Let ω² = -6 , p = 13 , a = 2 ; Compute (2 + ω)^7 (2 + ω)^2 = 4 + 4 ω - 6 = -2 + 4 ω (2 + ω)^4 = (-2 + 4 ω)^2 = -1 - 3 ω (2 + ω)^6 = (-2 + 4 ω) * ( -1 - 3 ω) = 9 + 2 ω (2 + ω)^7 = (9 + 2 ω) * (2 + ω) = 6 + 0 ω = 6
--G.Brougnard (talk) 22:14, 26 March 2016 (UTC)