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  (mod p)

(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)

The general case is "Arithmetic in Fp2" inside the task description

Your example :

Let ω² = -6 , p = 13  ;
Compute (2 + ω)^4  (mod p)

(2 + ω)^2 = (2 + ω) * (2 + ω) = 4 + 2ω + 2ω + ω² = 4 + 4ω - 6 = -2 + 4ω (1)
(2 + ω)^4  = (2 + ω)^2 * (2 + ω)^2      (2)
remplacing (1) in (2)
(2 + ω)^4 = (-2 + 4 ω) ^2
(-2 + 4ω)^2 = 4 - 8ω - 8ω + 16ω² = 4 - 16ω - 96 = -92 - 16ω = -1 - 3ω .

--G.Brougnard (talk) 23:27, 26 March 2016 (UTC)

That is not helpful.

The problem is that we have declared ω is ${\sqrt {-6}}$ and the identity you are using here assumes integer values (or perhaps gaussian integers). But we already know that ω is not an integer. So this step is not a valid step.

Of course, -6 = 7 for our specific example here (in the Fp² domain where we compare all numbers modulo 13), so you could just as easily plug in the square root of seven. But the result here would still be invalid because the square root of seven is still not an integer. --Rdm (talk) 23:45, 26 March 2016 (UTC)

Absolutely right. I forgot to mention it in arithmetic in Fp² . It seemed evident due to the mentioned analogy R/C Fp/Fp² . Nevertheless -1 -3ω seems to be as valid as -1 -3i, even if i has no value in R .--G.Brougnard (talk) 01:12, 27 March 2016 (UTC)

It's a valid value, it's just not equal to -92 - 16ω if ω is not an integer. (And ω is not an integer if ω² is not a square - which the algorithm guarantees.)

So the problem I am left with is: how do I make this algorithm work? It's got this big "magic goes here" specific example that I am somehow supposed to generalize from, but the example itself doesn't make sense. So I have no idea how to make this work.

At this point, I am not even sure if it can be made to work. (In fact, when I look at http://people.math.gatech.edu/~mbaker/pdf/cipolla2011.pdf I see the same kind of mistake, for example on page 3, in computing the fourth power expression.) --Rdm (talk) 01:42, 27 March 2016 (UTC)