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

Re: Insignifcant queries about primality test performance

Expand Messages
  • 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 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);
      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.