20170623, 09:59  #1 
Mar 2017
2·3·5 Posts 
Twin Prime tests
Given N with no special form or factorization, we want to know if N1, 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^{n2} \mod n1\) and \(2^n\mod n+1\) simultaneously. I thought first about computing something like \(r=2^{n2}\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! 
20170623, 11:12  #2 
Apr 2010
Over the rainbow
3·11·73 Posts 
The Proof by N1/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.
Last fiddled with by firejuggler on 20170623 at 11:14 
20170623, 11:45  #3 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}×3×79 Posts 
Not of much help but to state the obvious for possible further elaboration:
n is coprime to both n+1 and n1. 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 n1 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 n1 and run primality test on the product rather than individually, skipping the expected factors. Last fiddled with by a1call on 20170623 at 11:56 
20170623, 14:01  #4 
Jun 2003
11125_{8} Posts 
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.

20170623, 15:59  #5 
"Curtis"
Feb 2005
Riverside, CA
2·3·719 Posts 

20170623, 16:22  #6 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}·3·79 Posts 

20170623, 16:30  #7  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
5·181 Posts 
Quote:
[Edit: ok, it WAS a funny comment, and RDS certainly had a valid point in that people should precisely say what they mean] Last fiddled with by danaj on 20170623 at 16:36 

20170623, 16:33  #8 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
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^21 because that's the product of n1 and n+1. if (n1)*x+2^(n2)=(n+1)*y+2^n then (n1)*x=(n+1)*y+3*2^(n2) n being even allows us to replace it with 2*z for some value z then via pigeonhole principle one of {n1,n,n+1} must be divisible by 3 maybe that would help in some cases. anyways mostly just babbling on.
Last fiddled with by science_man_88 on 20170623 at 16:34 
20170623, 18:31  #9  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{3}×3×79 Posts 
Quote:
As a measure of clarifying the concept and proving its obvious (to hopefully most) merits: Code:
print("BRY100ATwinPrimes.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=n1; for(i=1,1,{ print(factor(n),3); print(factor(n+2),3); }) ## factor(n*(n+2),3) ## Code:
BRY100ATwinPrimes.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. Last fiddled with by a1call on 20170623 at 18:33 

20170624, 05:39  #10 
Mar 2017
36_{8} Posts 
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! Last fiddled with by mathPuzzles on 20170624 at 05:39 
20170624, 08:41  #11 
Dec 2012
The Netherlands
2^{2}×359 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Highest Prime is also a twin prime... NOT  hydeer  Lone Mersenne Hunters  9  20180403 22:54 
Twin Prime Days, Prime Day Clusters  cuBerBruce  Puzzles  3  20141201 18:15 
Twin Prime Question  Unregistered  Information & Answers  4  20100908 13:00 
Top10 twin prime found!  gd_barnes  Riesel Prime Search  6  20071012 18:42 
Top10 twin prime found!  gd_barnes  Twin Prime Search  3  20071012 08:30 