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

Factoring with Issquare Sieves

Expand Messages
  • aldrich617
    I believe that it is possible to use the first conjecture from CONTEST++ as a starting point for a new factoring method, and that even if it is found to be not
    Message 1 of 1 , Dec 25, 2007
    • 0 Attachment
      I believe that it is possible to use the first
      conjecture from CONTEST++
      as a starting point for a new factoring method, and
      that even if it is found to be not always true, the
      method itself
      may still be of interest:

      (x,A,B,c,k,f : integers)
      Let A = 20x^2 + 10x + 1;
      Let B = 10x^2 + 4x + 1;
      Let c = trunc(A/sqrt(5)) - 1;

      For any x > 0, apply the issquare test to each k
      in the interval c <= k < B.
      If there exists a value of k that satisfies the
      conditions of the test, then A is composite,
      and there will be at least one value of k such
      that 2*k - 1 will have a factor in A.
      (issquare test: 0 < 5*(2*k -1)^2 - 4*A^2 = f^2)

      If we are to have any hope of finding factors for large
      A(x) = 20x^2 + 10x + 1 even in this small interval
      by means of the issquare test, a faster
      search algorithm than
      issquare itself needs to be developed, and I think that
      a small two-dimensional initiating sieve array
      mapped onto a large one-dimensional array representing
      the interval A(x)/sqrt(5)-1 to 10x^2 + 4x + 1 or some
      portion of it
      may be a plausable data structure{see the program
      at bottom of page}
      for accomplishing this goal. Success would greatly
      depend on the technical aspects
      of state-of–the-art sieve construction and manipulation -
      qualities that
      my primitive first effort here do not reflect, but
      I am hoping that perhaps the group can help
      with some real expertise in these matters. I do know
      that several variants of sieve will eliminate all
      invalid k if they can be made
      sufficiently large – the functional equivalent of
      using issquare to
      test every k across an interval - and that ways exist
      that can improve
      performance of algorithms by using several
      sieves simultaneously.
      My program has so much redundancy of computation,
      however, that
      it can in no way be considered the desired solution
      without drastic
      revision. Perhaps there is fortunately available
      some advanced
      techniques of variable
      simplification that may be able to rework it into
      a much more efficient form.
      The complete program at the end of this discussion,
      written
      in ancient Pascal , is merely meant to illustrate
      the principles of the issquare
      sieve in a basic comprehensible manner, and
      though the code is executable as is, to
      actually run the program requires that it be
      somehow imported
      into a compatible programming environment.

      To begin the demonstration of simple sieve
      construction
      we start with an amalgam of two variants of sieve
      that will
      give us the smallest possible data structure for
      twenty-four elements. Let Q = the product of
      3,7,13,17,23,37,43,47,53,67,73,83,97,11,19,29,31,
      41,59,61,71,79,89,101,
      which is the size of the interval that
      could be covered mod Q, and is equal to about
      2.33 * 10^37.
      Its advantage, if buildable, over the usual issquare
      test is that it is repeatable
      without any further modification, as many times
      as necessary mod Q.
      It would be a very sparse array and tests indicate
      an error rate of about 1 in 5000000 for the
      demo program,
      values that would need to be checked by the regular
      issquare test or GCD. A few changes to the
      demo program
      could lower the error rate to at least 1 in 10^7,
      but would add a bit more computation time. Of course
      our demo test number is tiny, and the program makes
      no errors for a number that small.

      For the demo choose x = 46 on 31 101 211...
      so that A = 42781 ,
      with k starting at 19132, and I = 10 * k =191320,
      and S = A^2 + I = 42781^2 + 191320. If S is evenly
      divisible by any of the twenty-four elements the
      results will be
      recorded at location #1 on the two-dimensional sieve.
      At the same
      location we check to see which of the elements
      are a factor
      of S + I + I+ 10, S(x) + I+ I + 10 + I + 20 etc.
      for (101 + 1)/2 iterations..
      We find 17,23,37,73,83,19,29,59,61,71,79 and 101 are
      all found on location #1 of the sieve, and each of
      these will
      repeat at regular intervals at higher locations:
      17 at 1 + 17*m, 23 at 1 + 23*m,
      37 at 1 + 37*m, 73 at 1 + 73*m, 83 at 1 + 83*m ,
      19 at 1 + 19*m etc.

      For sieve location #2 we start with
      S = A^2 + I = 42781^2 + 191330
      and repeat the process, thus finding factors
      3,13,23,37,43,47,67,97,11,29,41,61,79 which
      will similarly
      repeat at higher locations. We continue the
      initialization process
      until location #101, the maximum element size.
      The results
      of the initialization process are shown in the
      first part of the program.
      For all elements E = +/- 3 mod 10, the locations
      L + E * m are
      mapped onto the one-dimensional array and are
      eliminated as
      valid values for k ; this is the exclusion sieve
      concept. For all
      elements E = +/- 1 mod 10 the locations L + E * m
      are mapped
      onto the one-dimensional array at any value not
      already eliminated as possibility by the exclusion
      sieve and remain
      possible only if the array value there is covered
      by all eleven
      E = +/- 1 mod 10 elements.
      These are the only candidates left for satifying
      the conditions of the
      issquare test, and are the only values of k
      such that 2k -1 may have a common factor in A.
      For our test number
      A = 42781 there is only one possible solution,
      at k = 20196, so 2*k - 1 = 40391 = 239*169.
      The GCD(40391,42781) = 239, a factor of A.

      .{$N+}{E+}
      Program issquaresieve (input, output);

      uses wincrt;
      type
      numptr = ^number;
      number = record
      next : array[0..60000] of shortint;
      end;
      frame = array[0..999] of numptr;
      var
      A,B, P,P1,xp, hq1,hq2,hqx : extended;
      fr : frame;
      x, w,w1,ta: longint;

      Procedure bigdat;
      {ESSENTIALLY A ONE-DIMENSIONAL ARRAY
      ONTO WHICH UP TO 60000000 ENTRIES CAN BE MAPPED}
      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 60000 do
      begin
      fr[i]^.next[a] := 0;
      end;
      writeln(' nnn');
      end;

      Procedure gcd1;
      {GREATEST COMMON DIVISOR}
      var
      i,j : longint;
      aa,bb: longint;
      k,n1,n2 : integer;
      c,hqf1, hqf2,r,s,t : extended;
      begin
      r := 2;
      hqf1 := P1*2 -1;{hqx;{}
      writeln('2*K-1 = ',trunc(HQF1));
      hqf2 := P;
      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 writeln('FACTOR ',trunc(hqf1));

      {else writeln(' gcd 1 ');
      {writeln('end gcd '); }
      end;


      Procedure Issqseries;
      {SETS UP THE INITIAL BOUNDRIES FOR THE SIEVE}
      var ab : array[1..15] of extended;
      x,y,z,z1,z2 : extended;
      ct : longint;
      i,j : integer;

      procedure sieve;
      {COMBINATION OF BOTH EXCLUSION
      AND INCLUSION ISSQUARE SIEVE TYPES
      MINIMIZE THE MODULUS SIZE}
      var ft,i,j,k,count: integer;
      Q : array[1..26] of 0..251;
      R : array[1..26,1..251] of 0..251;
      g,g1,g2 : longint;
      y,y1,z,h : extended;

      begin
      {THE VALUES HERE ARE FOR THE EXCLUSION PORTION OF THE SIEVE}

      q[1] := 3; q[2] := 7; q[3] := 13; q[4] := 17; q[5] := 23; q
      [6] := 37; q[7] := 43; q[8] := 47;
      q[9] := 53; q[10] := 67; q[11] := 73; q[12] := 83; q[13] := 97;
      {}

      {THE VALUES HERE ARE FOR THE INCLUSION PORTION OF THE SIEVE}

      q[14] := 11; q[15] := 19; q[16] := 29; q[17] := 31; q[18] :=
      41; q[19] := 59;
      q[20] := 61; q[21] := 71; q[22] := 79; q[23] := 89; q[24] :=
      101;

      {THIS CODE CHECKS THE TEST NUMBER FOR SMALL FACTORS}
      { for i := 1 to 24 do
      if x/q[i] = int(x/q[i]) then
      begin
      writeln(' Small Factor ',q[i]);
      readln;
      end;{}

      Z := ab[1] ;
      for i := 1 to 24 do
      for j := 1 to 251 do
      r[i,j] := 0 ;

      k := 1;
      repeat
      count := 1;
      y1 := 10*Z;
      y := x + y1;
      while count < 251 do
      begin
      for i := 1 to 24 do
      if y/q[i] = int(y/q[i]) then
      begin
      r[i,k] := q[i];
      end;
      count := count + 1;
      y1 := y1 + 10;
      y := y + y1;
      end;
      z := z + 1;
      k := k +1;
      until k = 251 + 1;


      writeln('initial locations and values ');
      writeln(' of the elements of the sieve ');

      for i := 1 to 24 do
      begin
      for j := 1 to q[i] do
      write(' ',j:4,r[i,j]:4,' ');
      readln;
      writeln;
      end; {}

      bigdat;{ }
      writeln;

      {EXCLUSION SIEVE ELIMINATES MOST
      INVALID ISSQUARE VALUES}
      for i := 1 to 13 do
      begin
      for j := 1 to q[i] do
      if r[i,j] > 0 then
      begin
      g := j;
      fr[0]^.next[g] := -1;

      while g < w+1 -w1 do
      begin
      g := g + Q[i];
      g1 := g mod 60000;
      g2 := g div 60000;
      fr[g2]^.next[g1] := -1;
      end;
      end;
      end;{}

      {INCLUSION SIEVE PICKS
      POSSIBLE VALID ISSQUARE VALUES
      FROM THOSE THAT REMAIN}

      for i := 14 to 24 do
      begin
      for j := 1 to q[i] do
      if r[i,j] > 0 then
      begin
      g := j;
      if fr[0]^.next[g] > -1 then
      fr[0]^.next[g] := fr[0]^.next[g] + 1;
      while g < w+1 -w1 do
      begin
      g := g + Q[i];
      g1 := g mod 60000;
      g2 := g div 60000;
      if fr[g2]^.next[g1] > -1 then
      fr[g2]^.next[g1] := fr[g2]^.next[g1] + 1;

      end;
      end;
      end;

      {OUTPUT OF PROGRAM}
      ct := 0;
      For g := 1 to w+1 - w1 do
      begin
      g1 := g mod 60000;
      g2 := g div 60000;
      begin
      if fr[g2]^.next[g1] = 11 then
      begin
      ct := ct + 1;
      end;
      end ;
      if fr[g2]^.next[g1] = 11 then
      begin
      write('K = ',TRUNC(g1 + g2*60000 + w1 -1),' ');
      P1 := (g1 + g2*60000 + w1 -1);
      GCD1;
      end;

      end;
      WRITELN;
      writeln(' NUMBER OF POSSIBLE VALID ISSQUARES ',ct);
      writeln(' xxx ');
      for i := 0 to 999 do
      dispose(fr[i]);

      end;


      begin{top}

      ab[10] := sqr(P);{}
      X := AB[10];{}
      ab[1] := trunc(P/sqrt(5)) ;{}
      w1 := trunc(ab[1]);
      write('test interval ',w1,' ');
      w :=trunc(B-1);{****}
      writeln(w);

      Sieve;
      writeln(' end sieve ');
      readln;
      end;

      BEGIN {TOP}
      writeln('ENTER AN INTEGER FOR X');
      READLN(X);

      A := 20*sqr(x)+ 10*x +1;
      B := 10*sqr(x) +4*x + 1;
      WRITELN(' A = ',A);
      WRITELN(' B = ',B);

      p := A;

      {p := p *p;{}
      {p := sqrt(p);{}

      Issqseries;{}

      END.

      Merry Christmas,
      Aldrich Stevens
    Your message has been successfully submitted and would be delivered to recipients shortly.