package rsa;
import java.math.BigInteger;
public final class rsa implements rsaa {
public static void main(String[] args) {
System.out.println(new rsa().run());
}
private static final int P = 1009;
private static final int Q = 3643;
private static final int TOTIENT = (P - 1) * (Q - 1);
public String run() {
int[] numUnconcealedP = countAllUnconcealed(P);
int[] numUnconcealedQ = countAllUnconcealed(Q);
int minUnconcealedP = Integer.MAX_VALUE;
for (int x : numUnconcealedP)
minUnconcealedP = Math.min(x, minUnconcealedP);
int minUnconcealedQ = Integer.MAX_VALUE;
for (int x : numUnconcealedQ)
minUnconcealedQ = Math.min(x, minUnconcealedQ);
long sum = 0;
for (int e = 0; e < TOTIENT; e++) {
if (numUnconcealedP[e % (P - 1)] == minUnconcealedP && numUnconcealedQ[e % (Q - 1)] == minUnconcealedQ)
sum += e;
}
return Long.toString(sum);
}
private static int[] countAllUnconcealed(int prime) {
int[] numUnconcealed = new int[prime - 1];
for (int e = 0; e < numUnconcealed.length; e++) {
if (Library.gcd(e, prime - 1) == 1)
numUnconcealed[e] = countUnconcealed(prime, e);
else
numUnconcealed[e] = Integer.MAX_VALUE;
}
return numUnconcealed;
}
private static int countUnconcealed(int modulus, int e) {
int count = 0;
for (int m = 0; m < modulus; m++) {
if (Library.powMod(m, e, modulus) == m)
count++;
}
return count;
}
final static class Library {
public static int powMod(int x, int y, int m) {
if (x < 0)
throw new IllegalArgumentException("Negative base not supported");
if (y < 0)
throw new IllegalArgumentException("Modular reciprocal not supported");
if (m <= 0)
throw new IllegalArgumentException("Modulus must be positive");
if (m == 1)
return 0;
// Exponentiation by squaring
int z = 1;
while (y != 0) {
if ((y & 1) != 0)
z = (int)((long)z * x % m);
x = (int)((long)x * x % m);
y >>>= 1;
}
return z;
}
public static int gcd(int x, int y) {
if (x < 0 || y < 0)
throw new IllegalArgumentException("Negative number");
while (y != 0) {
int z = x % y;
x = y;
y = z;
}
return x;
}
}
}
评论0