Rosetta Code

Tonelli-Shanks algorithm: Difference between revisions

Page Discussion

Tonelli-Shanks algorithm (view source)

Revision as of 14:49, 14 February 2024

11,360 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
(→‎{{header|C}}: add a new version of tonelli_shanks algorithm)
m (→‎{{header|Wren}}: Minor tidy)
 
(7 intermediate revisions by 4 users not shown)
Line 60:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">F legendre(a, p)
R pow(a, (p - 1) I/ 2, p)
 
Line 104:
assert((r * r - n) % p == 0)
print(‘n = #. p = #.’.format(n, p))
print("\t roots : #. #.".format(r, p - r))</langsyntaxhighlight>
 
{{out}}
Line 126:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang="aarch64 assembly">
<lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/* program tonshan64.s */
Line 568:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
</lang>
{{Output}}
<pre>
Line 582:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang="arm assembly">
<lang ARM Assembly>
/* ARM assembly Raspberry PI or android 32 bits */
/* program tonshan.s */
Line 1,003:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
</lang>
{{Output}}
<pre>
Line 1,017:
=== Version 1 ===
{{trans|C#}}
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
Line 1,118:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>n = 10
Line 1,145:
 
=== Version 2 ===
<syntaxhighlight lang="c">
<lang c>
// return (a * b) % mod, avoiding overflow errors while doing modular multiplication.
static unsigned multiplication_modulo(unsigned a, unsigned b, const unsigned mod) {
Line 1,240:
assert(root == 0); // no solution to the congruence exists.
}
</syntaxhighlight>
</lang>
 
A is assumed odd prime, the algorithm requires O(log A + r * r) multiplications modulo A, where r is the power of 2 dividing A − 1.
Line 1,246:
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Numerics;
Line 1,361:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>n = 10
Line 1,401:
root1 = 32102985369940620849741983987300038903725266634508
root2 = 67897014630059379150258016012699961096274733366069</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <vector>
 
struct Pair {
uint64_t n;
uint64_t p;
};
 
struct Solution {
uint64_t root1;
uint64_t root2;
bool is_square;
};
 
uint64_t multiply_modulus(uint64_t a, uint64_t b, const uint64_t& modulus) {
a %= modulus; b %= modulus;
if ( b < a ) {
uint64_t temp = a; a = b; b = temp;
}
 
uint64_t result = 0;
while ( a > 0 ) {
if ( a % 2 == 1 ) {
result = ( result + b ) % modulus;
};
b = ( b << 1 ) % modulus;
a >>= 1;
}
return result;
}
 
uint64_t power_modulus(uint64_t base, uint64_t exponent, const uint64_t& modulus) {
if ( modulus == 1 ) {
return 0;
}
 
base %= modulus;
uint64_t result = 1;
while ( exponent > 0 ) {
if ( ( exponent & 1 ) == 1 ) {
result = multiply_modulus(result, base, modulus);
}
base = multiply_modulus(base, base, modulus);
exponent >>= 1;
}
return result;
}
 
uint64_t legendre(const uint64_t& a, const uint64_t& p) {
return power_modulus(a, ( p - 1 ) / 2, p);
}
 
Solution tonelli_shanks(const uint64_t& n, const uint64_t& p) {
if ( legendre(n, p) != 1 ) {
return Solution(0, 0, false);
}
 
// Factor out powers of 2 from p - 1
uint64_t q = p - 1;
uint64_t s = 0;
while ( q % 2 == 0 ) {
q /= 2;
s += 1;
}
 
if ( s == 1 ) {
uint64_t result = power_modulus(n, ( p + 1 ) / 4, p);
return Solution(result, p - result, true);
}
 
// Find a non-square z such as ( z | p ) = -1
uint64_t z = 2;
while ( legendre(z, p) != p - 1 ) {
z += 1;
}
 
uint64_t c = power_modulus(z, q, p);
uint64_t t = power_modulus(n, q, p);
uint64_t m = s;
uint64_t result = power_modulus(n, ( q + 1 ) >> 1, p);
 
while ( t != 1 ) {
uint64_t i = 1;
z = multiply_modulus(t, t, p);
while ( z != 1 && i < m - 1 ) {
i += 1;
z = multiply_modulus(z, z, p);
}
uint64_t b = power_modulus(c, 1 << ( m - i - 1 ), p);
c = multiply_modulus(b, b, p);
t = multiply_modulus(t, c, p);
m = i;
result = multiply_modulus(result, b, p);
}
return Solution(result, p - result, true);
}
 
int main() {
const std::vector<Pair> tests = { Pair(10, 13), Pair(56, 101), Pair(1030, 1009), Pair(1032, 1009),
Pair(44402, 100049), Pair(665820697, 1000000009), Pair(881398088036, 1000000000039) };
 
for ( const Pair& test : tests ) {
Solution solution = tonelli_shanks(test.n, test.p);
std::cout << "n = " << test.n << ", p = " << test.p;
if ( solution.is_square == true ) {
std::cout << " has solutions: " << solution.root1 << " and " << solution.root2 << std::endl << std::endl;
} else {
std::cout << " has no solutions because n is not a square modulo p" << std::endl << std::endl;
}
}
}
</syntaxhighlight>
{{ out }}
<pre>
n = 10, p = 13 has solutions: 7 and 6
 
n = 56, p = 101 has solutions: 37 and 64
 
n = 1030, p = 1009 has solutions: 651 and 358
 
n = 1032, p = 1009 has no solutions because n is not a square modulo p
 
n = 44402, p = 100049 has solutions: 30468 and 69581
 
n = 665820697, p = 1000000009 has solutions: 378633312 and 621366697
 
n = 881398088036, p = 1000000000039 has solutions: 791399408049 and 208600591990
</pre>
 
=={{header|Clojure}}==
<langsyntaxhighlight lang="clojure">
(defn find-first
" Finds first element of collection that satisifies predicate function pred "
Line 1,460 ⟶ 1,592:
(println (format "n: %5d p: %d \n\troots: %5d %5d" (biginteger n) (biginteger p) (biginteger r) (biginteger (- p r)))))
 
</syntaxhighlight>
</lang>
{{out}}
n: 10 p: 13
Line 1,479 ⟶ 1,611:
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.bigint;
import std.stdio;
import std.typecons;
Line 1,598 ⟶ 1,730:
}
else writeln("No solution exists");
}</langsyntaxhighlight>
 
{{out}}
Line 1,641 ⟶ 1,773:
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
(require 'bigint)
;; test equality mod p
Line 1,683 ⟶ 1,815:
(mod:≡ t (* t c) p)
(set! m i)))))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,724 ⟶ 1,856:
=={{header|FreeBASIC}}==
===LongInt version===
<langsyntaxhighlight FreeBASIClang="freebasic">' version 11-04-2017
' compile with: fbc -s console
' maximum for p is 17 digits to be on the save side
Line 1,886 ⟶ 2,018:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 1,910 ⟶ 2,042:
===GMP version===
{{libheader|GMP}}
<langsyntaxhighlight lang="freebasic">' version 12-04-2017
' compile with: fbc -s console
 
