mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-06-23, 09:59   #1
mathPuzzles
 
Mar 2017

3010 Posts
Default 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!
mathPuzzles is offline   Reply With Quote
Old 2017-06-23, 11:12   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2·1,217 Posts
Default

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
firejuggler is offline   Reply With Quote
Old 2017-06-23, 11:45   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

19×101 Posts
Default

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
a1call is offline   Reply With Quote
Old 2017-06-23, 14:01   #4
axn
 
axn's Avatar
 
Jun 2003

32×523 Posts
Default

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.
axn is online now   Reply With Quote
Old 2017-06-23, 15:59   #5
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,363 Posts
Default

Quote:
Originally Posted by a1call View Post
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.
VBCurtis is offline   Reply With Quote
Old 2017-06-23, 16:22   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

19×101 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
a1call is offline   Reply With Quote
Old 2017-06-23, 16:30   #7
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×3×151 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
danaj is offline   Reply With Quote
Old 2017-06-23, 16:33   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-06-23, 18:31   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

191910 Posts
Default

Quote:
Originally Posted by danaj View Post
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
a1call is offline   Reply With Quote
Old 2017-06-24, 05:39   #10
mathPuzzles
 
Mar 2017

1E16 Posts
Default

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
mathPuzzles is offline   Reply With Quote
Old 2017-06-24, 08:41   #11
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

23×181 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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!
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Highest Prime is also a twin prime... NOT hydeer Lone Mersenne Hunters 9 2018-04-03 22:54
Twin Prime Days, Prime Day Clusters cuBerBruce Puzzles 3 2014-12-01 18:15
Twin Prime Question Unregistered Information & Answers 4 2010-09-08 13:00
Top-10 twin prime found! gd_barnes Riesel Prime Search 6 2007-10-12 18:42
Top-10 twin prime found! gd_barnes Twin Prime Search 3 2007-10-12 08:30

All times are UTC. The time now is 06:46.

Tue Oct 20 06:46:07 UTC 2020 up 40 days, 3:57, 0 users, load averages: 1.42, 1.55, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.