At the moment I have only implemented the MPQS, where the sieving interval is larger then the sieving interval in the SIQS. The sieving interval m is a few times bigger then the largest prime. So calculating a * x + b mod p might be faster then resieving.
In SIQS the sieving interval and the larges prime might be in the same area, so resieving will be fast for big factors.
For larger n a ~ sqrt (n)/m and b were no long values. But even if I calculate a * x + b mod p with arbitrary precision this is fast.
My imprecise profiling tool is telling me that sieving takes twice as long as factoring the sieved values. If I eliminate the factoring step the sieving and factoring step decreases only by 1/5.
Forget about my other idea. Calculating the mod is to slow.
Anyway how do you calculate the modular inverse?
Last fiddled with by ThiloHarich on 20051207 at 08:38
