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)

If the examples do not make sense, someone has to fix the Wikipedia page. Nevertheless I will publish to-morrow - it is late here :-) - a working solution. It only uses the rules of arithmetic. To make things work, you have to implement Fp2 arithmetic, like complex arithmetic is implemented. A number is a pair (x y) , etc. Remark: Indeed, -1 -3ω = -92 -16ω (mod 13) --G.Brougnard (talk) 02:20, 27 March 2016 (UTC)

Let ω = 2.64575 (in other words: ${\sqrt {7}}$) then -1 - 3ω =(mod 13) 4.06275 however, -92 - 16ω =(mod 13) 8.66798. And, ok, there's a slight precision issue because I've only shown the first six digits of those numbers. But neither that precision issue, nor the mod 13 issue, convinces me that 4.06275 equals 8.66798. --Rdm (talk) 03:11, 27 March 2016 (UTC)

Let a = -1 -3ω , b = -92 -16ω , hence -a = 1 +3ω , then -a + b = -91 -13ω (mod 13). Remarking that -91 - 13ω = 0 + 0ω (mod 13), we have -a + b = 0. This seems to indicate that a = b. But I may be wrong.--G.Brougnard (talk) 08:50, 27 March 2016 (UTC)

That holds true only if ω is an integer (or a gaussian integer), but in this case ω is an irrational number (the square root of a non-square), so you can't use mod 13 on the values you multiply it by. --Rdm (talk) 11:11, 27 March 2016 (UTC)

May be thinking of x + ωy as a pair (x, y) helps. I do'nt know.

There's no problem with the x part of that pair. The problem only shows up when multiplying by a fractional value, which only happens in the y part of that pair.

Anyways, it looks like you won't see any working implementations of this algorithm, just examples with holes in them where the real work happens. --Rdm (talk) 16:31, 27 March 2016 (UTC)

No working implementation ... I agree :-) --G.Brougnard (talk) 17:20, 27 March 2016 (UTC)

Delete this task?

Since this is a bogus algorithm, should we delete this task?

Or should we instead update the main page to state that it's a joke algorithm?