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)

So how do I compute (a + ω) ^ ((p + 1)/2) (mod p) in Fp² if finding a value for ω is impossible? --Rdm (talk) 18:31, 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)

I saw that, but how does that work for the general case?

Actually, I am not even sure that that is correct. For example, I cannot prove to myself that -1 - 3ω = (2+ω)^4

But, in any event, there's no algorithm here that I can see, which seems relevant to the general case. --Rdm (talk)