Cipolla's algorithm: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (Phix/mpfr) |
m (→{{header|Wren}}: Minor tidy) |
||
(15 intermediate revisions by 11 users not shown) | |||
Line 75:
* [[Tonelli-Shanks algorithm]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F convertToBase(n, b)
I (n < 2)
R [n]
V temp = n
V ans = [Int]()
L (temp != 0)
ans = [temp % b] [+] ans
temp I/= b
R ans
F cipolla(=n, p)
n %= p
I (n == 0 | n == 1)
R [n, (p - n) % p]
V phi = p - 1
I (pow(BigInt(n), phi I/ 2, p) != 1)
R [Int]()
I (p % 4 == 3)
V ans = Int(pow(BigInt(n), (p + 1) I/ 4, p))
R [ans, (p - ans) % p]
V aa = 0
L(i) 1 .< p
V temp = pow(BigInt((i * i - n) % p), phi I/ 2, p)
I (temp == phi)
aa = i
L.break
V exponent = convertToBase((p + 1) I/ 2, 2)
F cipollaMult(ab, cd, w, p)
V (a, b) = ab
V (c, d) = cd
R ((a * c + b * d * w) % p, (a * d + b * c) % p)
V x1 = (aa, 1)
V x2 = cipollaMult(x1, x1, aa * aa - n, p)
L(i) 1 .< exponent.len
I (exponent[i] == 0)
x2 = cipollaMult(x2, x1, aa * aa - n, p)
x1 = cipollaMult(x1, x1, aa * aa - n, p)
E
x1 = cipollaMult(x1, x2, aa * aa - n, p)
x2 = cipollaMult(x2, x2, aa * aa - n, p)
R [x1[0], (p - x1[0]) % p]
print(‘Roots of 2 mod 7: ’cipolla(2, 7))
print(‘Roots of 8218 mod 10007: ’cipolla(8218, 10007))
print(‘Roots of 56 mod 101: ’cipolla(56, 101))
print(‘Roots of 1 mod 11: ’cipolla(1, 11))
print(‘Roots of 8219 mod 10007: ’cipolla(8219, 10007))</syntaxhighlight>
{{out}}
<pre>
Roots of 2 mod 7: [4, 3]
Roots of 8218 mod 10007: [9872, 135]
Roots of 56 mod 101: [37, 64]
Roots of 1 mod 11: [1, 10]
Roots of 8219 mod 10007: []
</pre>
=={{header|C}}==
{{trans|FreeBasic}}
<
#include <stdint.h>
#include <stdio.h>
Line 267 ⟶ 325:
return 0;
}</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 286 ⟶ 344:
Find solution for n = 665165880 and p = 1000000007
Solution found: x1 = 524868305, x2 = 475131702</pre>
=={{header|C sharp|C#}}==
<
using System.Numerics;
Line 364 ⟶ 421:
}
}
}</
{{out}}
<pre>(6, 7, True)
Line 374 ⟶ 431:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
import std.typecons;
Line 460 ⟶ 516:
writeln(c("881398088036", "1000000000039"));
writeln(c("34035243914635549601583369544560650254325084643201", ""));
}</
{{out}}
<pre>Tuple!(BigInt, "x", BigInt, "y", bool, "b")(6, 7, true)
Line 470 ⟶ 526:
Tuple!(BigInt, "x", BigInt, "y", bool, "b")(791399408049, 208600591990, true)
Tuple!(BigInt, "x", BigInt, "y", bool, "b")(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>
=={{header|EchoLisp}}==
<
(lib 'struct)
(lib 'types)
Line 524 ⟶ 579:
(assert (mod= n (* x x) p)) ;; checking the result
(printf "Roots of %d are (%d,%d) (mod %d)" n x (% (- p x) p) p))
</syntaxhighlight>
{{out}}
<pre>
Line 545 ⟶ 600:
</pre>
=={{header|F_Sharp|F#}}==
===The function===
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<
// Cipolla's algorithm. Nigel Galloway: June 16th., 2019
let Cipolla n g =
Line 561 ⟶ 615:
|_->let n,i=Seq.item α fE in ((Πn*n+Πi*i*b)%g)
if fN 1I n ((g-1I)/2I) g<>1I then None else Some(fL 1I 0I 0 ((g+1I)/2I))
</syntaxhighlight>
===The Task===
<
let test=[(10I,13I);(56I,101I);(8218I,10007I);(8219I,10007I);(331575I,1000003I);(665165880I,1000000007I);(881398088036I,1000000000039I);(34035243914635549601583369544560650254325084643201I,10I**50+151I)]
test|>List.iter(fun(n,g)->match Cipolla n g with Some r->printfn "Cipolla %A %A -> %A (%A) check %A" n g r (g-r) ((r*r)%g) |_->printfn "Cipolla %A %A -> has no result" n g)
</syntaxhighlight>
{{out}}
<pre>
Line 579 ⟶ 633:
Real: 00:00:00.089, CPU: 00:00:00.090, GC gen0: 2, gen1: 0
</pre>
=={{header|Factor}}==
{{trans|Sidef}}
{{works with|Factor|0.99 2020-08-14}}
<syntaxhighlight lang="factor">USING: accessors assocs interpolate io kernel literals locals
math math.extras math.functions ;
TUPLE: point x y ;
C: <point> point
:: (cipolla) ( n p -- m )
0 0 :> ( a! ω2! )
[ ω2 p legendere -1 = ]
[ a sq n - p rem ω2! a 1 + a! ] do until a 1 - a!
[| a b |
a x>> b x>> * a y>> b y>> ω2 * * + p mod
a x>> b y>> * b x>> a y>> * + p mod <point>
] :> [mul]
1 0 <point> :> r!
a 1 <point> :> s!
p 1 + -1 shift :> n!
[ n 0 > ] [
n odd? [ r s [mul] call r! ] when
s s [mul] call s!
n -1 shift n!
] while
r y>> zero? r x>> f ? ;
: cipolla ( n p -- m/f )
2dup legendere 1 = [ (cipolla) ] [ 2drop f ] if ;
! Task
{
{ 10 13 }
{ 56 101 }
{ 8218 10007 }
{ 8219 10007 }
{ 331575 1000003 }
{ 665165880 1000000007 }
{ 881398088036 1000000000039 }
${
34035243914635549601583369544560650254325084643201
10 50 ^ 151 +
}
}
[
2dup cipolla
[ 2dup - [I Roots of ${3} are (${1} ${0}) mod ${2}I] ]
[ [I No solution for (${}, ${})I] ] if* nl
] assoc-each</syntaxhighlight>
{{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
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|FreeBASIC}}==
===LongInt version===
Had a close look at the EchoLisp code for step 2.
Used the FreeBASIC code from the Miller-Rabin task for prime testing.
<
' compile with: fbc -s console
' maximum for p is 17 digits to be on the save side
Line 770 ⟶ 888:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 794 ⟶ 912:
===GMP version===
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 941 ⟶ 1,059:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 966 ⟶ 1,084:
Find solution for n = 34035243914635549601583369544560650254325084643201 and p = 10^50 + 151
Solution found: x1 = 17436881171909637738621006042549786426312886309400, x2 = 82563118828090362261378993957450213573687113690751</pre>
=={{header|Go}}==
===int===
Implementation following the pseudocode in the task description.
<
import "fmt"
Line 1,032 ⟶ 1,149:
fmt.Println(c(8219, 10007))
fmt.Println(c(331575, 1000003))
}</
{{out}}
<pre>
Line 1,043 ⟶ 1,160:
===big.Int===
Extra credit:
<
import (
Line 1,102 ⟶ 1,219:
fmt.Println(&R1)
fmt.Println(&R2)
}</
{{out}}
<pre>
Line 1,110 ⟶ 1,227:
17436881171909637738621006042549786426312886309400
</pre>
=={{header|J}}==
Based on the echolisp implementation:
<
x (y&|)@^ (y-1)%2
)
Line 1,148 ⟶ 1,264:
assert. 'not a valid square root'
end.
)</
Task examples:
<
6 7
56 cipolla 101
Line 1,168 ⟶ 1,284:
208600591990 791399408049
34035243914635549601583369544560650254325084643201x cipolla (10^50x) + 151
17436881171909637738621006042549786426312886309400 82563118828090362261378993957450213573687113690751</
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|8}}
<
import java.util.function.BiFunction;
import java.util.function.Function;
Line 1,280 ⟶ 1,395:
System.out.println(c("34035243914635549601583369544560650254325084643201", ""));
}
}</
{{out}}
<pre>(6, 7, true)
Line 1,290 ⟶ 1,405:
(791399408049, 208600591990, true)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>
=={{header|jq}}==
{{trans|Wren}}
'''Works with gojq, the Go implementation of jq'''
A Point is represented by a numeric array of length two (i.e. [x,y]).
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
# 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 bigBig: (10|power(50)) + 151;
# The remainder when $b raised to the power $e is divided by $m:
def modPow($b; $e; $m):
if ($m == 1) then 0
else {r: 1, b: ($b % $m), $e}
| until (.e <= 0;
if (.e % 2) == 1 then .r = (.r*.b) % $m else . end
| .e |= idivide(2)
| .b |= ((.*.) % $m) )
| .r
end;
def c($ns; $ps):
$ns as $n
| (if $ps != "" then $ps else bigBig end) as $p
# Legendre symbol, returns 1, 0 or p - 1
| def ls($a): modPow($a; ($p - 1) | idivide(2); $p);
# multiplication in Fp2 where .omega2 comes from .
def mul($aa; $bb):
[($aa[0] * $bb[0] + $aa[1] * $bb[1] * .omega2) % $p,
($aa[0] * $bb[1] + $bb[0] * $aa[1]) % $p] ;
# Step 0, validate arguments
if (ls($n) != 1) then [0, 0, false]
else
# Step 1, find a, omega2
{ a: 0, stop: false }
| until( .stop;
.omega2 = ((.a * .a + $p - $n) % $p)
| if ls(.omega2) == ($p - 1)
then .stop = true
else .a += 1
end )
# Step 2, compute power
| { r: [1, 0],
s: [.a, 1],
nn: (( ($p + 1) | idivide(2)) % $p),
omega2 }
| until (.nn <= 0;
if (.nn % 2) == 1 then .r = mul(.r; .s) else . end
| .s = mul(.s; .s)
| .nn |= idivide(2) )
# Step 3, check x in Fp; or that x * x = n
| if (.r[1] != 0) or ((.r[0] * .r[0]) % $p != $n) then [0, 0, false]
# Step 4, solutions
else [.r[0], $p - .r[0], true]
end
end;
def exercise:
c(10; 13),
c(56; 101),
c(8218; 10007),
c(8219; 10007),
c(331575; 1000003),
c(665165880; 1000000007),
c(881398088036; 1000000000039),
c(34035243914635549601583369544560650254325084643201; "")
;
exercise</syntaxhighlight>
{{out}}
<pre>
[6,7,true]
[37,64,true]
[9872,135,true]
[0,0,false]
[855842,144161,true]
[475131702,524868305,true]
[791399408049,208600591990,true]
[82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,true]
</pre>
=={{header|Julia}}==
{{trans|Perl}}
<
function legendre(n, p)
Line 1,339 ⟶ 1,547:
println(r > 0 ? "Roots of $n are ($r, $(p - r)) mod $p." : "No solution for ($n, $p)")
end
</
<pre>
Roots of 10 are (6, 7) mod 13.
Line 1,350 ⟶ 1,558:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151.
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 1,419 ⟶ 1,626:
println(c("881398088036", "1000000000039"))
println(c("34035243914635549601583369544560650254325084643201", ""))
}</
{{out}}
Line 1,432 ⟶ 1,639:
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Cipolla]
Cipolla[n_, p_] := Module[{ls, omega2, nn, a, r, s},
ls = JacobiSymbol[n, p];
If[ls != 1,
{0, 0, False}
,
a = 0;
While[True,
omega2 = Mod[a^2 + p - n, p];
If[JacobiSymbol[omega2, p] == -1, Break[]];
a++
];
ClearAll[Mul];
Mul[{ax_, ay_}, {bx_, by_}] :=
Mod[{ax bx + ay by omega2, ax by + bx ay}, p];
r = {1, 0};
s = {a, 1};
nn = Mod[BitShiftRight[p + 1, 1], p];
While[nn > 0,
If[BitAnd[nn, 1] == 1,
r = Mul[r, s]
];
s = Mul[s, s];
nn = BitShiftRight[nn, 1];
];
If[r[[2]] != 0, Return[{0, 0, False}]];
If[Mod[r[[1]]^2, p] != n, Return[{0, 0, False}]];
Return[{r[[1]], p - r[[1]], True}]
]
]
Cipolla[10, 13]
Cipolla[56, 101]
Cipolla[8218, 10007]
Cipolla[8219, 10007]
Cipolla[331575, 1000003]
Cipolla[665165880, 1000000007]
Cipolla[881398088036, 1000000000039]
Cipolla[34035243914635549601583369544560650254325084643201, 10^50 + 151]</syntaxhighlight>
{{out}}
<pre>{6,7,True}
{37,64,True}
{9872,135,True}
{0,0,False}
{855842,144161,True}
{475131702,524868305,True}
{791399408049,208600591990,True}
{82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,True}</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<syntaxhighlight lang="nim">import options
import bignum
let
Zero = newInt(0)
One = newInt(1)
BigBig = newInt(10)^50 + 15
type
Point = tuple[x, y: Int]
Solutions = (Int, Int)
proc exp(x, y, m: Int): Int =
## Missing function in "bignum" module.
if m == 1: return Zero
result = newInt(1)
var x = x mod m
var y = y.clone
while not y.isZero:
if y mod 2 == 1:
result = result * x mod m
y = y shr 1
x = x * x mod m
proc c(ns, ps: string): Option[Solutions] =
let n = newInt(ns)
let p = if ps.len != 0: newInt(ps) else: BigBig
# Legendre symbol: returns 1, 0 or p - 1.
proc ls(a: Int): Int = a.exp((p - 1) div 2, p)
# Step 0, validate arguments.
if ls(n) != One: return none(Solutions)
# Step 1, find a, omega2.
var a = newInt(0)
var omega2: Int
while true:
omega2 = (a * a + p - n) mod p
if ls(omega2) == p - 1: break
a += 1
# Multiplication in Fp2.
proc `*`(a, b: Point): Point =
((a.x * b.x + a.y * b.y * omega2) mod p,
(a.x * b.y + b.x * a.y) mod p)
# Step 2, compute power.
var
r: Point = (One, Zero)
s: Point = (a, One)
nn = ((p + 1) shr 1) mod p
while not nn.isZero:
if (nn and One) == One: r = r * s
s = s * s
nn = nn shr 1
# Step 3, check x in Fp.
if not r.y.isZero: return none(Solutions)
# Step 5, check x * x = n.
if r.x * r.x mod p != n: return none(Solutions)
# Step 4, solutions.
result = some((r.x, p - r.x))
when isMainModule:
const Values = [("10", "13"), ("56", "101"), ("8218", "10007"),
("8219", "10007"), ("331575", "1000003"),
("665165880", "1000000007"), ("881398088036", "1000000000039"),
("34035243914635549601583369544560650254325084643201", "")]
for (n, p) in Values:
let sols = c(n, p)
if sols.isSome: echo sols.get()
else: echo "No solutions."</syntaxhighlight>
{{out}}
<pre>(6, 7)
(37, 64)
(9872, 135)
No solutions.
(855842, 144161)
(475131702, 524868305)
(791399408049, 208600591990)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400)</pre>
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use ntheory qw(is_prime);
Line 1,486 ⟶ 1,834:
$r ? printf "Roots of %d are (%d, %d) mod %d\n", $n, $r, $p-$r, $p
: print "No solution for ($n, $p)\n"
}</
{{out}}
<pre>Roots of 10 are (6, 7) mod 13
Line 1,495 ⟶ 1,843:
Roots of 665165880 are (475131702, 524868305) mod 1000000007
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre>
=={{header|Phix}}==
{{trans|Kotlin}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang="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>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">legendre</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Legendre symbol, returns 1, 0 or p - 1 (in r)</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mul_point</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">omega2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (modifies a)</span>
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">xa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ya</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">xb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yb</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">xaxb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">yayb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">xayb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">xbya</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xb</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ya</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yb</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yb</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xbya</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ya</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omega2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xa</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- xa := mod(xaxb+yayb*omega2,p)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xbya</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ya</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ya := mod(xayb+xbya,p)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xbya</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">xaxb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xayb</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xbya</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cipolla</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">no</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">po</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">no</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">po</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- Step 0, validate arguments</span>
<span style="color: #000000;">legendre</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"false"</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- Step 1, find a, omega2</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">omega2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">pm1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_sub_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">*</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">omega2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">legendre</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omega2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pm1</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- Step 2, compute power</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)},</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)}</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">nn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_fdiv_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mul_point</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omega2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">mul_point</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omega2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_fdiv_q_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- Step 3, check x in Fp</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"false"</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- Step 5, check x * x = n</span>
<span style="color: #7060A8;">mpz_powm_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"false"</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000080;font-style:italic;">-- Step 4, solutions</span>
<span style="color: #7060A8;">mpz_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">),</span> <span style="color: #008000;">"true"</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">13</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">56</span><span style="color: #0000FF;">,</span><span style="color: #000000;">101</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">8218</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10007</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">8219</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10007</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">331575</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1000003</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">665165880</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1000000007</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"881398088036"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1000000000039"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"34035243914635549601583369544560650254325084643201"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"100000000000000000000000000000000000000000000000151"</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cipolla</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
Obviously were you to use that in anger, you would probably rip out a few mpz_get_str() and return NULL/false rather than "0"/"false", etc.
{{out}}
Line 1,605 ⟶ 1,955:
{"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}
</pre>
=={{header|PicoLisp}}==
{{trans|Go}}
<
(de **Mod (X Y N)
(let M 1
Line 1,668 ⟶ 2,017:
(println (ci 665165880 1000000007))
(println (ci 881398088036 1000000000039))
(println (ci 34035243914635549601583369544560650254325084643201 (+ (** 10 50) 151)))</
{{out}}
<pre>
Line 1,680 ⟶ 2,029:
(82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400)
</pre>
=={{header|Python}}==
<
#Converts n to base b as a list of integers between 0 and b-1
#Most-significant digit on the left
Line 1,728 ⟶ 2,076:
return (x1[0],-x1[0]%p)
print
print
print
print
print
</syntaxhighlight>
{{out}}
<pre>
Roots of 2 mod 7: (4, 3)
Roots of 8218 mod 10007: (9872, 135)
Roots of 56 mod 101: (37, 64)
Line 1,746 ⟶ 2,095:
{{trans|EchoLisp}}
<
(require math/number-theory)
Line 1,819 ⟶ 2,168:
(report-Cipolla 881398088036 1000000000039)
(report-Cipolla 34035243914635549601583369544560650254325084643201
100000000000000000000000000000000000000000000000151))</
{{out}}
Line 1,831 ⟶ 2,180:
Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039)
Roots of 34035243914635549601583369544560650254325084643201 are (17436881171909637738621006042549786426312886309400,82563118828090362261378993957450213573687113690751) (mod 100000000000000000000000000000000000000000000000151)</pre>
=={{header|Raku}}==
(formerly Perl 6)
Line 1,837 ⟶ 2,185:
{{trans|Sidef}}
<syntaxhighlight lang="raku"
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {
Line 1,896 ⟶ 2,244:
!! "No solution for ($n, $p)"
}
</syntaxhighlight>
{{out}}
<pre>Roots of 10 are (6, 7) mod 13
Line 1,908 ⟶ 2,256:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151
</pre>
=={{header|Sage}}==
{{works with|Sage|7.6}}
<
def eulerCriterion(a, p):
return -1 if pow(a, int((p-1)/2), p) == p-1 else 1
Line 1,965 ⟶ 2,312:
return sorted(out)
</syntaxhighlight>
{{out}}
<pre>
Line 1,980 ⟶ 2,327:
False
</pre>
=={{header|Scala}}==
===Imperative solution===
<
private val BIG = BigInt(10).pow(50) + BigInt(151)
Line 2,036 ⟶ 2,382:
}
}</
{{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}}
<
legendre(n, p) == 1 || return nil
Line 2,089 ⟶ 2,434:
say "No solution for (#{n}, #{p})"
}
}</
{{out}}
<pre>Roots of 10 are (6 7) mod 13
Line 2,099 ⟶ 2,444:
Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151</pre>
Simpler implementation:
<syntaxhighlight lang="ruby">func cipolla(n, p) {
kronecker(n, p) == 1 || return nil
var (a, ω) = (
0..Inf -> lazy.map {|a|
[a, submod(a*a, n, p)]
}.first_by {|t|
kronecker(t[1], p) == -1
}...
)
var r = lift(Mod(Quadratic(a, 1, ω), p)**((p+1)>>1))
r.b == 0 ? r.a : nil
}</syntaxhighlight>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Module Module1
Line 2,173 ⟶ 2,537:
End Sub
End Module</
{{out}}
<pre>(6, 7, True)
Line 2,183 ⟶ 2,547:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="wren">import "./big" for BigInt
import "./dynamic" for Tuple
var Point = Tuple.create("Point", ["x", "y"])
var bigBig = BigInt.ten.pow(50) + BigInt.new(151)
var c = Fn.new { |ns, ps|
var n = BigInt.new(ns)
var p = (ps != "") ? BigInt.new(ps) : bigBig
// Legendre symbol, returns 1, 0 or p - 1
var ls = Fn.new { |a| a.modPow((p - BigInt.one) / BigInt.two, p) }
// Step 0, validate arguments
if (ls.call(n) != BigInt.one) return [BigInt.zero, BigInt.zero, false]
// Step 1, find a, omega2
var a = BigInt.zero
var omega2
while (true) {
omega2 = (a * a + p - n) % p
if (ls.call(omega2) == p - BigInt.one) break
a = a.inc
}
// multiplication in Fp2
var mul = Fn.new { |aa, bb|
return Point.new((aa.x * bb.x + aa.y * bb.y * omega2) % p,
(aa.x * bb.y + bb.x * aa.y) % p)
}
// Step 2, compute power
var r = Point.new(BigInt.one, BigInt.zero)
var s = Point.new(a, BigInt.one)
var nn = ((p + BigInt.one) >> 1) % p
while (nn > BigInt.zero) {
if ((nn & BigInt.one) == BigInt.one) r = mul.call(r, s)
s = mul.call(s, s)
nn = nn >> 1
}
// Step 3, check x in Fp
if (r.y != BigInt.zero) return [BigInt.zero, BigInt.zero, false]
// Step 5, check x * x = n
if (r.x * r.x % p != n) return [BigInt.zero, BigInt.zero, false]
// Step 4, solutions
return [r.x, p - r.x, true]
}
System.print(c.call("10", "13"))
System.print(c.call("56", "101"))
System.print(c.call("8218", "10007"))
System.print(c.call("8219", "10007"))
System.print(c.call("331575", "1000003"))
System.print(c.call("665165880", "1000000007"))
System.print(c.call("881398088036", "1000000000039"))
System.print(c.call("34035243914635549601583369544560650254325084643201", ""))</syntaxhighlight>
{{out}}
<pre>
[6, 7, true]
[37, 64, true]
[9872, 135, true]
[0, 0, false]
[855842, 144161, true]
[475131702, 524868305, true]
[791399408049, 208600591990, true]
[82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true]
</pre>
=={{header|zkl}}==
{{trans|EchoLisp}}
Uses lib GMP (GNU MP Bignum Library).
<
fcn modEq(a,b,p) { (a-b)%p==0 }
fcn Legendre(a,p){ a.powm((p - 1)/2,p) }
Line 2,217 ⟶ 2,656:
println("Roots of %d are (%d,%d) (mod %d)".fmt(n,x,(p-x)%p,p));
return(x,(p-x)%p);
}</
<
T(10,13),T(56,101),T(8218,10007),T(8219,10007),T(331575,1000003),
T(665165880,1000000007),T(881398088036,1000000000039),
Line 2,224 ⟶ 2,663:
BN(10).pow(50) + 151) )){
try{ Cipolla(n,p) }catch{ println(__exception) }
}</
{{out}}
<pre>
|