Cipolla's algorithm: Difference between revisions
Added Wren
m (Phix/mpfr) |
(Added Wren) |
||
Line 2,183:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
<lang ecmascript>import "/big" for BigInt
class Point {
construct new(x, y) {
_x = x
_y = y
}
x { _x }
y { _y }
toString { "(%(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", ""))</lang>
{{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}}==
| |||