Testing Robinson numbers for primality

The reader is assumed to be familiar with searches for Proth primes and related forms using software such as Proth.exe, Newpgen.exe, Primeform.exe, Prp.exe, Winbitwin.exe, Titanix,exe, etc.

There are a number of ways of testing a positive integer p for primality. These include :

  1. a full sieve to the root of p;
  2. variations of the p- 1 methods developed by Brillhart, Morrison and Selfridge, based on earlier results by Lucas, Proth and Pocklington, wherein p- 1 is factored completely or partially and the factors used to test for pseudoprimality.
  3. variations of the p+1 methods developed by Brillhart, Morrison and Selfridge from earlier ideas by Lucas and Lehmer.
  4. combinations of both of the previous methods.
  5. generic primality testing algorithms such as ECPP (Elliptic Curve Primality Proving), by Atkin and Morain (Titanix.exe is an implementation of this), and APR-CL (Adleman, Pomerance, Rumely, Cohen , Lenstra).

In practice, whether for finding Proth primes, primes in arithmetic progression, Cunningham chains, etc., interest will usually be in searching across large ranges of numbers of the form k*2n +1, where the p- 1 Proth test can be used. The initial search space (i.e. the entire set of numbers to be considered) is substantially restricted by using a partial sieve to a manageable limit, as it done by both Proth.exe and Newpgen.exe. These programs can be used to build lists of combinations k & n which may then be tested for pseudoprimality using Prp.exe and then primality using Proth.exe or Primeform.exe. Note that the generic algorithms are not equipped to cope with numbers of the sizes typically considered here.

I am interested in the typical number of pseudoprimality / primality tests that have to be carried out across a close range (I mean by this that values of n are approximately equal) in order to locate a prime. In particular, in searching for Keller primes, I am interested in testing a fixed and limited number of k values over given n ranges. Since Newpgen.exe is not suited to this, the alternative is to generate quickly an initial test set using a very brief sieve and then passing the output of this to Proth.exe, using the "Factors only" preference and with a fixed manual sieve limit. The idea of a fixed limit sieve is important in what follows.

Now for some theory : It is widely known (and I won't give references) that p (x), the number of primes less than or equal to x, is approximately equal to and that the likelihood that x is prime is approximately . But what if x (or p, since we are interested in primes) has already survived a sieve to a limit q ? Now, it is obvious that the proportion of integers surviving a sieve to q is s(q) = . If p has survived a sieve to q, then the likelihood that p is a prime is therefore , or where t(q) = , and the expected number of tests required in order to obtain a prime is the inverse of this. A classical result by Mertens implies that t(q) ® eg .log(q) as q ® , where g is Euler's constant, and so the value of t(q) rises logarithmically. The two tables below comparative values between the calculated value and the estimated value for a variety of key limits.

q

t(q) (calculated)

t(q) (estimated)

10

4.375

4.101

102

8.31135737892

8.202

103

12.3509756739

12.3032

104

16.4244896322

16.4043

105

20.5115928252

20.50535

106

24.6073829476

24.6064

107

28.7077703609

28.7075

108

32.808698609

32.8086

 

and

q

t(q) (calculated)

t(q) (estimated)

2

2

1.2345

22

3

2.469

23

4.375

3.7036

24

5.21354166667

4.938

25

6.54226970908

6.173

26

7.59951458813

7.4073

27

8.78222652931

8.642

28

9.96479475259

9.876

29

11.2037429513

11.1109

210

12.3997465887

12.34545

211

13.6141194455

13.58

212

14.8463264797

14.81454

213

16.0642635225

16.049

214

17.2996827618

17.2836

215

18.5252325284

18.5182

216

19.7576704153

19.7527

217

20.9920980308

20.98727

218

22.2243300099

22.1816

219

23.4592887593

23.45636

220

24.692296376

24.6909

221

25.9266589754

25.92545

222

27.1608713184

27.16

223

28.3950646914

28.39454

224

29.6294155136

29.62909

225

30.864034405

30.8636

226

32.098384759

32.09818

227

33.33284689

33.33272

 

Consider p = k*2n + 1. Then log (p) n*log(2) + log (k), and if k is small in comparison to n, then we can take log (p) n*log(2). Then the expected number of tests required on numbers surviving a sieve to q (rounding up to nearest integer) is :

q \ n

10000

20000

50000

100000

200000

105

338

676

1690

3380

6759

106

282

564

1409

2817

5634

107

242

483

1208

2415

4829

108

212

423

1057

2113

4226

 

URL : www.glasgowg43.freeserve.co.uk/survive.htm