Tonelli-Shanks algorithm: Difference between revisions
Added Kotlin
(Added Kotlin) |
|||
Line 747:
41660815127637347468140745042827704103445750172002x tosh (10^50x)+577
32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</lang>
=={{header|Kotlin}}==
{{trans|Go}}
<lang scala>// version 1.1.3
import java.math.BigInteger
data class Solution(val root1: BigInteger, val root2: BigInteger, val exists: Boolean)
val bigZero = BigInteger.ZERO
val bigOne = BigInteger.ONE
val bigTwo = BigInteger.valueOf(2L)
val bigFour = BigInteger.valueOf(4L)
val bigTen = BigInteger.TEN
fun ts(n: Long, p: Long) = ts(BigInteger.valueOf(n), BigInteger.valueOf(p))
fun ts(n: BigInteger, p: BigInteger): Solution {
fun powModP(a: BigInteger, e: BigInteger) = a.modPow(e, p)
fun ls(a: BigInteger) = powModP(a, (p - bigOne) / bigTwo)
if (ls(n) != bigOne) return Solution(bigZero, bigZero, false)
var q = p - bigOne
var ss = bigZero
while (q.and(bigOne) == bigZero) {
ss = ss + bigOne
q = q.shiftRight(1)
}
if (ss == bigOne) {
val r1 = powModP(n, (p + bigOne) / bigFour)
return Solution(r1, p - r1, true)
}
var z = bigTwo
while (ls(z) != p - bigOne) z = z + bigOne
var c = powModP(z, q)
var r = powModP(n, (q + bigOne) / bigTwo)
var t = powModP(n, q)
var m = ss
while (true) {
if (t == bigOne) return Solution(r, p - r, true)
var i = bigZero
var zz = t
while (zz != bigOne && i < m - bigOne) {
zz = zz * zz % p
i = i + bigOne
}
var b = c
var e = m - i - bigOne
while (e > bigZero) {
b = b * b % p
e = e - bigOne
}
r = r * b % p
c = b * b % p
t = t * c % p
m = i
}
}
fun main(args: Array<String>) {
val pairs = listOf<Pair<Long, Long>>(
10L to 13L,
56L to 101L,
1030L to 10009L,
1032L to 10009L,
44402L to 100049L,
665820697L to 1000000009L,
881398088036L to 1000000000039L
)
for (pair in pairs) {
val (n, p) = pair
val (root1, root2, exists) = ts(n, p)
println("n = $n")
println("p = $p")
if (exists) {
println("root1 = $root1")
println("root2 = $root2")
}
else println("No solution exists")
println()
}
val bn = BigInteger("41660815127637347468140745042827704103445750172002")
val bp = bigTen.pow(50) + BigInteger.valueOf(577L)
val (broot1, broot2, bexists) = ts(bn, bp)
println("n = $bn")
println("p = $bp")
if (bexists) {
println("root1 = $broot1")
println("root2 = $broot2")
}
else println("No solution exists")
}</lang>
{{out}}
<pre>
n = 10
p = 13
root1 = 7
root2 = 6
n = 56
p = 101
root1 = 37
root2 = 64
n = 1030
p = 10009
root1 = 1632
root2 = 8377
n = 1032
p = 10009
No solution exists
n = 44402
p = 100049
root1 = 30468
root2 = 69581
n = 665820697
p = 1000000009
root1 = 378633312
root2 = 621366697
n = 881398088036
p = 1000000000039
root1 = 791399408049
root2 = 208600591990
n = 41660815127637347468140745042827704103445750172002
p = 100000000000000000000000000000000000000000000000577
root1 = 32102985369940620849741983987300038903725266634508
root2 = 67897014630059379150258016012699961096274733366069
</pre>
=={{header|Perl 6}}==
| |||