Cipolla's algorithm: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(6 intermediate revisions by 4 users not shown) | |||
Line 75:
* [[Tonelli-Shanks algorithm]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<
I (n < 2)
R [n]
Line 125 ⟶ 124:
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))</
{{out}}
Line 135 ⟶ 134:
Roots of 8219 mod 10007: []
</pre>
=={{header|C}}==
{{trans|FreeBasic}}
<
#include <stdint.h>
#include <stdio.h>
Line 327 ⟶ 325:
return 0;
}</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 346 ⟶ 344:
Find solution for n = 665165880 and p = 1000000007
Solution found: x1 = 524868305, x2 = 475131702</pre>
=={{header|C sharp|C#}}==
<
using System.Numerics;
Line 424 ⟶ 421:
}
}
}</
{{out}}
<pre>(6, 7, True)
Line 434 ⟶ 431:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.stdio;
import std.typecons;
Line 520 ⟶ 516:
writeln(c("881398088036", "1000000000039"));
writeln(c("34035243914635549601583369544560650254325084643201", ""));
}</
{{out}}
<pre>Tuple!(BigInt, "x", BigInt, "y", bool, "b")(6, 7, true)
Line 530 ⟶ 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 584 ⟶ 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 605 ⟶ 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 621 ⟶ 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 639 ⟶ 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}}
<
math math.extras math.functions ;
Line 693 ⟶ 686:
[ 2dup - [I Roots of ${3} are (${1} ${0}) mod ${2}I] ]
[ [I No solution for (${}, ${})I] ] if* nl
] assoc-each</
{{out}}
<pre>
Line 705 ⟶ 698:
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 896 ⟶ 888:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 920 ⟶ 912:
===GMP version===
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 1,067 ⟶ 1,059:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>Find solution for n = 10 and p = 13
Line 1,092 ⟶ 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,158 ⟶ 1,149:
fmt.Println(c(8219, 10007))
fmt.Println(c(331575, 1000003))
}</
{{out}}
<pre>
Line 1,169 ⟶ 1,160:
===big.Int===
Extra credit:
<
import (
Line 1,228 ⟶ 1,219:
fmt.Println(&R1)
fmt.Println(&R2)
}</
{{out}}
<pre>
Line 1,236 ⟶ 1,227:
17436881171909637738621006042549786426312886309400
</pre>
=={{header|J}}==
Based on the echolisp implementation:
<
x (y&|)@^ (y-1)%2
)
Line 1,274 ⟶ 1,264:
assert. 'not a valid square root'
end.
)</
Task examples:
<
6 7
56 cipolla 101
Line 1,294 ⟶ 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,406 ⟶ 1,395:
System.out.println(c("34035243914635549601583369544560650254325084643201", ""));
}
}</
{{out}}
<pre>(6, 7, true)
Line 1,416 ⟶ 1,405:
(791399408049, 208600591990, true)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>
=={{header|jq}}==
{{trans|Wren}}
Line 1,422 ⟶ 1,410:
A Point is represented by a numeric array of length two (i.e. [x,y]).
<
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
Line 1,499 ⟶ 1,487:
;
exercise</
{{out}}
<pre>
Line 1,511 ⟶ 1,499:
[82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,true]
</pre>
=={{header|Julia}}==
{{trans|Perl}}
<
function legendre(n, p)
Line 1,561 ⟶ 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,572 ⟶ 1,558:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151.
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 1,641 ⟶ 1,626:
println(c("881398088036", "1000000000039"))
println(c("34035243914635549601583369544560650254325084643201", ""))
}</
{{out}}
Line 1,654 ⟶ 1,639:
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
Cipolla[n_, p_] := Module[{ls, omega2, nn, a, r, s},
ls = JacobiSymbol[n, p];
Line 1,694 ⟶ 1,678:
Cipolla[665165880, 1000000007]
Cipolla[881398088036, 1000000000039]
Cipolla[34035243914635549601583369544560650254325084643201, 10^50 + 151]</
{{out}}
<pre>{6,7,True}
Line 1,704 ⟶ 1,688:
{791399408049,208600591990,True}
{82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,True}</pre>
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<
import bignum
Line 1,787 ⟶ 1,770:
let sols = c(n, p)
if sols.isSome: echo sols.get()
else: echo "No solutions."</
{{out}}
Line 1,798 ⟶ 1,781:
(791399408049, 208600591990)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400)</pre>
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<
use ntheory qw(is_prime);
Line 1,852 ⟶ 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,861 ⟶ 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}}
<!--<
<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 1,960 ⟶ 1,941:
<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>
<!--</
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,974 ⟶ 1,955:
{"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}
</pre>
=={{header|PicoLisp}}==
{{trans|Go}}
<
(de **Mod (X Y N)
(let M 1
Line 2,037 ⟶ 2,017:
(println (ci 665165880 1000000007))
(println (ci 881398088036 1000000000039))
(println (ci 34035243914635549601583369544560650254325084643201 (+ (** 10 50) 151)))</
{{out}}
<pre>
Line 2,049 ⟶ 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 2,097 ⟶ 2,076:
return (x1[0],-x1[0]%p)
print
print
print
print
print
</syntaxhighlight>
{{out}}▼
▲{{out}}
<pre>Roots of 2 mod 7: (4, 3)▼
<pre>
Roots of 8218 mod 10007: (9872, 135)
Roots of 56 mod 101: (37, 64)
Line 2,115 ⟶ 2,095:
{{trans|EchoLisp}}
<
(require math/number-theory)
Line 2,188 ⟶ 2,168:
(report-Cipolla 881398088036 1000000000039)
(report-Cipolla 34035243914635549601583369544560650254325084643201
100000000000000000000000000000000000000000000000151))</
{{out}}
Line 2,200 ⟶ 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 2,206 ⟶ 2,185:
{{trans|Sidef}}
<syntaxhighlight lang="raku"
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {
Line 2,265 ⟶ 2,244:
!! "No solution for ($n, $p)"
}
</syntaxhighlight>
{{out}}
<pre>Roots of 10 are (6, 7) mod 13
Line 2,277 ⟶ 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 2,334 ⟶ 2,312:
return sorted(out)
</syntaxhighlight>
{{out}}
<pre>
Line 2,349 ⟶ 2,327:
False
</pre>
=={{header|Scala}}==
===Imperative solution===
<
private val BIG = BigInt(10).pow(50) + BigInt(151)
Line 2,405 ⟶ 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,458 ⟶ 2,434:
say "No solution for (#{n}, #{p})"
}
}</
{{out}}
<pre>Roots of 10 are (6 7) mod 13
Line 2,468 ⟶ 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,542 ⟶ 2,537:
End Sub
End Module</
{{out}}
<pre>(6, 7, True)
Line 2,552 ⟶ 2,547:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
{{libheader|Wren-dynamic}}
<
import "./dynamic" for Tuple
var Point = Tuple.create("Point", ["x", "y"])
Line 2,615 ⟶ 2,609:
System.print(c.call("665165880", "1000000007"))
System.print(c.call("881398088036", "1000000000039"))
System.print(c.call("34035243914635549601583369544560650254325084643201", ""))</
{{out}}
Line 2,632 ⟶ 2,626:
{{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,662 ⟶ 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,669 ⟶ 2,663:
BN(10).pow(50) + 151) )){
try{ Cipolla(n,p) }catch{ println(__exception) }
}</
{{out}}
<pre>
|