20180212, 21:54  #1 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2335_{10} Posts 
Factoring n via factors of n1 or n+1
Are there any such algorithms?
Other than occasional hits of FLT primality test, that is. Thank you in advance Last fiddled with by a1call on 20180212 at 22:02 
20180212, 22:16  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Last fiddled with by science_man_88 on 20180212 at 22:18 

20180212, 22:22  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5×467 Posts 
Very interesting concept, regardless.
But that's not what I had in mind. Are there any algorithms that use known factors of n1 or n+1 to find factor candidates of n? 
20180212, 22:35  #4 
Aug 2006
5,987 Posts 
It doesn't seem likely. I know all the factors of 2^57828929506774569941382167850941401232743376153559817438751 but that doesn't help me find factors of the number just below it.

20180212, 22:53  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5·467 Posts 
How about special forms, say subtract a 1 from you example.

20180212, 22:57  #6 
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 

20180213, 02:22  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2335_{10} Posts 
FWIW:
Much better and more complete implantations seem possible. Basic Conceptual Implementation of the fact that most small FermatPseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor. Example: 341 = 11 x 31 = (10 + 1) x (3 x 10) +1 https://en.wikipedia.org/wiki/Fermat...Factorizations Code:
print("\n**** BZS100A by Rashid Naimi (a1call) ****"); print("Basic Conceptual Implementation of the fact that most small FermatPseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor."); print("Example:\n341 = 11 x 31 = (10 + 1) x (3 x 10) +1"); print("https://en.wikipedia.org/wiki/Fermat_pseudoprime#Factorizations"); allocatemem(19^8); forstep(e=3,19^4,2,{ n=2^e1; if(isprime(n),next(1););\\Skip prime candidates o=n1; for(i=0,19^1,\\Increase this range for larger Exponents e \\print("i ",i); fordiv(o, g, \\ Only useful if all prime factors of n1 are known gg=2^i*g+1;\\print("gg ",gg); k= lift(Mod(n,gg)); if((k == 0) && ((gg) != n), print("\n***** 2^",e,"  1 is divisible by:";); print("**** ",g+1); next(3); ); ); ); print("\n***** 2^",e,"  1";); print("No factor found."); \\next(19); }) Code:
**** BZS100A by Rashid Naimi (a1call) **** Basic Conceptual Implementation of the fact that most small FermatPseudoprimes have factors which are 1 greater than integer multiples of 1 less than their smallest factor. Example: 341 = 11 x 31 = (10 + 1) x (3 x 10) +1 https://en.wikipedia.org/wiki/Fermat_pseudoprime#Factorizations ***** 2^9  1 is divisible by: **** 7 ***** 2^11  1 is divisible by: **** 23 ***** 2^15  1 is divisible by: **** 7 ***** 2^21  1 is divisible by: **** 7 ***** 2^23  1 is divisible by: **** 47 ***** 2^25  1 is divisible by: **** 31 ***** 2^27  1 is divisible by: **** 7 ***** 2^29  1 is divisible by: **** 59 ***** 2^33  1 is divisible by: **** 7 ***** 2^35  1 No factor found. ***** 2^37  1 is divisible by: **** 223 ***** 2^39  1 is divisible by: **** 7 ***** 2^41  1 No factor found. ***** 2^43  1 No factor found. ***** 2^45  1 is divisible by: **** 7 ***** 2^47  1 is divisible by: **** 283 ***** 2^49  1 is divisible by: **** 127 ***** 2^51  1 is divisible by: **** 7 ***** 2^53  1 is divisible by: **** 1591 ***** 2^55  1 No factor found. ***** 2^57  1 is divisible by: **** 7 ***** 2^59  1 No factor found. ***** 2^63  1 is divisible by: **** 7 ***** 2^65  1 is divisible by: **** 31 ***** 2^67  1 No factor found. ***** 2^69  1 is divisible by: **** 7 ***** 2^71  1 No factor found. ***** 2^73  1 is divisible by: **** 439 ***** 2^75  1 is divisible by: **** 7 ***** 2^77  1 No factor found. ***** 2^79  1 No factor found. ***** 2^81  1 is divisible by: **** 7 ***** 2^83  1 is divisible by: **** 167 ***** 2^85  1 is divisible by: **** 31 ***** 2^87  1 is divisible by: **** 7 ***** 2^91  1 is divisible by: **** 127 ***** 2^93  1 is divisible by: **** 7 ***** 2^95  1 No factor found. ***** 2^97  1 No factor found. ***** 2^99  1 is divisible by: **** 7 ***** 2^101  1 No factor found. ***** 2^103  1 No factor found. ***** 2^105  1 is divisible by: **** 7 ***** 2^109  1 No factor found. ***** 2^111  1 is divisible by: **** 7 ***** 2^113  1 is divisible by: **** 3391 ***** 2^115  1 No factor found. ***** 2^117  1 is divisible by: **** 7 ***** 2^119  1 No factor found. ***** 2^121  1 is divisible by: **** 23 ***** 2^123  1 is divisible by: **** 7 ***** 2^125  1 is divisible by: **** 31 ***** 2^129  1 is divisible by: **** 7 ***** 2^131  1 is divisible by: **** 263 ***** 2^133  1 is divisible by: **** 127 ***** 2^135  1 is divisible by: **** 7 ***** 2^137  1 No factor found. ***** 2^139  1 No factor found. ***** 2^141  1 is divisible by: **** 7 ***** 2^143  1 No factor found. ***** 2^145  1 is divisible by: **** 31 ***** 2^147  1 is divisible by: **** 7 ***** 2^149  1 No factor found. ***** 2^151  1 No factor found. ***** 2^153  1 is divisible by: **** 7 ***** 2^155  1 No factor found. ***** 2^157  1 No factor found. ***** 2^159  1 is divisible by: **** 7 ***** 2^161  1 No factor found. ***** 2^163  1 No factor found. ***** 2^165  1 is divisible by: **** 7 ***** 2^167  1 No factor found. ***** 2^169  1 is divisible by: **** 8191 ***** 2^171  1 is divisible by: **** 7 ***** 2^173  1 No factor found. ***** 2^175  1 is divisible by: **** 127 ***** 2^177  1 is divisible by: **** 7 ***** 2^179  1 is divisible by: **** 359 ***** 2^181  1 is divisible by: **** 5431 ***** 2^183  1 is divisible by: **** 7 ***** 2^185  1 is divisible by: **** 31 ***** 2^187  1 No factor found. ***** 2^189  1 is divisible by: **** 7 ***** 2^191  1 is divisible by: **** 383 ***** 2^193  1 No factor found. ***** 2^195  1 is divisible by: **** 7 ***** 2^197  1 No factor found. ***** 2^199  1 No factor found. ***** 2^201  1 is divisible by: **** 7 ***** 2^203  1 No factor found. ***** 2^205  1 is divisible by: **** 31 ***** 2^207  1 is divisible by: **** 7 ***** 2^209  1 No factor found. ***** 2^211  1 is divisible by: **** 3799 ***** 2^213  1 is divisible by: **** 7 ***** 2^215  1 No factor found. ***** 2^217  1 is divisible by: **** 127 ***** 2^219  1 is divisible by: **** 7 ***** 2^221  1 No factor found. ***** 2^223  1 No factor found. ***** 2^225  1 is divisible by: **** 7 ***** 2^227  1 No factor found. ***** 2^229  1 No factor found. ***** 2^231  1 is divisible by: **** 7 ***** 2^233  1 is divisible by: **** 1399 ***** 2^235  1 No factor found. ***** 2^237  1 is divisible by: **** 7 ***** 2^239  1 is divisible by: **** 479 ***** 2^241  1 No factor found. ***** 2^243  1 is divisible by: **** 7 ***** 2^245  1 is divisible by: **** 31 ***** 2^247  1 No factor found. ***** 2^249  1 is divisible by: **** 7 ***** 2^251  1 is divisible by: **** 503 ***** 2^253  1 is divisible by: **** 271 ***** 2^255  1 is divisible by: **** 7 ***** 2^257  1 No factor found. ***** 2^259  1 is divisible by: **** 127 ***** 2^261  1 is divisible by: **** 7 
20180213, 02:40  #8 
"Sam"
Nov 2016
5·67 Posts 
The exponent, 57828929506774569941382167850941401232743376153559817438751 is prime, so you know that each prime dividing 2^578289295067745699413821678509414012327433761535598174387511 is congruent to 1 (mod 57828929506774569941382167850941401232743376153559817438751). That's useful because now you that 2^578289295067745699413821678509414012327433761535598174387511 has no prime factors below 5.782892e+58...

