Factoring n via factors of n-1 or n+1

[a1call]

Are there any such algorithms?
Other than occasional hits of FLT primality test, that is.
Thank you in advance

[science_man_88]

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.

[a1call]

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?

[CRGreathouse]

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.

[a1call]

How about special forms, say subtract a 1 from you example.

[science_man_88]

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.

[a1call]

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

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);
})

**** 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

[carpetpool]

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...

[science_man_88]

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.

[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.

[science_man_88]

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