20111103, 09:06  #1 
Aug 2006
Monza, Italy
74_{8} Posts 
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 GMPECM or GGNFS, allow this? Thank you. 
20111103, 10:16  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Quote:


20111103, 10:39  #3 
Tribal Bullet
Oct 2004
3,529 Posts 
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 casebycase basis. Lookuptablebased methods like you suggest don't help at all
Last fiddled with by jasonp on 20111103 at 10:44 
20111103, 10:49  #4 
Jun 2003
4693_{10} Posts 

20111103, 15:07  #5 
Aug 2006
Monza, Italy
3C_{16} Posts 
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=yx/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. Last fiddled with by RedGolpe on 20111103 at 15:15 
20111103, 18:38  #6 
Tribal Bullet
Oct 2004
110111001001_{2} Posts 
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

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factoring special form of 1024bit RSA key  Johnatan  YAFU  20  20160422 04:33 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
Special n  kar_bon  Riesel Prime Data Collecting (k*2^n1)  1  20090219 04:28 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
Factors of the Form 7 mod 8  JuanTutors  Data  3  20040329 02:31 