View Single Post
Old 2005-12-06, 09:29   #4
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

32×11 Posts
Default

Resieving is what I actually do.
Is the QS still the best method to find the factors, even if we know that the factors have to be small?
If we have not found many factors, it makes no sense to start at sqrt (n) to find the factors.

An other question.
While sieving we have to determine a^-1 mod p, were a is the factor of the sieving polynomial (ax+b)^2 - n and p is a factor of the factor base.
I compute a^1 mod p by the extended Euclidean algorithm.
Are there faster algorithms? I heard of an unpublished paper of Richard Schroeppel. This algorithm is used in the java class BigInteger.

Back to my idea:
We can compute a^1 mod p via a^(p-2) mod p. This is only a bit slower then the extended Euclidean algorithm.
If a is 2^k then a^1 mod p = 2^k*(p-2) mod p. So we only need a fast algorithm for calculating the modulus.
In practice we need a few a's.
ThiloHarich is offline   Reply With Quote