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

Fib(25561) from K-P combined test

Expand Messages
  • d.broadhurst@open.ac.uk
    Fib(25561) from K-P combined test A few months ago, the proof requirement for Pfgw was 33.33% factorization of either N-1 or N+1. Then there were two rather
    Message 1 of 4 , Jul 7, 2001
      Fib(25561) from K-P combined test

      A few months ago, the proof requirement for Pfgw
      was 33.33% factorization of either N-1 or N+1.

      Then there were two rather significant developments:

      1) Chris Nash implemented the BLS proof method
      with 3*F_max + Fmin > 1, where F_max=max(F1,F2)
      and F_min=min(F1,F2), with F1 being the proportion
      of the digits of N-1 that are factorized, and F2
      the proportion of N+1. This brought Pfgw
      up to the standard of the BLS part of VFYPR.

      2) Andy Steward implemented, in Ubasic, a
      Konyagin-Pomerance proof, in the case F1 > 0.3.
      I then implemented it in Pari, which was far faster,
      thanks to the commands "contfrac" and "polroots".

      When Andy and I met recently with Bouk de Water
      in Amsterdam, the hot topic was rather obvious:
      how to combine both advances?

      Today I worked out how it goes; it is enough to have

      11*F1 > 10*F1 + 3*F2 > 3

      [give or take a few bits: precise conditions appended.]

      Colleagues with sharp minds are invited to check the theorem,
      below, which is a rather straightforward adaptation of
      my improvement of K-P to benefit from extra square tests.

      This has an immediate and very pleasant consequence.

      Until today the Fibonacci roll of hour had only
      5 titanic entries

      U(81839) 17103 p54 2001 Fibonacci number
      U(14431) 3016 p54 2001 Fibonacci number
      U(9677) 2023 c2 2000 Fibonacci number
      U(9311) 1946 DK 1995 Fibonacci number
      U(5387) 1126 WM 1990 Fibonacci number

      To these, Bouk and I now add

      U(25561) 5342 p54 2001 Fibonacci number

      thanks to the fractions F1=0.2865, F2=0.05704
      and the corresponding cubic and square tests.

      David Broadhurst
      Appendix:
      Theorem [KP combined test]
      ==========================

      Let N=F*R+1 with gcd(F,R)=1 and R>F^2.
      Let N=G*S-1 with gcd(F,G)=1.

      Suppose that the BLS tests establish
      that every factor of N is 1 mod F
      and +/- 1 mod G.

      Let c1 be the unique integer in [1,F-1]
      such that c4=(R-c1)/F is an integer.
      Now test that
      (c1+t*F)^2+4*t-4*c4
      is not a square when t=t_G
      and t_G is the unique integer in [0,G-1]
      with t=c4 mod G.

      Now *modify* the KP cubic algorithm
      by taking u/v to be the continued
      fraction convergent to c1/F with
      maximal v < F^(1/3). [sic]

      Suppose that we construct the cubic
      P(X) = v*X^3 + (u*F-c1*v)*X^2 + (c4*v-d*F+u)*X - d
      with d=round(c4*v/F)
      and verify that none of its roots is an integer.

      Then N is prime, if

      F^(1/3)/6 > G+1 > 3*N/F^(10/3)
      ==============================

      Proof:
      ======

      Suppose that N were not prime,
      but instead of the form N=(a1*F+1)*(a2*F+1).
      Let t = c4-a1*a2.
      One of a1*F and a2*F must be divisible by G.
      Hence t = c4 mod G, since gcd(F,G)=1.
      When t = t_G has been ruled out,
      the proof given in
      http://groups.yahoo.com/group/primeform/message/2142
      goes through, with T replaced by G-1.
    • d.broadhurst@open.ac.uk
      Apologies for a typo: in ... The precise condition is F^(1/3)/6 G-1 3*N/F^(10/3) as is clear from the proof.
      Message 2 of 4 , Jul 7, 2001
        Apologies for a typo: in
        > Theorem [KP combined test]

        The precise condition is

        F^(1/3)/6 > G-1 > 3*N/F^(10/3)

        as is clear from the proof.
      • Satoshi TOMABECHI
        On Sat, 07 Jul 2001 19:04:24 -0000 ... [snip] ... Broadhurst s combined test is very excellent, especially from computational view point . The conditions above
        Message 3 of 4 , Jul 9, 2001
          On Sat, 07 Jul 2001 19:04:24 -0000
          d.broadhurst@... wrote:

          > Theorem [KP combined test]
          > ==========================
          >
          > Let N=F*R+1 with gcd(F,R)=1 and R>F^2.
          > Let N=G*S-1 with gcd(F,G)=1.
          [snip]
          >
          > Proof:
          > ======
          >
          > Suppose that N were not prime,
          > but instead of the form N=(a1*F+1)*(a2*F+1).
          > Let t = c4-a1*a2.
          > One of a1*F and a2*F must be divisible by G.
          > Hence t = c4 mod G, since gcd(F,G)=1.

          Broadhurst's combined test is very excellent,
          especially from computational view point .
          The conditions above restricts the possible values of a1,a2.
          This decreases extremely square tests.
          If we admit some extra square tests, G may be more smaller.

          Satoshi Tomabechi
        • d.broadhurst@open.ac.uk
          Satoshi Tomabechi wrote ... In fact I have made further improvements by finding a way to combine APRCL tests with the KP cubic and BLS square tests. First
          Message 4 of 4 , Jul 9, 2001
            Satoshi Tomabechi wrote

            > Broadhurst's combined test is very excellent,
            > especially from computational view point.
            > The conditions above restricts the possible values of a1,a2.
            > This decreases extremely square tests.
            > If we admit some extra square tests, G may be more smaller.

            In fact I have made further improvements
            by finding a way to combine APRCL tests
            with the KP cubic and BLS square tests.

            First let's summarize what VFYPR can do:

            Suppose that N=F1*R1+1=F2*R2-1, with
            2|F1, gcd(F1,R1)=1,
            2|F2, gcd(F2,R2)=1,
            and the BLS tests proving that
            every divisor d of N has
            d = 1 mod F1, (1)
            d = +/-1 mod F2. (2)

            Suppose further that for some S
            with gcd(S,N^2-1)=1 the APRCL
            tests prove that every divisor has
            d = N^i mod S, (3)
            for some i<T.

            Let F_max=max(F1,F2) and F_min=min(F1,F2).
            Then the classic APRCL + BLS-combined
            method enables a proof in the case

            2*N < F_max^3 * F_min * S [VFYPR]

            at the expense of a single square test and a
            simple divisor test for each of the 2*T residue
            classes mod (F1*F2*S/2) that result from
            using the Chinese remainder theorem on (1,2,3).

            I have derived a stronger result:

            Pomerance^2 = APRCL + KP
            ========================

            Provided that N < F_max^4, a proof is
            also possible in the case

            6*N < F_max^(10/3) * F_min * S [APR-CL-KP]

            at the expense of
            no more than 2*T square tests and
            no more than 2 cubic tests.

            Uses: Suppose that we have only 25%
            from N-1, then we need 16.66% from
            N+1 and S.

            However, there is a pressing case
            with 29.62% of the 4,200 digits of N-1.
            Here we need only 1.3% from N+1 and S, i.e.
            55 digits. Bouk and I have 8 digits from
            N+1 and hence can complete with S=O(10^47)
            from APRCL, which is feasible at 4,200 digits.

            David Broadhurst
          Your message has been successfully submitted and would be delivered to recipients shortly.