Factoring in the Quadratic Sieve

[jasonp]

Originally Posted by ThiloHarich

Why is msieve so dammed fast?

Practice practice practice :)

jasonp

[Mystwalker]

Originally Posted by ThiloHarich

Here were my results based on my Factoring Algorithm:

Thanks for the comparisons, Thilo. The performance increase for JDK 1.6 without "-server" is surprising. I so far found no reason for it - but your postings on the java.sun.com forum.

What where the absolute runtimes of your benchmark? In the order of minutes?

[ThiloHarich]

They run only for about 10 sec. I run each test 3 times and took the best value.
I made longer runs for the -server option on JDK 1.5 and 1.6 to manifest the difference. It is there.

I only count the sieving phase, not the setup of the Factorbase (since the sieving phase dominates the running time for MPQS).
The IBM JRE has an interesting phenomenon. After the second polynom the performance goes down darmatically (factor 10) for one or two polynomials, then the performance comes back again. In the second or third run it performed well from the beginning. The Sun JRE has no such peeks.
I used System.currentTimeMillis () which is not very pecise. Since JDK 1.5 there is the more precise System.nanoTime().

How much faster is the SIQS compared with the MPQS?
I got a factor of 2 in my mind but hope for a bigger value.
In my tests the large prime variant gives a factor of 2 (simply since there were nearly as much large congruencies as normal congruencies).
So I can hope to improve Performance only by a factor of 4. So I am still far away from mseive

[alpertron]

Originally Posted by ThiloHarich

So I can hope to improve Performance only by a factor of 4. So I am still far away from mseive

Java experiences very high penalties for array access because it has the check whether the index is inside bounds. This does not happen on programs written in C.

If you are not writing applets, Java is a bad choice for numerical programs.

[alpertron]

Originally Posted by ThiloHarich

The IBM JRE has an interesting phenomenon. After the second polynom the performance goes down darmatically (factor 10) for one or two polynomials, then the performance comes back again. In the second or third run it performed well from the beginning. The Sun JRE has no such peeks.

This is not strange at all. The Just in Time (JIT) compiler detects that it is running repeated code and starts compiling (slowing down code execution), then it works OK. It is possible that the Virtual Machine caches somewhere on your computer the compiled code so the second time your program starts, the delay is not noticeable.

You should run your programs for at least two minutes in order to have a better benchmark.

[ThiloHarich]

At http://dada.perl.it/shootout/sieve.html
there is a factor of 5 between C and JAVA on the Sieve of Erathostenes.
This should be due to the range check in JAVA, as you already said.

With JNI (Java Native Interface) you can call C or C++ from Java, in order to do the sieving. But because of the different management of (array) Objects this seems to be no good solution.

[Mystwalker]

Originally Posted by ThiloHarich

With JNI (Java Native Interface) you can call C or C++ from Java, in order to do the sieving. But because of the different management of (array) Objects this seems to be no good solution.

In addition, you have the call overhead. Unless the call frequency is very low, this should negate (or at least reduce) any performance improvements.

As stated earlier, you could try gcj with the option -fno-bounds-check.
I haven't tested it yet, though.

[ThiloHarich]

I am working under windows. I hate all this linux gcc stuff. I can not get it running. Now I am downloading the minGW stuff. This is why i like java. It works.

[ThiloHarich]

After fighting with gcj I did a test with the sieve of Erathostenes.
GCJ with --no-bounds-check has the same performance as JDK 1.5_08 -server.
So java do not seems to be a good solution for this kind of Algorithms.

[ThiloHarich]

Back to the sieving.
I think it is not necessary to sieve with all primes of the factorbase.
As stated earlier we can skip sieving with the small primes.

When we have a sieving Intervall n*log n and a highest prime n*log n
sieving with the log (n) smallest prime has effort n*log n / (log n * log log (n)) = n / log log (n) sieving with the log (n) smallest primes has at least effort n * log (n)/ log log (n).

Sieving with (1-epsilon) * n highest of the n primes we have effort:
n*log n / (epsilon * n log (espilon * n)) = (1/eplison * (1+epsilon)) per prime. which is (1+1/eplison) * (1-epsilon)* n ~ 1/epsilon * n.

So sieving with the small primes is very expensive (i know the calculation above is very raw).

I stop sieving with the 30th smallest prime for factorBase Size 35576 (MPQS 65 Digit Input). And check the divideability of the smooth q(x) by checking if q(x) mod p is one of the values we tried to sieve with for prime p. I increased the smooth threshold from 1.1 * max_prime to 1.9 * max_prime. Since we have to check ~10 pseudo smooth q(x) to get one real smooth, this is no big extra effort.
@ Jasonp This is some kind of hashing with the prime we sieve with, if you want to see it in this way.

My idea is to start with normal sieving for bigger primes. After this phase we have collected pseudo smooth q(x) with many primes.
These were very sparse (compared to the sieve interval). Then we try to find the divisors of these q (x) for the remaining primes.

The question is: "Is there a clever way to find the small divisors?"
Is there a way to find them without checking every of the pseudo smooth values with every prime.
Can we create an efficient function which decides if the prime p divides one (or more precisely which of the) pseudo smooth q (x)?

We might calculate the remainder of q(x) after dividing out the bigger primes and start a Factorization.
Is there a fast algorithm for dividability with small primes?

@ alpertron do you factorize the small primes with the ECM?

[akruppa]

There is something I've been wondering about for a while: if you don't sieve with small primes, do you still sieve with large enough powers of small primes? I suppose you should, if sieving with, say, 127 is worthwhile, so should be sieving with 128.

Alex