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