Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
(Added Kotlin) |
|||
Line 747: | Line 747: | ||
41660815127637347468140745042827704103445750172002x tosh (10^50x)+577 |
41660815127637347468140745042827704103445750172002x tosh (10^50x)+577 |
||
32102985369940620849741983987300038903725266634508 67897014630059379150258016012699961096274733366069</lang> |
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}}== |
=={{header|Perl 6}}== |