Twin Prime tests

[mathPuzzles]

Given N with no special form or factorization, we want to know if N-1, N+1 form a twin prime pair. Easy enough, we can just treat them as two independent tests. Trial divisions to weed out easy rejections, then use Miller Rabin test(s) on each, and use a deterministic test if they both pass the probabilistic tests and you want a proven prime.

My question is whether there is any way to somehow amortize or combine the Miller Rabin tests for the pair of very similar candidates. This is likely the same as asking if there's a clever way to compute both \(2^{n-2} \mod n-1\) and \(2^n\mod n+1\) simultaneously.

I thought first about computing something like \(r=2^{n-2}\mod {n^2}\) and then somehow "adjusting" the modular remainder by adding or subtracting \(r/n\) to \(r\mod n\), but the computation cost of a larger modular base overwhelms the savings of only having to compute one power.

So the answer is likely to "just test the two potential primes seperately" but this is the forum with the experts who live and breathe computational number theory, and I'm probably missing whole branches of techniques!

[firejuggler]

The Proof by N-1/N+1 might come in handy. It require you to factorise N to 33% to prove it is prime. Since it is for a twin prime, the factorisation would help for both.

[a1call]

Not of much help but to state the obvious for possible further elaboration:
n is coprime to both n+1 and n-1.
So if n is divisible by any numbers, then its neighbours don't need to be checked for division by them. Useful if n is a product of many factors such as is the case with Factorials, Multifactorials, primorials or any subset of them.
Additionally n-1 and n+1 can only have 2 as a cofactor, so in case of odd pairs they will be coprime.

ETA Perhaps it would make sense to compose a product of n+1 and n-1 and run primality test on the product rather than individually, skipping the expected factors.

[axn]

You don't need to combine the tests of the two candidates. In fact, you don't need to test the two candidates! Test one side. Only if it is PRP (which it will probably not be), test the other one.

[VBCurtis]

Originally Posted by a1call

ETA Perhaps it would make sense to compose a product of n+1 and n-1 and run primality test on the product rather than individually, skipping the expected factors.

Pretty sure that the product of n+1 and n-1 will fail a primality test, since it's a PRODUCT.

[a1call]

Originally Posted by VBCurtis

Pretty sure that the product of n+1 and n-1 will fail a primality test, since it's a PRODUCT.

You are way too smart, VBCurtis. Makes one wonder how you keep finding all those record primes all the time.

[danaj]

Originally Posted by VBCurtis

Pretty sure that the product of n+1 and n-1 will fail a primality test, since it's a PRODUCT.

We could channel a little less RDS and make the leap that he meant look for small factors.

[Edit: ok, it WAS a funny comment, and RDS certainly had a valid point in that people should precisely say what they mean]

[science_man_88]

Originally Posted by VBCurtis

Pretty sure that the product of n+1 and n-1 will fail a primality test, since it's a PRODUCT.

unless one of the values is 1 like in the n=2 case. giving 1*3 =3 as tot he originally suggest and the equality would be something mod n^2-1 because that's the product of n-1 and n+1. if (n-1)*x+2^(n-2)=(n+1)*y+2^n then (n-1)*x=(n+1)*y+3*2^(n-2) n being even allows us to replace it with 2*z for some value z then via pigeonhole principle one of {n-1,n,n+1} must be divisible by 3 maybe that would help in some cases. anyways mostly just babbling on.

[a1call]

Originally Posted by danaj

We could channel a little less RDS and make the leap that he meant look for small factors.

[Edit: ok, it WAS a funny comment, and RDS certainly had a valid point in that people should precisely say what they mean]

Thank you very much danaj, for having the integrity of pointing out the fact, that may (or may not) have been missed by VBCurtis.

As a measure of clarifying the concept and proving its obvious (to hopefully most) merits:

print("BRY-100-A-Twin-Primes.gp\nBy a1call")
print("An exagerated proof of concept on how primality checking of product of twin primes May be faster than checking them individually.")
#


theExp = 160;\\larger integers will enlarge random n

\\\
primorial(n)=
  {
    my(thePrimorial=1);
    forprime(p=2,n,thePrimorial=thePrimorial*p);
    return (thePrimorial);
  }
\\\



n = primorial(theExp);
n=n/(3^valuation(n,3));
n=n-1;

for(i=1,1,{
  print(factor(n),3);
  print(factor(n+2),3);
})
##
factor(n*(n+2),3)
##

BRY-100-A-Twin-Primes.gp
By a1call
An exagerated proof of concept on how primality checking of product of
twin primes May be faster than checking them individually.


   timer = 1 (on)
[161019721, 1; 687532283, 1; 1926333679, 1; 55293433823693391514403552582053037, 1]3
[3, 7; 1907718880931972625735437, 1; 2826272826347667485764205659904789, 1]3
time = 7,600 ms.
  ***   last result computed in 7,600 ms.

[3 7]

[63577830606787566004050559614704642811807861437302814363915534345301945702599892305649162589984570424655118390132351177 1]

  ***   last result computed in 0 ms.

[mathPuzzles]

a1cal, thanks for that simple and important realization that the small trial division can be sped up. Though expanding on your idea, it would be significantly faster (for multiword N) to instead trial divide just N itself by various small primes and simply look for +1 or -1 residuals. That would indeed be a 2x computation speedup. As simple as that method is, I didn't think of it, perhaps because the Rabin Miller powering dominates testing time and therefore my thinking was focused on it.

It's a shame that there's seemingly no way to boost the efficiency of that dominating modular power computation, even with such similar and simply related arguments. I was thinking some result using quadratic reciprocity would let me share the main powering computation, but that is a seeming dead end since it requires the two values to be prime.. which is the assumption we're actually testing for!

Thanks!

[Nick]

Originally Posted by mathPuzzles

It's a shame that there's seemingly no way to boost the efficiency of that dominating modular power computation, even with such similar and simply related arguments.

They are "similar and simply related" in terms of addition, not in terms of multiplication!