20080902, 08:59  #1 
Aug 2006
Monza, Italy
73 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.

20080902, 10:26  #2 
Mar 2007
Austria
2×151 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 20080902 at 10:28 
20080902, 11:02  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
11026_{10} Posts 
Quote:
Paul 

20080902, 11:40  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Sigh. My message never seems to get through..... Repeat after me: Google is my friend. See: Coppersmith, HowgraveGraham, & Nagaraj Divisors in Residue Classes, Constructively Math. Comp. Jan 2008 

20080902, 12:01  #5  
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 
Quote:


20080902, 13:01  #6 
Nov 2003
1D24_{16} Posts 

20080902, 14:46  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
2^{2}·3^{2}·179 Posts 
Thanks for the interesting reference, which is a nice refinement to the LLLbased 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 ...

20080902, 14:46  #8  
Jun 2003
The Texas Hill Country
3^{2}·11^{2} Posts 
Quote:
Nor does KimberlyClark consider Kleenex a generic facial tissue. 

20080902, 15:24  #9  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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. P1, 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 stateoftheart. 

20080902, 15:27  #10  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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.... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Programming and factoring problem  lavalamp  Puzzles  112  20141005 20:37 
Problem with P1 factoring...  VolMike  Software  5  20070726 13:35 
Prime95 v24.14 P1 Factoring problem  harlee  Software  1  20061219 22:19 
Problem trial factoring + 64 bit  EPF  Hardware  2  20050626 04:12 
Factoring Problem  asdf  Puzzles  4  20030830 17:56 