mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-11-03, 09:06   #1
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

59 Posts
Default 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.
RedGolpe is offline   Reply With Quote
Old 2011-11-03, 10:16   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by RedGolpe View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-03, 10:39   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2011-11-03, 10:49   #4
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
axn is online now   Reply With Quote
Old 2011-11-03, 15:07   #5
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

59 Posts
Default

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
RedGolpe is offline   Reply With Quote
Old 2011-11-03, 18:38   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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
jasonp is offline   Reply With Quote
Reply

Thread Tools


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

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

Fri Sep 18 17:22:39 UTC 2020 up 8 days, 14:33, 1 user, load averages: 1.56, 1.54, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.