## Re: Insignifcant queries about primality test performance

Expand Messages
• ... I hope that my ulterior motive for asking these questions was not too obvious; I have a new primality/factoring idea written in Pascal, running on a
Message 1 of 5 , Dec 12, 2010
--- 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.
> > >
> >
> > 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
>

I hope that my ulterior motive for asking these questions
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);
{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');
end
else if ch = '4' then
begin
h3 := 1; h4 := 3163073;{14}
h18 := 1.000504e13;
h40 := 1e13;
writeln('17 seconds for 52752 primes');
end
else if ch = '5' then
begin
h3 := 1; h4 := 10000073;{15}
h18 := 1.000015e14;
h40 := 1e14;
writeln('57 seconds for 155240 primes');
end
else if ch = '6' then
begin
h3 := 1; h4 := 31630073;{16}
h18 := 1.0004616e15;{}
h40 := 1e15;
writeln('199 seconds for 458234 primes');
end
else if ch = '7' then
begin
h3 := 1; h4 := 100000073;{17}
h18 := 1.0000015e16;{}
h40 := 1e16;
writeln('680 seconds for 1356045 primes');
end
else if ch = '8' then
begin
h3 := 1; h4 := 316300073;{18}
h18 := 1.0004573744e17;{}
h40 := 1e17;
writeln('2220 seconds for 4037523 primes');
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