Tonelli-Shanks algorithm: Difference between revisions
Added solution for D
(Added solution for D) |
|||
Line 69:
* [[Cipolla's algorithm]]
<br><br>
=={{header|D}}==
{{trans|Kotlin}}
<lang D>import std.bigint;
import std.stdio;
import std.typecons;
alias Pair = Tuple!(long, "n", long, "p");
enum BIGZERO = BigInt("0");
enum BIGONE = BigInt("1");
enum BIGTWO = BigInt("2");
enum BIGTEN = BigInt("10");
struct Solution {
BigInt root1, root2;
bool exists;
}
/// https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
BigInt modPow(BigInt b, BigInt e, BigInt n) {
if (n == 1) return BIGZERO;
BigInt result = 1;
b = b % n;
while (e > 0) {
if (e % 2 == 1) {
result = (result * b) % n;
}
e >>= 1;
b = (b*b) % n;
}
return result;
}
Solution ts(long n, long p) {
return ts(BigInt(n), BigInt(p));
}
Solution ts(BigInt n, BigInt p) {
auto powMod(BigInt a, BigInt e) {
return a.modPow(e, p);
}
auto ls(BigInt a) {
return powMod(a, (p-1)/2);
}
if (ls(n) != 1) return Solution(BIGZERO, BIGZERO, false);
auto q = p - 1;
auto ss = BIGZERO;
while ((q & 1) == 0) {
ss = ss + 1;
q = q >> 1;
}
if (ss == BIGONE) {
auto r1 = powMod(n, (p + 1) / 4);
return Solution(r1, p - r1, true);
}
auto z = BIGTWO;
while (ls(z) != p - 1) z = z + 1;
auto c = powMod(z, q);
auto r = powMod(n, (q + 1) / 2);
auto t = powMod(n, q);
auto m = ss;
while (true) {
if (t == 1) return Solution(r, p - r, true);
auto i = BIGZERO;
auto zz = t;
while (zz != 1 && i < m - 1) {
zz = zz * zz % p;
i = i + 1;
}
auto b = c;
auto e = m - i - 1;
while (e > 0) {
b = b * b % p;
e = e - 1;
}
r = r * b % p;
c = b * b % p;
t = t * c % p;
m = i;
}
}
void main() {
auto pairs = [
Pair( 10L, 13L),
Pair( 56L, 101L),
Pair( 1_030L, 10_009L),
Pair( 1_032L, 10_009L),
Pair( 44_402L, 100_049L),
Pair( 665_820_697L, 1_000_000_009L),
Pair(881_398_088_036L, 1_000_000_000_039L),
];
foreach (pair; pairs) {
auto sol = ts(pair.n, pair.p);
writeln("n = ", pair.n);
writeln("p = ", pair.p);
if (sol.exists) {
writeln("root1 = ", sol.root1);
writeln("root2 = ", sol.root2);
}
else writeln("No solution exists");
writeln();
}
auto bn = BigInt("41660815127637347468140745042827704103445750172002");
auto bp = BIGTEN ^^ 50 + 577L;
auto sol = ts(bn, bp);
writeln("n = ", bn);
writeln("p = ", bp);
if (sol.exists) {
writeln("root1 = ", sol.root1);
writeln("root2 = ", sol.root2);
}
else writeln("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|EchoLisp}}==
| |||