这道题目要求跟据 RSA 加密算法中的 n、 e 和 d 求出 p 和 q。其中 n = pq；e 和 d 互为 MOD (p - 1)(q - 1) 情况下的逆元，即 ed MOD (p - 1)(q - 1) = 1；p < q；n, d ≤ 10
100； 3 ≤ e ≤ 31。
我记得比赛时有不少队做出了这道题，可是我们毫无头绪。以下是 PROXIMA 队的做法。
已知 ed - 1 是 (p - 1)(q - 1) 的倍数，则可以枚举可能的 (p - 1)(q - 1) 值。他们枚举了 ed - 1、(ed - 1) / 2……直到 (ed - 1) / 100。
然后设 t = (p - 1)(q - 1)，n = pq，则可以解出 p 和 q：
- p =
^{2}-4t}}{2}+1 "\frac{n-t-1-\sqrt{(n-t-1)^{2}-4t}}{2}+1")
- q =
^{2}-4t}}{2}+1 "\frac{n-t-1+\sqrt{(n-t-1)^{2}-4t}}{2}+1")
只要碰到中间过程整除都除得尽、根号都开得出的，就是答案了。这么说起来好像一点也不难，我们怎么就是想不出呢，主要还是被大数吓到了。以下是 PROXIMA 队的代码，其中第 61 ~ 80 行重复了两遍，我没看出这有什么作用：
import java.io.FileInputStream;
import java.math.BigInteger;
import java.util.Random;
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author acm
*/
public class Main {
public static BigInteger sqrt(BigInteger a) {
double ad = a.doubleValue();
ad = Math.sqrt(ad);
BigInteger l = BigInteger.valueOf(0);
BigInteger r = new BigInteger(a.toString());
/*double size = Math.log10(a.doubleValue());
if (size)*/
while (l.compareTo(r)<0) {
BigInteger mid = l.add(r).divide(BigInteger.valueOf(2));
int res = mid.multiply(mid).compareTo(a);
if (res==0) return mid;
if (res<0) l = mid.add(BigInteger.ONE);
else r = mid.subtract(BigInteger.ONE);
}
return l;
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
/* BigInteger a1 = BigInteger.probablePrime(100, new Random());
BigInteger a2 = BigInteger.probablePrime(100, new Random());
BigInteger d = BigInteger.probablePrime(199, new Random());
System.out.println(a1);
System.out.println(a2);
System.out.println(a1.multiply(a2));
System.out.println(d);
System.out.println();
*/
try {
Scanner in = new Scanner(new FileInputStream("c.in"));
for (int tt=1;; tt++) {
BigInteger n = in.nextBigInteger();
BigInteger d = in.nextBigInteger();
int e = in.nextInt();
if (e==0) break;
d = d.multiply(BigInteger.valueOf(e)).subtract(BigInteger.ONE);
for (int kk=1; kk<=100; kk++) {
BigInteger t = d.divide(BigInteger.valueOf(kk));
if (t.multiply(BigInteger.valueOf(kk)).equals(d)) {
BigInteger tosqrt = n.subtract(t).subtract(BigInteger.ONE).pow(2).subtract(t.multiply(BigInteger.valueOf(4)));
if (tosqrt.compareTo(BigInteger.ZERO)>=0) {
BigInteger sol = sqrt(tosqrt);
if (sol.pow(2).equals(tosqrt)) {
BigInteger x = n.subtract(t).subtract(BigInteger.ONE).add(sol).divide(BigInteger.valueOf(2));
BigInteger y = n.subtract(t).subtract(BigInteger.ONE).subtract(x);
BigInteger p = x.add(BigInteger.ONE), q = y.add(BigInteger.ONE);
if (p.signum()>0 && q.signum()>0 && p.multiply(q).equals(n) && p.isProbablePrime(100) && q.isProbablePrime(100)) {
if (p.compareTo(q)>0) {
BigInteger sw = p; p = q; q = sw;
}
System.out.println("Case #"+tt+": "+p+" "+q);
break;
}
x = n.subtract(t).subtract(BigInteger.ONE).subtract(sol).divide(BigInteger.valueOf(2));
y = n.subtract(t).subtract(BigInteger.ONE).subtract(x);
p = x.add(BigInteger.ONE); q = y.add(BigInteger.ONE);
if (p.signum()>0 && q.signum()>0 && p.multiply(q).equals(n) && p.isProbablePrime(100) && q.isProbablePrime(100)) {
if (p.compareTo(q)>0) {
BigInteger sw = p; p = q; q = sw;
}
System.out.println("Case #"+tt+": "+p+" "+q);
break;
}
}
}
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
