mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-09-02, 08:59   #1
RedGolpe
 
RedGolpe's Avatar
 
Aug 2006
Monza, Italy

10010012 Posts
Default 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.
RedGolpe is offline   Reply With Quote
Old 2008-09-02, 10:26   #2
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

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
nuggetprime is offline   Reply With Quote
Old 2008-09-02, 11:02   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24·13·53 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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
xilman is offline   Reply With Quote
Old 2008-09-02, 11:40   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by RedGolpe View Post
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:

Google is my friend.


See:
Coppersmith, Howgrave-Graham, & Nagaraj
Divisors in Residue Classes, Constructively
Math. Comp. Jan 2008
R.D. Silverman is offline   Reply With Quote
Old 2008-09-02, 12:01   #5
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

108910 Posts
Default

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?
Wacky is offline   Reply With Quote
Old 2008-09-02, 13:01   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by Wacky View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2008-09-02, 14:46   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×32×179 Posts
Default

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 ...
fivemack is offline   Reply With Quote
Old 2008-09-02, 14:46   #8
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32×112 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2008-09-02, 15:24   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2008-09-02, 15:27   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Wacky View Post
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....
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Programming and factoring problem lavalamp Puzzles 112 2014-10-05 20:37
Problem with P-1 factoring... VolMike Software 5 2007-07-26 13:35
Prime95 v24.14 P-1 Factoring problem harlee Software 1 2006-12-19 22:19
Problem trial factoring + 64 bit EPF Hardware 2 2005-06-26 04:12
Factoring Problem asdf Puzzles 4 2003-08-30 17:56

All times are UTC. The time now is 23:10.


Mon Nov 29 23:10:38 UTC 2021 up 129 days, 17:39, 0 users, load averages: 1.78, 1.51, 1.39

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.