Line 2,040 ⟶ 2,172:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 2,069 ⟶ 2,201:
===int===
Implementation following Wikipedia, using similar variable names, and using the int type for simplicity.
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 2,145 ⟶ 2,277:
fmt.Println(ts(1032, 10009))
fmt.Println(ts(44402, 100049))
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,156 ⟶ 2,288:
===big.Int===
For the extra credit, we use big.Int from the math/big package of the Go standard library. While the method call syntax is not as easy on the eyes as operator syntax, the package provides modular exponentiation and even the Legendre symbol as the Jacobi function.
<langsyntaxhighlight lang="go">package main
 
import (
Line 2,227 ⟶ 2,359:
fmt.Println(&R1)
fmt.Println(&R2)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,237 ⟶ 2,369:
===Library===
It gets better; the library has a ModSqrt function that uses Tonelli-Shanks internally. Output is same as above.
<langsyntaxhighlight lang="go">package main
 
import (
Line 2,264 ⟶ 2,396:
fmt.Println(&R1)
fmt.Println(&R2)
}</langsyntaxhighlight>
 
=={{header|Haskell}}==
{{trans|Python}}
<langsyntaxhighlight lang="haskell">import Data.List (genericTake, genericLength)
import Data.Bits (shiftR)
 
Line 2,309 ⟶ 2,441:
c' = (b*b) `mod` p
t' = (t*c') `mod` p
in loop i c' r' t'</langsyntaxhighlight>
 
<pre>λ> tonelli 10 13
Line 2,333 ⟶ 2,465:
Implementation:
 
<langsyntaxhighlight Jlang="j">leg=: dyad define
x (y&|)@^ (y-1)%2
)
Line 2,361 ⟶ 2,493:
end.
y|(,-)r
)</langsyntaxhighlight>
 
Task examples:
 
