CODEWITHSUNDEEP
javaalgorithmfactorization
Ilya Gazman
Ilya Gazman

Reputation: 32261

What is the most efficient factoring algorithm for quadratic sieve extraction phase?

In the quadratic sieve algorithm, after finding bSmooth values using logarithmic approximation you need to factor the number, let's call it B, to construct the bSmooth vector.

A common solution is to use a trial division using the primes in the factor base. Unlike random numbers, in this case, the trial division is super efficient since most of the factors will be in the prime base. I am saying "most" because a common optimization will allow a small threshold to include 1-3 prims with a product of up to 2^30 or so, it's called a partial relation.

In my current implementation, this vector extraction phase takes most of the time. Another solution that I have been trying to do is receiving, walking again over the prime base, and record the vectors in the indexes knowen to be b-smooth., but that turned to be even slower.

Below is my current code, I added 4 optimizations for the trial division, please tell me if there are better solutions for it.

  1. For the prime 2, I check the last set bit of B and shift right to extract it.
  2. I am using BigInteger divideAndRemainder it's optimizing both the memory and the performance by combining the division and the mod actions into 1
  3. if B is smaller then the max prime in the factor base, then it must be in the factor base, so I use a hash map to locate it's index
  4. if no prime up to B.bitLenght() / 2 is dividing B then it must be a partial relation, I will include it only if it's a prime.
    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 is used to differentiate between full and partial relations. The last else-if case that calls for isPrime is rare and takes less than 0.001% overall performance of this method, the bottleneck is in the call to divideAndRemainder that takes about 72% of the performance.

Upvotes: 1

Views: 384

Answers (1)

Ilya Gazman
Ilya Gazman

Reputation: 32261

I was able to achieve a nearly 80% boost in performance by switching the trial division with receiving. Now, I already mentioned in the question that I tried this before with no success. Well, this time it worked.

I replaced the BigInteger.mod(x).equals(ZERO) test with integer operations (bSmoothData.localX - delta) % prime == startingPosition, it's probably very specific to my implemintation, but the idea is to check if the prime is supposed to divide the bSmooth index in the sieving array.

Next, I construct a product of all those primes and divide the actual bSmooth value by it, I left then with a reminder that can feet into Java long. And I continue extracting it using trial division. If you are interested in my implementation I made a video about it here

Upvotes: 1

Related Questions