Factors with special form
 

Sometimes when factoring a number N we already know the remainder of its factors modulo some n. When using older methods, like a simple sieve or Fermat, this clearly speeds up the process n times. One would think that the difficulty of the general factorization problem improves from log(N) to log(N)-log(n).

Is it possible to use this information on, say, ECM or NFS? If so, can someone point me to the relevant resources, or let me know if current implementations of said methods, like GMP-ECM or GGNFS, allow this? Thank you.

[QUOTE=RedGolpe;276981]Sometimes when factoring a number N we already know the remainder of its factors modulo some n. When using older methods, like a simple sieve or Fermat, this clearly speeds up the process n times.
[/QUOTE]

?? I think you are confused.

[QUOTE]
One would think that the difficulty of the general factorization problem improves from log(N) to log(N)-log(n).
[/QUOTE]

This is just plain nonsense.

Pollard Rho also can become faster for i.e. Fermat numbers, whose factors have a special form. However, the advanced factoring methods do not improve based upon the assumed form of the factors of N. If you know an actual factor of N, then dividing it out will change the polynomials used in the special number field sieve so that the result runs faster sometimes, but this will only help on a case-by-case basis. Lookup-table-based methods like you suggest don't help at all

[QUOTE=jasonp;276985]Pollard Rho also can become faster for i.e. Fermat numbers, whose factors have a special form. [/QUOTE]
And P-1 and TF for mersennes and fermats and wagstaff.

I obviously didn't make myself clear, so I'll try with an example. Let's take the 37th Fibonacci number, 24157817. We know that at least one of its factors (say, x) is congruent to -1 (mod 37). As the cofactor y must be congruent to 1 (mod 37), using Fermat's factorization method (nothing to do with Fermat numbers), we obviously have to test only squares b^2=|y-x|/2 congruent to 1 (mod 37), so b=+/-1 (mod 37) and the process is 37/2 times faster than to test all of them.

If this is just plain wrong, I would like to understand why anyway.

You're not wrong, but other factoring methods cannot benefit from this kind of information. Basically this is a solution to the problem of recognizing when an integer is a square, but Fermat's method can only use this because it's linearly searching for numbers that are squares already. QS doesn't care about finding squares, it will construct them mod N