Talk:Cipolla's algorithm: Difference between revisions

example
(example)
Line 14:
 
Let ω² = -6 , p = 13 , a = 2 ;
Compute (2 + ω)^7 (mod p)
 
(2 + ω)^2 = 4 + 4 ω - 6 = -2 + 4 ω
Line 27:
: 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. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]])
 
:: The general case is "Arithmetic in Fp2" inside the task description
:: Your example :
 
<pre>
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ω .
</pre>
--[[User:G.Brougnard|G.Brougnard]] ([[User talk:G.Brougnard|talk]]) 23:27, 26 March 2016 (UTC)