Cipolla's algorithm: Difference between revisions

Line 1,351:

</pre>

=={{header|Scala}}==

===Imperative solution===

<lang Scala>object CipollasAlgorithm extends App {

private val BIG = BigInt(10).pow(50) + BigInt(151)

println(c("10", "13"))

println(c("56", "101"))

println(c("8218", "10007"))

println(c("8219", "10007"))

println(c("331575", "1000003"))

println(c("665165880", "1000000007"))

println(c("881398088036", "1000000000039"))

println(c("34035243914635549601583369544560650254325084643201", ""))

private def c(ns: String, ps: String): Triple = {

val (n, p) = (BigInt(ns), if (ps.isEmpty) BIG else BigInt(ps))

// Legendre symbol, returns 1, 0 or p - 1

def ls(a: BigInt) = a.modPow((p - BigInt(1)) / BigInt(2), p)

// multiplication in Fp2

def mul(aa: Point, bb: Point, omega2: BigInt) =

new Point((aa.x * bb.x + aa.y * bb.y * omega2) % p, (aa.x * bb.y + (bb.x * aa.y)) % p)

// Step 0, validate arguments

if (ls(n) != BigInt(1)) new Triple(0, 0, false)

else {

// Step 1, find a, omega2

var (a, flag, omega2) = (BigInt(0), true, BigInt(0))

while (flag) {

omega2 = (a * a + p - n) % p

if (ls(omega2) == p - BigInt(1)) flag = false else a = a + BigInt(1)

}

// Step 2, compute power

var (nn, r, s) = ((p + BigInt(1) >> 1) % p, new Point(BigInt(1), 0), new Point(a, BigInt(1)))

while (nn > 0) {

if ((nn & BigInt(1)) == BigInt(1)) r = mul(r, s, omega2)

s = mul(s, s, omega2)

nn = nn >> 1

}

// Step 3, check x in Fp

if (r.y != 0) new Triple(0, 0, false)

else // Step 5, check x * x = n

if ((r.x * r.x) % p != n) new Triple(0, 0, false)

else new Triple(r.x, p - r.x, true) // Step 4, solutions

}

private class Point(val x: BigInt, val y: BigInt)

private class Triple(val x: BigInt, val y: BigInt, val b: Boolean) {

override def toString: String = f"($x%s, $y%s, $b%s)"

}

}</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)].

=={{header|Sidef}}==

Line 1,403:

Line 1,460:

}</lang>

⚫

<pre>Roots of 10 are (6 7) mod 13

<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

Line 1,411:

Line 1,467:

Roots of 665165880 are (475131702 524868305) mod 1000000007

Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151

Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151</pre>

</pre>

=={{header|zkl}}==