- How long would it take to find 1000000 eighteen digit probable primes

using the best primality tests or combinations thereof now available?

What percentage of these would be expected to be psuedo-primes ?

Aldrich - In PARI it takes 1.6 sec (on my laptop from 2005) to find the first 10^4 18 digit primes.

I am ready to bet anything you want that even in the first 10^6 pseudoprimes you'd find this way in about 150 sec. there is no composite.

M.

--- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@...> wrote:

>

>

>

> How long would it take to find 1000000 eighteen digit probable primes

> using the best primality tests or combinations thereof now available?

> What percentage of these would be expected to be psuedo-primes ?

>

> Aldrich

> > --- In primenumbers@yahoogroups.com, "Aldrich" <aldrich617@> wrote:

> >

> >

> >

> > How long would it take to find 1000000 eighteen digit probable primes

> > using the best primality tests or combinations thereof now available?

> > What percentage of these would be expected to be psuedo-primes ?

> >

> > Aldrich

--- In primenumbers@yahoogroups.com, "maximilian_hasler" <maximilian.hasler@...> wrote:

>

> In PARI it takes 1.6 sec (on my laptop from 2005) to find the first 10^4 18 digit primes.

>

> I am ready to bet anything you want that even in the first 10^6 pseudoprimes you'd find this way in about 150 sec. there is no composite.

>

> M.

What type of primality test does the PARI program use?

a.> > In PARI it takes 1.6 sec (on my laptop from 2005) to find the first 10^4 18 digit primes.

The Baillie-Pomerance-Selfridge-Wagstaff pseudo prime test:

> >

> > I am ready to bet anything you want that even in the first 10^6 pseudoprimes you'd find this way in about 150 sec. there is no composite.

> >

>

> What type of primality test does the PARI program use?

strong Rabin-Miller pseudo primality for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that P^2 - 4 is not a square mod x).

Maximilian- --- In primenumbers@yahoogroups.com, "maximilian_hasler" <maximilian.hasler@...> wrote:
>

I hope that my ulterior motive for asking these questions

>

> > > In PARI it takes 1.6 sec (on my laptop from 2005) to find the first 10^4 18 digit primes.

> > >

> > > I am ready to bet anything you want that even in the first 10^6 pseudoprimes you'd find this way in about 150 sec. there is no composite.

> > >

> >

> > What type of primality test does the PARI program use?

>

>

> The Baillie-Pomerance-Selfridge-Wagstaff pseudo prime test:

> strong Rabin-Miller pseudo primality for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that P^2 - 4 is not a square mod x).

>

>

> Maximilian

>

was not too obvious; I have a new primality/factoring

idea written in Pascal, running on a Pentium3 that seems

pretty good, as it produces no psuedo-primes.

If your figures are accurate, then the PARI

program run on a recent machine is only 3-4 times faster,

at least for 18 digit integers, and I find that encouraging.

I will look for a tutor so that I may see how fast a

PARI translation of the idea will run.

The idea is very simple in concept, and it is somewhat

perplexing that no one seems to have found it before.

Has no one ever looked at the lowest 36 values for

A = 5x^2 + 5xy + y^2 (A < 211)? I am sure that

aftcionados of Fortran will hate the program below,

especially if it works as advertized, but really, in some

ways Pascal is still the best.

__

{This Pascal program quickly finds large numbers of primes

appearing as values of A = 5x^2 + 5xy + y^2 and is based

upon the observation that primes and squares of primes ending

in one or nine with GCD(A,y) = 1 will appear only once as values

of A whereas composites ending in one or nine with

GCD(A,y) > 1 will appear more than once. A simple

stepwise iteration and storage system finds and records eligible

integers, and the composites among them are eliminated when

they appear a second time. An eligible integer, besides being

+/- 1 mod 10, must also fall within the well-defined interval

being examined . This method will

work with minor adjustments for A values ocurring in intervals

of any size, and in fact is only one of many million of similar

patterns. This particular prime mine variant generates only

primes that end in one. As a primality test, it has not yet

been proven to be valid, although it certainly appears to be.}

{$N+}{E+}

Program PRIMEMINE (input, output);

uses wincrt;

type

numptr = ^number;

number = record

next : array[0..64000] of shortint;

end;

frame = array[0..999] of numptr;

var

h1,h2,h3,h4,h18,h30,h31,h40 : extended;

bo1,bool : boolean;

i,j,b11 : integer;

fr : frame;

w: longint;

ch : char;

Procedure bigsieve;

{This procedure initializes the pointer

variable arrays that will store eligible

prime candidates and record the number

of times that they occur}

var i,j : integer;

a : longint;

begin

for i := 0 to 999 do

new(fr[i]);

for i := 0 to 999 do

for a := 0 to 64000 do

begin

fr[i]^.next[a] := 0;

end;

writeln(' nnn');

end;

Procedure gcd1;

{This procedure finds the greatest common

denominator of A and y}

var

c,hqf1, hqf2,r,s,t : extended;

begin

bo1 := false;

r := 2;

hqf1 := h2;

hqf2 := h4;

If hqf1 <> hqf2 then

