mersenneforum.org Factors with special form
 Register FAQ Search Today's Posts Mark Forums Read

 2011-11-03, 09:06 #1 RedGolpe     Aug 2006 Monza, Italy 748 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 GMP-ECM or GGNFS, allow this? Thank you.
2011-11-03, 10:16   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by RedGolpe 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.
?? 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).
This is just plain nonsense.

 2011-11-03, 10:39 #3 jasonp 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 case-by-case basis. Lookup-table-based methods like you suggest don't help at all Last fiddled with by jasonp on 2011-11-03 at 10:44
2011-11-03, 10:49   #4
axn

Jun 2003

469310 Posts

Quote:
 Originally Posted by jasonp Pollard Rho also can become faster for i.e. Fermat numbers, whose factors have a special form.
And P-1 and TF for mersennes and fermats and wagstaff.

 2011-11-03, 15:07 #5 RedGolpe     Aug 2006 Monza, Italy 3C16 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=|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. Last fiddled with by RedGolpe on 2011-11-03 at 15:15
 2011-11-03, 18:38 #6 jasonp Tribal Bullet     Oct 2004 1101110010012 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Johnatan YAFU 20 2016-04-22 04:33 michael Math 31 2015-09-04 05:57 kar_bon Riesel Prime Data Collecting (k*2^n-1) 1 2009-02-19 04:28 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 JuanTutors Data 3 2004-03-29 02:31

All times are UTC. The time now is 16:17.

Sun Sep 20 16:17:04 UTC 2020 up 10 days, 13:28, 1 user, load averages: 1.34, 1.27, 1.25