Factors with special form

RedGolpe · 2011-11-03, 09:06

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.

R.D. Silverman · 2011-11-03, 10:16

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.

jasonp · 2011-11-03, 10:39

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

axn · 2011-11-03, 10:49

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.

RedGolpe · 2011-11-03, 15:07

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.

jasonp · 2011-11-03, 18:38

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

2011-11-03, 09:06	#1
RedGolpe Aug 2006 Monza, Italy 1001001₂ 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:39	#3
jasonp Tribal Bullet Oct 2004 3,541 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, 15:07	#5
RedGolpe Aug 2006 Monza, Italy 73 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
factoring special form of 1024-bit RSA key	Johnatan	YAFU	20	2016-04-22 04:33
Special Form of Mersenne and Fermat Number Factors	michael	Math	31	2015-09-04 05:57
Special n	kar_bon	Riesel Prime Data Collecting (k*2^n-1)	1	2009-02-19 04:28
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
Factors of the Form 7 mod 8	JuanTutors	Data	3	2004-03-29 02:31

2011-11-03, 18:38	#6
jasonp Tribal Bullet Oct 2004 3,541 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