mersenneforum.org > Math Twin Prime tests
 Register FAQ Search Today's Posts Mark Forums Read

 2017-06-23, 09:59 #1 mathPuzzles   Mar 2017 3010 Posts Twin Prime tests 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!
 2017-06-23, 11:12 #2 firejuggler     Apr 2010 Over the rainbow 2·1,237 Posts 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. Last fiddled with by firejuggler on 2017-06-23 at 11:14
 2017-06-23, 11:45 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 79A16 Posts 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. Last fiddled with by a1call on 2017-06-23 at 11:56
 2017-06-23, 14:01 #4 axn     Jun 2003 22×5×239 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.
2017-06-23, 15:59   #5
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

106058 Posts

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

2017-06-23, 16:22   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2·7·139 Posts

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

2017-06-23, 16:30   #7
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts

Quote:
 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]

Last fiddled with by danaj on 2017-06-23 at 16:36

2017-06-23, 16:33   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 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 $2^{n-2} \pmod {n-1}$ and $2^n \pmod {n+1}$ 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.

Last fiddled with by science_man_88 on 2017-06-23 at 16:34

2017-06-23, 18:31   #9
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

194610 Posts

Quote:
 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:

Code:
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)
##
Code:
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.

Last fiddled with by a1call on 2017-06-23 at 18:33

 2017-06-24, 05:39 #10 mathPuzzles   Mar 2017 2·3·5 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 2017-06-24 at 05:39
2017-06-24, 08:41   #11
Nick

Dec 2012
The Netherlands

2×751 Posts

Quote:
 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post hydeer Lone Mersenne Hunters 9 2018-04-03 22:54 cuBerBruce Puzzles 3 2014-12-01 18:15 Unregistered Information & Answers 4 2010-09-08 13:00 gd_barnes Riesel Prime Search 6 2007-10-12 18:42 gd_barnes Twin Prime Search 3 2007-10-12 08:30

All times are UTC. The time now is 17:31.

Sat Nov 28 17:31:57 UTC 2020 up 79 days, 14:42, 4 users, load averages: 2.35, 1.97, 1.74