Cipolla's algorithm: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(→{{header|Phix}}: removed bigatom (now deprecated)) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 76:
<br><br>
=={{header
<lang csharp>using System;
using System.Numerics;
Line 334:
</pre>
=={{header|F_Sharp|F#}}==
===The function===
Line 1,138 ⟶ 1,139:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151.
</pre>
=={{header|Kotlin}}==
Line 1,286 ⟶ 1,284:
Roots of 665165880 are (475131702, 524868305) mod 1000000007
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre>
=={{header|Phix}}==
Line 1,698 ⟶ 1,620:
Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039)
Roots of 34035243914635549601583369544560650254325084643201 are (17436881171909637738621006042549786426312886309400,82563118828090362261378993957450213573687113690751) (mod 100000000000000000000000000000000000000000000000151)</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2016.10}}
{{trans|Sidef}}
<lang perl6># Legendre operator (𝑛│𝑝)
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {
when 0 { 0 }
when 1 { 1 }
default { -1 }
}
}
# a coordinate in a Field of p elements
class Fp {
has Int $.x;
has Int $.y;
}
sub cipolla ( Int \𝑛, Int \𝑝 ) {
note "Invalid parameters ({𝑛}, {𝑝})"
and return Nil if (𝑛│𝑝) != 1;
my $ω2;
my $a = 0;
loop {
last if ($ω2 = ($a² - 𝑛) % 𝑝)│𝑝 < 0;
$a++;
}
# define a local multiply operator for Field coordinates
multi sub infix:<*> ( Fp $a, Fp $b ){
Fp.new: :x(($a.x * $b.x + $a.y * $b.y * $ω2) % 𝑝),
:y(($a.x * $b.y + $b.x * $a.y) % 𝑝)
}
my $r = Fp.new: :x(1), :y(0);
my $s = Fp.new: :x($a), :y(1);
for (𝑝+1) +> 1, * +> 1 ... 1 {
$r *= $s if $_ % 2;
$s *= $s;
}
return Nil if $r.y;
$r.x;
}
my @tests = (
(10, 13),
(56, 101),
(8218, 10007),
(8219, 10007),
(331575, 1000003),
(665165880, 1000000007),
(881398088036, 1000000000039),
(34035243914635549601583369544560650254325084643201,
100000000000000000000000000000000000000000000000151)
);
for @tests -> ($n, $p) {
my $r = cipolla($n, $p);
say $r ?? "Roots of $n are ($r, {$p-$r}) mod $p"
!! "No solution for ($n, $p)"
}
</lang>
{{out}}
<pre>Roots of 10 are (6, 7) mod 13
Roots of 56 are (37, 64) mod 101
Roots of 8218 are (9872, 135) mod 10007
Invalid parameters (8219, 10007)
No solution for (8219, 10007)
Roots of 331575 are (855842, 144161) mod 1000003
Roots of 665165880 are (475131702, 524868305) mod 1000000007
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151
</pre>
=={{header|Sage}}==
Line 1,828 ⟶ 1,827:
}</lang>
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/QQBsMza/3 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/NEP5hOWmSBqqpwmF30LpUA Scastie (JVM)].
=={{header|Sidef}}==
{{trans|Go}}
| |||