Loading ...
Sorry, an error occurred while loading the content.

Insignifcant queries about primality test performance

Expand Messages
  • Aldrich
    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
    Message 1 of 5 , Dec 11, 2010
    • 0 Attachment
      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
    • maximilian_hasler
      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
      Message 2 of 5 , Dec 11, 2010
      • 0 Attachment
        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
        >
      • Aldrich
        ... What type of primality test does the PARI program use? a.
        Message 3 of 5 , Dec 12, 2010
        • 0 Attachment
          > --- 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.
        • maximilian_hasler
          ... The Baillie-Pomerance-Selfridge-Wagstaff pseudo prime test: strong Rabin-Miller pseudo primality for base 2, followed by strong Lucas test for the
          Message 4 of 5 , Dec 12, 2010
          • 0 Attachment
            > > 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
          • Aldrich
            ... 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 5 of 5 , Dec 12, 2010
            • 0 Attachment
              --- 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);
              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.
            Your message has been successfully submitted and would be delivered to recipients shortly.