使用素数阵列直到目标的并行素数因式分解

Question

我已经在Stack上看到了这个问题，但是我找不到任何具体的答案，或者至少我能理解的答案。所以这是我的问题：

如何并行化一个大数的因式分解？

我见过这样的回答:“…他只需要为找到的每个因素生成一个新线程，然后用某种同步对象来收集所有的因素”

但是我不太明白这是怎么做到的。有人能用例子解释一下吗？

Answer 1

如果你有一个素数列表。你可以这样做（对于真正的大数，可能需要一段时间）。用一张地图来保存素数因子的频率计数和它们出现的次数。

• 继续用当前素数除以目标，直到它不除以为止
• 然后使用BigInteger检查该值是否为素数（如果剩余值很大且为素数，则会大大加快处理速度）
• 继续下去，直到找到所有的因子或者你用完了素数

long candidate = 498977279919318060L;

Map<Long, Integer> factors = new TreeMap<>();
for (long p : primes) {
    while (candidate % p == 0) {
        factors.compute(p, (k,v) -> v == null ? 1 : v+1);
        candidate/=p;
    }
    if (BigInteger.valueOf(candidate).isProbablePrime(99)) {
        factors.put(candidate,1);
        candidate = 1;
        break;
    }
}
if (candidate != 1) {
    System.out.println("factorization incomplete - stopped at " + candidate);
}

factors.entrySet().forEach(System.out::println);

指纹

2=2
3=5
5=1
7=1
19=3
29=1
73=2
101=1
137=1

您可以通过首先将每个因子提高到其频率，然后使用duce计算这些结果的乘积来验证结果。

long val = factors.entrySet().stream()
        .mapToLong(e -> (long) Math
                .pow(e.getKey().doubleValue(), e.getValue()))
        .reduce(1L, (a, b) -> a * b);

System.out.println(val);

指纹

498977279919318060