<langsyntaxhighlight Jlang="j"> 10 tosh 13
7 6
56 tosh 101
Line 2,381 ⟶ 2,513:
791399408049 208600591990
41660815127637347468140745042827704103445750172002x tosh (10^50x)+577
32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|9}}
<langsyntaxhighlight Javalang="java">import java.math.BigInteger;
import java.util.List;
import java.util.Map;
Line 2,497 ⟶ 2,629:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>n = 10
Line 2,537 ⟶ 2,669:
root1 = 32102985369940620849741983987300038903725266634508
root2 = 67897014630059379150258016012699961096274733366069</pre>
 
=={{header|jq}}==
'''Works with gojq and fq, two Go implementations of jq'''
 
'''Adapted from [[#Wren|Wren]]'''
 
The Go implementations of jq provide indefinite-precision integer
arithmetic.
 
See [[Modular_exponentiation]] for suitable jq definitions of `power/1` and `modPow/2` as used here.
<syntaxhighlight lang=jq>
include "rc-modular-exponentiation"; # see remark above
 
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
def idivide($j):
. as $i
| ($i % $j) as $mod
| ($i - $mod) / $j ;
 
def Solution(a;b;c):
{"root1": a, "root2": b, "exists": c};
 
# pretty print a Solution
def pp:
if .exists
then "root1 = \(.root1)",
"root2 = \(.root2)"
else "No solution exists"
end;
 
# Tonelli-Shanks
def ts($n; $p):
def powModP($a; $e): $a | modPow($e; $p);
 
def ls($a): powModP($a; ($p - 1) | idivide(2));
 
if ls($n) != 1 then Solution(0; 0; false)
else { q: ($p - 1), ss: 0}
| until (.q % 2 != 0;
.ss += 1
| .q |= idivide(2) )
| if .ss == 1
then powModP(n; ($p+1) | idivide(4)) as $r1
| Solution($r1; $p - $r1; true)
else .z = 2
| until ( ls(.z) == ($p - 1); .z += 1 )
| .c = powModP(.z; .q)
| .r = powModP($n; (.q+1) | idivide(2))
| .t = powModP($n; .q)
| .m = .ss
| until (.emit;
if .t == 1 then .emit = Solution(.r; $p - .r; true)
else .i = 0
| .zz = .t
| until (.zz == 1 or .i >= (.m - 1);
.zz = (.zz * .zz) % p
| .i += 1 )
| .b = .c
| .e = .m - (1 + .i)
| until (.e <= 0;
.b = (.b * .b) % $p
| .e += -1 )
| .r = (.r * .b) % $p
| .c = (.b * .b) % $p
| .t = (.t * .c) % $p
| .m = .i
end )
| .emit
end
end;
def pairs: [
[10, 13], [56, 101], [1030, 10009], [1032, 10009], [44402, 100049],
[665820697, 1000000009], [881398088036, 1000000000039]
];
 
def task:
pairs[] as [$n, $p]
| ts($n; $p) as $sol
| "n = \($n)",
"p = \($p)",
($sol | pp),
"";
 
def task2:
def bn: 41660815127637347468140745042827704103445750172002;
def bp: (10 | power(50)) + 577;
ts(bn; bp) as $bsol
| "n = \(bn)",
"p = \(bp)",
( $bsol | pp );
 
task, task2
</syntaxhighlight>
{{output}}
See [[#Wren|Wren]].
 
=={{header|Julia}}==
Line 2,542 ⟶ 2,772:
 
'''Module''':
<langsyntaxhighlight lang="julia">module TonelliShanks
 
legendre(a, p) = powermod(a, (p - 1) ÷ 2, p)
Line 2,583 ⟶ 2,813:
end
 
end # module TonelliShanks</langsyntaxhighlight>
 
'''Main''':
<langsyntaxhighlight lang="julia">@show TonelliShanks.solve(10, 13)
@show TonelliShanks.solve(56, 101)
@show TonelliShanks.solve(1030, 10009)
Line 2,592 ⟶ 2,822:
@show TonelliShanks.solve(665820697, 1000000009)
@show TonelliShanks.solve(881398088036, 1000000000039)
@show TonelliShanks.solve(41660815127637347468140745042827704103445750172002, big"10" ^ 50 + 577)</langsyntaxhighlight>
 
{{out}}
Line 2,605 ⟶ 2,835:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
import java.math.BigInteger
Line 2,700 ⟶ 2,930:
}
else println("No solution exists")
}</langsyntaxhighlight>
 
{{out}}
Line 2,748 ⟶ 2,978:
Based algorithm pseudo-code, referencing python 3.
 
<langsyntaxhighlight Nimlang="nim">proc pow*[T: SomeInteger](x, n, p: T): T =
var t = x mod p
var e = n
Line 2,812 ⟶ 3,042:
run(1032, 10009)
run(44402, 100049)
run(665820697, 1000000009)</langsyntaxhighlight>
 