20180213, 02:49  #9  
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
Quote:


20180213, 03:10  #10 
"Rashid Naimi"
Oct 2015
Remote to Here/There
5×467 Posts 
Again FWIW:
the concept is based on the observation that just about all small FermatPseudoprimes have factors of the form: n = (x+1)(xy+1) ... The pattern gets more complex for larger numbers but the basic characteristic is usually still present, But higher orders of some of the prime factors of the smallest factor combine to produce the other factors. In it's basic form: n = (x+1)(xy+1) = x2y+x+xy+1 = x(xy+1+y)+1 => x  n1 Which is the link between the factors of n1 and the factors of n. This is a Theoretical concept and the application is still tentative to the caveat that all of the prime factors of n1 need to be known, This is often not the case with Merssene Pseudoprimes. So it does not have a practical application for factoring Merssene Pseudoprimes. Last fiddled with by a1call on 20180213 at 03:30 
20180213, 03:45  #11  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
P1 factoring attempts at smallestremaining Mersenne numbers with no known factors  UberNumberGeek  Factoring  51  20170213 20:30 
option for finding multiple factors during trial factoring  tha  Software  24  20140610 23:31 
Big factors  Jeff Gilchrist  Wagstaff PRP Search  10  20130407 11:07 
Missing factors at the 'Known Factors' page  MatWurS530113  PrimeNet  11  20090121 19:08 
Factoring of composites with near factors  request for data  AntonVrba  Factoring  3  20060205 06:30 