Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
m (→{{header|Sidef}}: code simplifications) |
Thundergnat (talk | contribs) m (→{{header|Perl 6}}: Minor code simplifications, add missing failing test) |
||
Line 410: | Line 410: | ||
<lang perl6># Legendre operator (𝑛│𝑝) |
<lang perl6># Legendre operator (𝑛│𝑝) |
||
sub infix:<│> (Int \𝑛, Int \𝑝 where |
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) { |
||
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) { |
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) { |
||
when 0 { 0 } |
when 0 { 0 } |
||
Line 418: | Line 418: | ||
} |
} |
||
sub tonelli-shanks ( \𝑛, \𝑝 where |
sub tonelli-shanks ( \𝑛, \𝑝 where (𝑛│𝑝) > 0 ) { |
||
my $𝑄 = 𝑝 - 1; |
my $𝑄 = 𝑝 - 1; |
||
my $𝑆 = 0; |
my $𝑆 = 0; |
||
$𝑄 +>= 1 and $𝑆++ while $𝑄 %% 2; |
$𝑄 +>= 1 and $𝑆++ while $𝑄 %% 2; |
||
return 𝑛.expmod((𝑝+1) div 4, 𝑝) if $𝑆 == 1; |
return 𝑛.expmod((𝑝+1) div 4, 𝑝) if $𝑆 == 1; |
||
my $𝑐 = ((2..𝑝).first: (*│𝑝) < 0).expmod($𝑄, 𝑝); |
|||
my $𝑐; |
|||
for 2 .. 𝑝 { |
|||
$𝑐 = .expmod($𝑄, 𝑝) and last if ($_│𝑝) < 0; |
|||
} |
|||
my $𝑅 = 𝑛.expmod( ($𝑄+1) +> 1, 𝑝 ); |
my $𝑅 = 𝑛.expmod( ($𝑄+1) +> 1, 𝑝 ); |
||
my $𝑡 = 𝑛.expmod( $𝑄, 𝑝 ); |
my $𝑡 = 𝑛.expmod( $𝑄, 𝑝 ); |
||
while ($𝑡-1) % 𝑝 { |
|||
my $b; |
my $b; |
||
while (($𝑡-1) % 𝑝) { |
|||
my $𝑡2 = $𝑡² % 𝑝; |
my $𝑡2 = $𝑡² % 𝑝; |
||
for 1 .. $ |
for 1 .. $𝑆 { |
||
if ($𝑡2-1) %% 𝑝 { |
if ($𝑡2-1) %% 𝑝 { |
||
$b = $𝑐.expmod( |
$b = $𝑐.expmod(1 +< ($𝑆-1-$_), 𝑝); |
||
$ |
$𝑆 = $_; |
||
last; |
last; |
||
} |
} |
||
Line 452: | Line 448: | ||
(56, 101), |
(56, 101), |
||
(1030, 10009), |
(1030, 10009), |
||
(1032, 10009), |
|||
(44402, 100049), |
(44402, 100049), |
||
(665820697, 1000000009), |
(665820697, 1000000009), |
||
Line 460: | Line 457: | ||
for @tests -> ($n, $p) { |
for @tests -> ($n, $p) { |
||
my $t = tonelli-shanks($n, $p); |
try my $t = tonelli-shanks($n, $p); |
||
say "No solution for ({$n}, {$p})." and next if !$t or ($t² - $n) % $p; |
|||
say "Roots of $n are ($t, {$p-$t}) mod $p"; |
say "Roots of $n are ($t, {$p-$t}) mod $p"; |
||
}</lang> |
}</lang> |
||
Line 468: | Line 465: | ||
Roots of 56 are (37, 64) mod 101 |
Roots of 56 are (37, 64) mod 101 |
||
Roots of 1030 are (1632, 8377) mod 10009 |
Roots of 1030 are (1632, 8377) mod 10009 |
||
No solution for (1032, 10009). |
|||
Roots of 44402 are (30468, 69581) mod 100049 |
Roots of 44402 are (30468, 69581) mod 100049 |
||
Roots of 665820697 are (378633312, 621366697) mod 1000000009 |
Roots of 665820697 are (378633312, 621366697) mod 1000000009 |