begin

While r > 1 do {}

begin

c := hqf1/hqf2;

s := trunc(c/1e9)*1e9;

t := c - s;

s := s + trunc(t);

r := hqf1 - s*hqf2;

hqf1 := hqf2; hqf2 := r;

end;

end;

if r = 0 then

begin

{writeln(' gcd ',hqf1); }

bo1 := true;

end;

b11 := trunc(r);

end;

procedure sieveT;

{This procedure filters out ineligible integers and

does the actual recording and counting of those

remaining}

var

g1,g2,g11 : longint;

begin

if h2 < h31 then

if h2 > h30 then

begin

if trunc(h2-h18) mod 10 = 1 then

begin

gcd1;{}

if not bo1 then

begin

w := w + 1;

g11 := trunc(h2-h18) div 10;

g1 := g11 mod 64000;

g2 := g11 div 64000;

fr[g2]^.next[g1] := fr[g2]^.next[g1] + 1;

if fr[g2]^.next[g1] > 1 then w := w - 1;

if fr[g2]^.next[g1] = 2 then w := w - 1;

end

end ;

end;{}

end;

procedure sieveT2;

{This procedure displays the primes found after

the program has gone through the entire interval.

There can be no valid results until the entire interval

has been traversed}

var

g,g1,g2 : longint;

z : extended;

begin

writeln('SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS');

g := 0;

for g2 := 0 to 999 do

for g1 := 0 to 64000 do

begin

if fr[g2]^.next[g1] = 1 then

begin

g := g + 1;

z := (g2*64000 +g1)*10 + 1;

z := z + h18; {}

write(trunc(z/1e9));

if trunc(z - trunc(z/1e9)*1e9) < 100000000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 10000000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 1000000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 100000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 10000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 1000 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 100 then write('0');

if trunc(z - trunc(z/1e9)*1e9) < 10 then write('0');

write(trunc(z - trunc(z/1e9)*1e9));

writeln;

writeln(' Prime # ',g,' of ',w);

readln;

{if g mod 10000 =1 then readln;{}

end;

end;

end;

procedure initby10;

{This procedure gives the user the choice of narrow

bands of six typical intervals to examine for primes.

It also calculates the permissible upper and lower

bounds of these bands that will filter out unusable

values of A.}

begin

if ch = '3' then

begin

h3 := 1; h4 := 1000073;{13}

h18 := 1.00015e12;{}

h40 := 1e12;

writeln('5 seconds for 18086 primes');

readln;

end

else if ch = '4' then

begin

h3 := 1; h4 := 3163073;{14}

h18 := 1.000504e13;

h40 := 1e13;

writeln('17 seconds for 52752 primes');

readln;

end

else if ch = '5' then

begin

h3 := 1; h4 := 10000073;{15}

h18 := 1.000015e14;

h40 := 1e14;

writeln('57 seconds for 155240 primes');

readln;

end

else if ch = '6' then

begin

h3 := 1; h4 := 31630073;{16}

h18 := 1.0004616e15;{}

h40 := 1e15;

writeln('199 seconds for 458234 primes');

readln;

end

else if ch = '7' then

begin

h3 := 1; h4 := 100000073;{17}

h18 := 1.0000015e16;{}

h40 := 1e16;

writeln('680 seconds for 1356045 primes');

readln;

end

else if ch = '8' then

begin

h3 := 1; h4 := 316300073;{18}

h18 := 1.0004573744e17;{}

h40 := 1e17;

writeln('2220 seconds for 4037523 primes');

readln;

end;

h1 := 5*h3*h3 + 5*h3*h4 + h4*h4;

h2 := 5*h3*h3 + 5*h3*(h4-1) + (h4-1)*(h4-1);

h30 := h1 -(h1 -h2)/2;

h31 := h1 +(h1 -h2)/2;

end;

procedure by10s2;

{This procedure is a stepwise iteration of A

values that will find all the eligible primes and

composites within the calculated boundries}

begin

h2 := 5*h3*h3 + 5*h3*h4 + h4*h4;

b11 := 0;

repeat

h3 := h3 + 1;

h4 := h4 -3;

h2 := 5*h3*h3 + 5*h3*h4 + h4*h4;

sieveT;

h3 := h3 + 1;

h4 := h4 -2;

h2 := 5*h3*h3 + 5*h3*h4 + h4*h4;

sieveT;

if h2 < h30 then

begin

h3 := h3 + 1;

h2 := 5*h3*h3 + 5*h3*h4 + h4*h4;

sieveT;

end;

until h4 < 3;

end;

BEGIN {TOP}

bigsieve;;

writeln('Type in the number of digits you wish ');

writeln('your sample prime mine to have. The choices');

writeln('are limited to 13, 14, 15, 16, 17 and 18');

writeln;

repeat

read(ch);

until (ch = '3') or (ch = '4') or (ch = '5')

or (ch = '6') or (ch = '7') or (ch = '8') ;

writeln('You chose 1',ch,' digits. Your wait time should be about');

initby10;

writeln;

h4 := h4 + 1;

by10s2;

sieveT2;{}

END.