123 lines
2.4 KiB
Dart
123 lines
2.4 KiB
Dart
class Pair {
|
|
final int n;
|
|
final int p;
|
|
|
|
Pair(this.n, this.p);
|
|
}
|
|
|
|
class Solution {
|
|
final int root1;
|
|
final int root2;
|
|
final bool isSquare;
|
|
|
|
Solution(this.root1, this.root2, this.isSquare);
|
|
}
|
|
|
|
int multiplyModulus(int a, int b, int modulus) {
|
|
a %= modulus;
|
|
b %= modulus;
|
|
if (b < a) {
|
|
var temp = a;
|
|
a = b;
|
|
b = temp;
|
|
}
|
|
|
|
int result = 0;
|
|
while (a > 0) {
|
|
if (a % 2 == 1) {
|
|
result = (result + b) % modulus;
|
|
}
|
|
b = (b << 1) % modulus;
|
|
a >>= 1;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
int powerModulus(int base, int exponent, int modulus) {
|
|
if (modulus == 1) return 0;
|
|
|
|
base %= modulus;
|
|
int result = 1;
|
|
while (exponent > 0) {
|
|
if ((exponent & 1) == 1) {
|
|
result = multiplyModulus(result, base, modulus);
|
|
}
|
|
base = multiplyModulus(base, base, modulus);
|
|
exponent >>= 1;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
int legendre(int a, int p) {
|
|
return powerModulus(a, (p - 1) ~/ 2, p);
|
|
}
|
|
|
|
Solution tonelliShanks(int n, int p) {
|
|
if (legendre(n, p) != 1) {
|
|
return Solution(0, 0, false);
|
|
}
|
|
|
|
// Factor out powers of 2 from p - 1
|
|
int q = p - 1;
|
|
int s = 0;
|
|
while (q % 2 == 0) {
|
|
q ~/= 2;
|
|
s += 1;
|
|
}
|
|
|
|
if (s == 1) {
|
|
int result = powerModulus(n, (p + 1) ~/ 4, p);
|
|
return Solution(result, p - result, true);
|
|
}
|
|
|
|
// Find a non-square z such that (z | p) = -1
|
|
int z = 2;
|
|
while (legendre(z, p) != p - 1) {
|
|
z += 1;
|
|
}
|
|
|
|
int c = powerModulus(z, q, p);
|
|
int t = powerModulus(n, q, p);
|
|
int m = s;
|
|
int result = powerModulus(n, (q + 1) ~/ 2, p);
|
|
|
|
while (t != 1) {
|
|
int i = 1;
|
|
int zTemp = multiplyModulus(t, t, p);
|
|
while (zTemp != 1 && i < m - 1) {
|
|
i += 1;
|
|
zTemp = multiplyModulus(zTemp, zTemp, p);
|
|
}
|
|
|
|
int b = powerModulus(c, 1 << (m - i - 1), p);
|
|
c = multiplyModulus(b, b, p);
|
|
t = multiplyModulus(t, c, p);
|
|
m = i;
|
|
result = multiplyModulus(result, b, p);
|
|
}
|
|
|
|
return Solution(result, p - result, true);
|
|
}
|
|
|
|
void main() {
|
|
final List<Pair> tests = [
|
|
Pair(10, 13),
|
|
Pair(56, 101),
|
|
Pair(1030, 1009),
|
|
Pair(1032, 1009),
|
|
Pair(44402, 100049),
|
|
Pair(665820697, 1000000009),
|
|
Pair(881398088036, 1000000000039),
|
|
];
|
|
|
|
for (final test in tests) {
|
|
final solution = tonelliShanks(test.n, test.p);
|
|
print('n = ${test.n}, p = ${test.p}');
|
|
if (solution.isSquare) {
|
|
print('has solutions: ${solution.root1} and ${solution.root2}\n');
|
|
} else {
|
|
print('has no solutions because n is not a square modulo p\n');
|
|
}
|
|
}
|
|
}
|