output:
Line 2,826 ⟶ 3,056:
{{libheader|zarith}}
An extra test case has been added for the `s = 1` branch.
<langsyntaxhighlight lang="ocaml">let tonelli n p =
let open Z in
let two = ~$2 in
Line 2,887 ⟶ 3,117:
(to_string r2)
| None -> print_endline "No solution exists\n")
</syntaxhighlight>
</lang>
 
{{out}}
Line 2,940 ⟶ 3,170:
{{trans|Raku}}
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use bigint;
use ntheory qw(is_prime powmod kronecker);
 
Line 2,997 ⟶ 3,227:
printf "Roots of %d are (%d, %d) mod %d\n", $n, $t, $p-$t, $p;
}
}</langsyntaxhighlight>
{{out}}
<pre>Roots of 10 are (7, 6) mod 13
Line 3,010 ⟶ 3,240:
{{trans|C#}}
{{libheader|Phix/mpfr}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 3,090 ⟶ 3,320:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"For n = %s and p = %s, %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 3,106 ⟶ 3,336:
=={{header|PicoLisp}}==
{{trans|Go}}
<langsyntaxhighlight PicoLisplang="picolisp"># from @lib/rsa.l
(de **Mod (X Y N)
(let M 1
Line 3,173 ⟶ 3,403:
(println (ts 665820697 1000000009))
(println (ts 881398088036 1000000000039))
(println (ts 41660815127637347468140745042827704103445750172002 (+ (** 10 50) 577)))</langsyntaxhighlight>
 
{{out}}
Line 3,185 ⟶ 3,415:
(791399408049 208600591990)
(32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069)
</pre>
 
=={{header|Powershell}}==
{{trans|Python}}
{{works with|Powershell|7}}
<syntaxhighlight lang="powershell">Function Invoke-ModuloExponentiation ([BigInt]$Base, [BigInt]$Exponent, $Modulo) {
$Result = 1
$Base = $Base % $Modulo
If ($Base -eq 0) {return 0}
While ($Exponent -gt 0) {
If (($Exponent -band 1) -eq 1) {$Result = ($Result * $Base) % $Modulo}
$Exponent = $Exponent -shr 1
$Base = ($Base * $Base) % $Modulo
}
return ($Result % $Modulo)
}
 
Function Get-Legendre ([BigInt]$Integer, [BigInt]$Prime) {
return (Invoke-ModuloExponentiation -Base $Integer -Exponent (($Prime - 1) / 2) -Modulo $Prime)
}
 
Function Invoke-TonelliShanks ([BigInt]$Integer, [BigInt]$Prime) {
If ((Get-Legendre $Integer $Prime) -ne 1) {throw "$Integer not a square (mod $Prime)"}
[bigint]$q = $Prime - 1
$s = 0
While (($q % 2) -eq 0) {
$q = $q / 2
$s++
}
If ($s -eq 1) {
return (Invoke-ModuloExponentiation $Integer -Exponent (($Prime + 1) / 4) -Modulo $Prime)
}
For ($z = 2; [Bigint]::Compare($z, $Prime) -lt 0; $z++) {
If ([BigInt]::Compare(($Prime - 1), (Get-Legendre $z $Prime)) -eq 0) {
break
}
}
$c = Invoke-ModuloExponentiation -Base $z -Exponent $q -Modulo $Prime
$r = Invoke-ModuloExponentiation -Base $Integer -Exponent (($q + 1) / 2) -Modulo $Prime
$t = Invoke-ModuloExponentiation -Base $Integer -Exponent $q -Modulo $Prime
$m = $s
$t2 = 0
While ((($t - 1) % $Prime) -ne 0) {
$t2 = $t * $t % $Prime
Foreach ($i in (1..$m)) {
If ((($t2 -1) % $Prime) -eq 0) {
break
}
$t2 = Invoke-ModuloExponentiation -Base $t2 -Exponent 2 -Modulo $Prime
}
$b = Invoke-ModuloExponentiation -Base $c -Exponent ([Math]::Pow(2, ($m - $i - 1))) -Modulo $Prime
$r = ($r * $b) % $Prime
$c = ($b * $b) % $Prime
$t = ($t * $c) % $Prime
$m = $i
}
return $r
}
 
$TonelliTests = @(
@{Integer = [BigInt]::Parse('10'); Prime = [BigInt]::Parse('13')},
@{Integer = [BigInt]::Parse('56'); Prime = [BigInt]::Parse('101')},
@{Integer = [BigInt]::Parse('1030'); Prime = [BigInt]::Parse('10009')},
@{Integer = [BigInt]::Parse('44402'); Prime = [BigInt]::Parse('100049')},
@{Integer = [BigInt]::Parse('665820697'); Prime = [BigInt]::Parse('1000000009')},
@{Integer = [BigInt]::Parse('881398088036'); Prime = [BigInt]::Parse('1000000000039')},
@{Integer = [BigInt]::Parse('41660815127637347468140745042827704103445750172002'); Prime = [BigInt]::Parse('100000000000000000000000000000000000000000000000577')}
)
 
$TonelliTests | Foreach-Object {
$Result = Invoke-TonelliShanks @_
[PSCustomObject]@{
n = $_['Integer']
p = $_['Prime']
Roots = @($Result, ($_['Prime'] - $Result))
}
} | Format-List</syntaxhighlight>
 
{{out}}
<pre>
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
 
n : 41660815127637347468140745042827704103445750172002
p : 100000000000000000000000000000000000000000000000577
Roots : {32102985369940620849741983987300038903725266634508, 67897014630059379150258016012699961096274733366069}
</pre>
 
Line 3,190 ⟶ 3,529:
{{trans|EchoLisp}}
{{works with|Python|3}}
<langsyntaxhighlight lang="python">def legendre(a, p):
return pow(a, (p - 1) // 2, p)
 
Line 3,231 ⟶ 3,570:
assert (r * r - n) % p == 0
print("n = %d p = %d" % (n, p))
print("\t roots : %d %d" % (r, p - r))</langsyntaxhighlight>
{{out}}
<pre>
Line 3,252 ⟶ 3,591:
=={{header|Racket}}==
{{trans|EchoLisp}}
<langsyntaxhighlight lang="racket">#lang racket
 
(require math/number-theory)
Line 3,311 ⟶ 3,650:
(task ttest)
 
(check-exn exn:fail? (λ () (Tonelli 1032 1009))))</langsyntaxhighlight>
 
{{out}}
Line 3,335 ⟶ 3,674:
Translation of the Wikipedia pseudocode, heavily influenced by Sidef and Python.
 
<syntaxhighlight lang="raku" perl6line># Legendre operator (𝑛│𝑝)
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {
Line 3,386 ⟶ 3,725:
say "No solution for ({$n}, {$p})." and next if !$t or ($t² - $n) % $p;
say "Roots of $n are ($t, {$p-$t}) mod $p";
}</langsyntaxhighlight>
 
{{out}}
Line 3,401 ⟶ 3,740:
{{trans|Python}}
The large numbers cannot reasonably be handled by the pow function shown here.
<langsyntaxhighlight lang="rexx">/* REXX (required by some interpreters) */
Numeric Digits 1000000
ttest ='[(10, 13), (56, 101), (1030, 10009), (44402, 100049)]'
Line 3,458 ⟶ 3,797:
If z>'' Then
p=p//z
Return p</langsyntaxhighlight>
{{out}}
<pre>n = 10 p = 13
Line 3,471 ⟶ 3,810:
=={{header|Sidef}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">func tonelli(n, p) {
legendre(n, p) == 1 || die "not a square (mod p)"
var q = p-1
Line 3,510 ⟶ 3,849:
assert((r*r - n) % p == 0)
say "Roots of #{n} are (#{r}, #{p-r}) mod #{p}"
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,524 ⟶ 3,863:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
 
Module Module1
Line 3,638 ⟶ 3,977:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>n = 10
Line 3,683 ⟶ 4,022:
{{libheader|Wren-dynamic}}
{{libheader|Wren-big}}
<langsyntaxhighlight ecmascriptlang="wren">import "./dynamic" for Tuple
import "./big" for BigInt
 
var Solution = Tuple.create("Solution", ["root1", "root2", "exists"])
Line 3,764 ⟶ 4,103:
} else {
System.print("No solution exists")
}</langsyntaxhighlight>
 
{{out}}
Line 3,810 ⟶ 4,149:
=={{header|zkl}}==
{{trans|EchoLisp}}
<langsyntaxhighlight lang="zkl">var BN=Import("zklBigNum");
fcn modEq(a,b,p) { (a-b)%p==0 }
fcn legendre(a,p){ a.powm((p - 1)/2,p) }
Line 3,828 ⟶ 4,167:
}
r
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">ttest:=T(T(10,13), T(56,101), T(1030,10009), T(44402,100049),
T(665820697,1000000009), T(881398088036,1000000000039),
T("41660815127637347468140745042827704103445750172002", BN(10).pow(50) + 577),
Line 3,838 ⟶ 4,177:
println("n=%d p=%d".fmt(n,p));
println(" roots: %d %d".fmt(r, p-r));
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/266689...352961"