Cipolla's algorithm: Difference between revisions
Content added Content deleted
(→{{header|Phix}}: removed bigatom (now deprecated)) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 76: | Line 76: | ||
<br><br> |
<br><br> |
||
=={{header |
=={{header|C sharp|C#}}== |
||
<lang csharp>using System; |
<lang csharp>using System; |
||
using System.Numerics; |
using System.Numerics; |
||
Line 334: | Line 334: | ||
</pre> |
</pre> |
||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
===The function=== |
===The function=== |
||
Line 1,138: | Line 1,139: | ||
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151. |
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151. |
||
</pre> |
</pre> |
||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
Line 1,286: | Line 1,284: | ||
Roots of 665165880 are (475131702, 524868305) mod 1000000007 |
Roots of 665165880 are (475131702, 524868305) mod 1000000007 |
||
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre> |
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre> |
||
=={{header|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|Phix}}== |
=={{header|Phix}}== |
||
Line 1,698: | Line 1,620: | ||
Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039) |
Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039) |
||
Roots of 34035243914635549601583369544560650254325084643201 are (17436881171909637738621006042549786426312886309400,82563118828090362261378993957450213573687113690751) (mod 100000000000000000000000000000000000000000000000151)</pre> |
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}}== |
=={{header|Sage}}== |
||
Line 1,828: | Line 1,827: | ||
}</lang> |
}</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)]. |
{{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}}== |
=={{header|Sidef}}== |
||
{{trans|Go}} |
{{trans|Go}} |