Talk:Cipolla's algorithm: Difference between revisions

Content added Content deleted

Inline

Revision as of 17:43, 26 March 2016

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)

@@ Line 4: / Line 4: @@
 : 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. --[[User:G.Brougnard|G.Brougnard]] ([[User talk: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.) --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 17:42, 26 March 2016 (UTC)