Anonymous user
Talk:Cipolla's algorithm: Difference between revisions
m
added tentative explanation
m (added tentative explanation) |
|||
Line 9:
::: 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 ω . --[[User:G.Brougnard|G.Brougnard]] ([[User talk: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? --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 18:31, 26 March 2016 (UTC)
<pre>
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
</pre>
--[[User:G.Brougnard|G.Brougnard]] ([[User talk:G.Brougnard|talk]]) 22:14, 26 March 2016 (UTC)
| |||