mersenneforum.org Factoring problem
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-02, 08:59 #1 RedGolpe     Aug 2006 Monza, Italy 1118 Posts Factoring problem I have been using ECM, ggnfs and msieve for a while and now I encountered an apparently simple problem but I found no solution. If I know the remainder of all factors of my target number modulo a certain number (which is generally the case for cyclotomic numbers), I assume that I might restrict the search and speed up the calculation (or at least the sieving, where it applies). For example, let's say I want to factor 247. With a basic sieving I should try all 6 prime numbers up to 13, but if I knew that all factors are congruent to 1 modulo 3 I'd just have to test 7 and 13, thus reducing my sieving by 3 times. In the end, if i knew that all factors are congruent to a modulo N i would expect my sieving time reduced by N times. I do not fully understand the mechanics of the various factoring methods but it seems to me that anywhere there is a sieve running (on the factors themselves or any linear combination of them), this restriction would speed up the test (I'm not sure about ECM). So, is there a way to tell the programs such a thing? If not, could it be implemented? Thank you for your time.
 2008-09-02, 10:26 #2 nuggetprime     Mar 2007 Austria 4568 Posts As I know, only trial division can benefit from that(and trial division is,on large numbers,even if you can dramatically reduce the possible factors, only suitable for finding small factors.) Last fiddled with by nuggetprime on 2008-09-02 at 10:28
2008-09-02, 11:02   #3
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

3×5×743 Posts

Quote:
 Originally Posted by nuggetprime As I know, only trial division can benefit from that(and trial division is,on large numbers,even if you can dramatically reduce the possible factors, only suitable for finding small factors.)
Fermat's method can also be speeded up. However, Fermat's method is almost always useless for factoring large integers.

Paul

2008-09-02, 11:40   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by RedGolpe I have been using ECM, ggnfs and msieve for a while and now I encountered an apparently simple problem but I found no solution. If I know the remainder of all factors of my target number modulo a certain number (which is generally the case for cyclotomic numbers), I assume that I might restrict the search such a thing?

Sigh. My message never seems to get through.....

Repeat after me:

See:
Coppersmith, Howgrave-Graham, & Nagaraj
Divisors in Residue Classes, Constructively
Math. Comp. Jan 2008

2008-09-02, 12:01   #5
Wacky

Jun 2003
The Texas Hill Country

100010000012 Posts

Quote:
 Originally Posted by R.D. Silverman My message never seems to get through..... Repeat after me: Google is my friend.
Does Steve Ballmer support your position?

2008-09-02, 13:01   #6
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by Wacky Does Steve Ballmer support your position?
"google" = "generic example for any internet search engine".

And I haven't talked with Steve face-to-face since our 10th (or was it 15th?)
reunion.

 2008-09-02, 14:46 #7 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 22×1,613 Posts Thanks for the interesting reference, which is a nice refinement to the LLL-based techniques for factoring a number given many bits of the factor, but s is definitely not >n^\alpha for \alpha>1/4 in the case the poster is interested in ...
2008-09-02, 14:46   #8
Wacky

Jun 2003
The Texas Hill Country

32×112 Posts

Quote:
 "google" = "generic example for any internet search engine".
I'm not sure that certain individuals in Mountain View, CA would agree.
Nor does Kimberly-Clark consider Kleenex a generic facial tissue.

2008-09-02, 15:24   #9
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by fivemack Thanks for the interesting reference, which is a nice refinement to the LLL-based techniques for factoring a number given many bits of the factor, but s is definitely not >n^\alpha for \alpha>1/4 in the case the poster is interested in ...
Well certainly the residue class must be large (> N^1/4) relative to the
number being factored (N) to be effectively computable. But that
issue was not raised.

And one can take advantage of a known divisor class in the cyclotomic
(e.g. P-1, P+1 etc.) methods.

However, if the known residue class is small relative to N, then it
really doesn't help very much in the current state-of-the-art.

2008-09-02, 15:27   #10
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Wacky I'm not sure that certain individuals in Mountain View, CA would agree. Nor does Kimberly-Clark consider Kleenex a generic facial tissue.
You would be correct. But it is irrelevant.

I'm sure Bayer does not consider aspirin a generic name. Or the same
for Dupont and 'teflon'. etc

But names become generic through usage as a language changes over time....

 Similar Threads Thread Thread Starter Forum Replies Last Post lavalamp Puzzles 112 2014-10-05 20:37 VolMike Software 5 2007-07-26 13:35 harlee Software 1 2006-12-19 22:19 EPF Hardware 2 2005-06-26 04:12 asdf Puzzles 4 2003-08-30 17:56

All times are UTC. The time now is 04:18.

Mon Jan 24 04:18:17 UTC 2022 up 184 days, 22:47, 0 users, load averages: 0.98, 1.16, 1.16