java - 二次筛提取阶段最有效的分解算法是什么？

问题描述

在二次筛算法中，在使用对数逼近找到 bSmooth 值后，您需要对数字进行分解，我们称之为B，以构造 bSmooth 向量。

一个常见的解决方案是使用因子基中的素数进行试除法。与随机数不同，在这种情况下，试除法非常有效，因为大多数因子都在质数基中。我说“大多数”是因为一个常见的优化将允许一个小的阈值包含 1-3 个 prims，其乘积最多为 2^30 左右，这称为部分关系。

在我当前的实现中，这个向量提取阶段花费了大部分时间。我一直在尝试做的另一个解决方案是接收，再次越过素数基础，并将向量记录在已知为 b 平滑的索引中。但结果变得更慢。

下面是我目前的代码，我为试用部门添加了4个优化，请告诉我是否有更好的解决方案。

对于素数 2，我检查最后一组位B并右移以提取它。
我正在使用 BigInteger divideAndRemainder，它通过将除法和 mod 动作组合为 1 来优化内存和性能
如果B小于因子基中的最大素数，那么它必须在因子基中，所以我使用哈希映射来定位它的索引
如果没有素数B.bitLenght() / 2正在划分B，那么它必须是部分关系，只有当它是素数时我才会包含它。

    private VectorData extractVector(BigInteger value) {
        BitSet vector = new BitSet(PrimeBase.instance.primeBase.size());
        if(value.compareTo(BigInteger.ZERO) < 0){
            vector.set(0);
            value = value.abs();
        }
        value = extractPower2(value, vector);
        for (int i = 2; i < PrimeBase.instance.primeBase.size(); i++) {
            BigInteger p = PrimeBase.instance.primeBaseBigInteger.get(i);
            int count = 1;
    
            BigInteger[] results = value.divideAndRemainder(p);
            if (results[1].equals(BigInteger.ZERO)) {
                value = results[0];
                while (true) {
                    results = value.divideAndRemainder(p);
                    if(!results[1].equals(BigInteger.ZERO)){
                        break;
                    }
                    value = results[0];
                    count++;
                }
                if(count % 2 == 1) {
                    vector.set(i);
                }
    
                if (value.equals(BigInteger.ONE)) {
                    bSmoothVectorData.vector = vector;
                    return bSmoothVectorData;
                } else if (value.compareTo(PrimeBase.instance.maxPrimeBigInteger) <= 0) {
                    int index = PrimeBase.instance.primeBaseMap.get(value);
                    vector.set(index);
                    bSmoothVectorData.vector = vector;
                    return bSmoothVectorData;
                } else if (value.bitLength() / 2 < p.bitLength()) {
                    if (isPrime(value.longValue())) {
                        return new VectorData(vector, value);
                    }
                    return null;
                }
            }
        }
        return null;
    }

bSmoothVectorData用于区分完全关系和部分关系。最后一个调用 else-if 的情况isPrime很少见，并且该方法的整体性能不到 0.001%，瓶颈在于调用divideAndRemainder该方法需要大约 72% 的性能。

标签： javaalgorithmfactorization

通过将试用部门转换为接收，我能够实现近 80% 的性能提升。现在，我已经在问题中提到我之前尝试过这个但没有成功。嗯，这次成功了。

我BigInteger.mod(x).equals(ZERO)用整数运算替换了测试(bSmoothData.localX - delta) % prime == startingPosition，它可能非常特定于我的实现，但想法是检查素数是否应该划分筛分数组中的 bSmooth 索引。

接下来，我构造了所有这些素数的乘积，并将实际的 bSmooth 值除以它，然后我留下了一个可以进入 Java 的提醒。我继续使用试用部门提取它。如果你对我的实现感兴趣，我在这里制作了一个关于它的视频

java - 二次筛提取阶段最有效的分解算法是什么？

问题描述

解决方案

推荐阅读