View Single Post
Old 2005-12-07, 08:37   #11
ThiloHarich's Avatar
Nov 2005

32×11 Posts

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 2005-12-07 at 08:38
ThiloHarich is offline   Reply With Quote