Tonelli-Shanks algorithm: Difference between revisions
Content added Content deleted
(Added solution for D) |
|||
Line 69: | Line 69: | ||
* [[Cipolla's algorithm]] |
* [[Cipolla's algorithm]] |
||
<br><br> |
<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}}== |
=={{header|EchoLisp}}== |