View Single Post
Old 2018-01-20, 16:47   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

5·181 Posts
Default

Brillhart-Lehmer-Selfridge (1975) show over 30 forms of n-1, n+1, and hybrid factoring.

It doesn't help at all with n-2 or n+2 other than to give the proofs behind lots of the n-1/n+1 methods.

These methods work quite well for small numbers (say, less than 40 digits) but suffer from scaling issues in general as once into the 100+ digit range it just takes too long for the partial factoring. It's still worth checking for easy cases. If your input is constructed then perhaps even large inputs have a known partial factorization for p-1 and/or p+1. Remember that your proof relies on the factor primality as well so for non-trivial factors you get to recurse.
danaj is offline   Reply With Quote