mersenneforum.org Factoring n via factors of n-1 or n+1
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-12, 21:54 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 233510 Posts Factoring n via factors of n-1 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 2018-02-12 at 22:02
2018-02-12, 22:16   #2
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by a1call Are there any such algorithms? Other than occasional hits of FLT primality test, that is. Thank you in advance
Is the list at the bottom of https://en.wikipedia.org/wiki/Euler%...ization_method what you want to avoid ? Checking if n-1 and n+1 use up all primes below sqrtint(n), is probably fruitless even at small levels.

Last fiddled with by science_man_88 on 2018-02-12 at 22:18

 2018-02-12, 22:22 #3 a1call     "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 n-1 or n+1 to find factor candidates of n?
2018-02-12, 22:35   #4
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by a1call Are there any such algorithms? Other than occasional hits of FLT primality test, that is.
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.

 2018-02-12, 22:53 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 5·467 Posts How about special forms, say subtract a 1 from you example.
2018-02-12, 22:57   #6
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by a1call How about special forms, say subtract a 1 from you example.
Then we run into above is a power of two and below is twice one less than the previous power of two.

 2018-02-13, 02:22 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 233510 Posts FWIW: Much better and more complete implantations seem possible. Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes 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**** BZS-100-A by Rashid Naimi (a1call) ****"); print("Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes 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^e-1; if(isprime(n),next(1););\\Skip prime candidates o=n-1; 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 n-1 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: **** BZS-100-A by Rashid Naimi (a1call) **** Basic Conceptual Implementation of the fact that most small Fermat-Pseudoprimes 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
2018-02-13, 02:40   #8
carpetpool

"Sam"
Nov 2016

5·67 Posts

Quote:
 Originally Posted by CRGreathouse 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.
The exponent, 57828929506774569941382167850941401232743376153559817438751 is prime, so you know that each prime dividing 2^57828929506774569941382167850941401232743376153559817438751-1 is congruent to 1 (mod 57828929506774569941382167850941401232743376153559817438751). That's useful because now you that 2^57828929506774569941382167850941401232743376153559817438751-1 has no prime factors below 5.782892e+58...

2018-02-13, 02:49   #9
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by carpetpool The exponent, 57828929506774569941382167850941401232743376153559817438751 is prime, so you know that each prime dividing 2^57828929506774569941382167850941401232743376153559817438751-1 is congruent to 1 (mod 57828929506774569941382167850941401232743376153559817438751). That's useful because now you that 2^57828929506774569941382167850941401232743376153559817438751-1 has no prime factors below 5.782892e+58...
Mr Greathouse, is refering to the statement about if factoring nearby numbers helps factor n. The problem is, if it was that easily done, it would be in use for mersenne factoring.

 2018-02-13, 03:10 #10 a1call     "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 Fermat-Pseudoprimes 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 | n-1 Which is the link between the factors of n-1 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 n-1 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 2018-02-13 at 03:30
2018-02-13, 03:45   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by a1call Again FWIW: the concept is based on the observation that just about all small Fermat-Pseudoprimes 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 | n-1 Which is the link between the factors of n-1 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 n-1 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.
Also can work with the minus 1 side though. (x-1)(xy-1) =x^2(y)-x-xy+1 also has the property x | n-1

 Similar Threads Thread Thread Starter Forum Replies Last Post UberNumberGeek Factoring 51 2017-02-13 20:30 tha Software 24 2014-06-10 23:31 Jeff Gilchrist Wagstaff PRP Search 10 2013-04-07 11:07 MatWur-S530113 PrimeNet 11 2009-01-21 19:08 AntonVrba Factoring 3 2006-02-05 06:30

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

Wed Feb 1 04:01:05 UTC 2023 up 167 days, 1:29, 0 users, load averages: 1.25, 1.17, 1.15