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

Re: mod quartic composite tests

Expand Messages
  • djbroadhurst
    ... Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n. Comment 2: Hence the happy gremlins, in this case. Exercise 3: Show that the test loses
    Message 1 of 26 , Jan 18, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

      > > loses (at least) one selfridge of potency for x^2 = 3 mod n.
      > Thanks for the insight.

      Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n.
      Comment 2: Hence the happy gremlins, in this case.

      Exercise 3: Show that the test loses 1 selfride for 2*x^2 = 5 mod n.
      Comment 3: The gremlins were not able to fool it in this case.

      David
    • djbroadhurst
      ... Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n. David
      Message 2 of 26 , Jan 18, 2013
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
        > Exercise 3: Show that the test loses 1 selfridge for 2*x^2 = 5 mod n.

        Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

        David
      • djbroadhurst
        ... Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n, degenerating to a 1-selfridge Euler test, with base -15/16, plus a 2-selfridge Lucas
        Message 3 of 26 , Jan 18, 2013
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:

          > Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

          Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n,
          degenerating to a 1-selfridge Euler test, with base -15/16, plus a
          2-selfridge Lucas test with P = 2/5 and Q = 1, and thus costs the same as BPSW.

          Comment: As in the case of BPSW, the gremlins cannot defraud this case.

          David
        • paulunderwooduk
          I failed to solve any of David s exercises... but I have done some shallow verification, n
          Message 4 of 26 , Jan 19, 2013
          • 0 Attachment
            I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:

            {tst(n,x)=kronecker(x^2-4,n)==-1&&
            gcd(x+1,n)==1&&
            Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}

            It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,

            Paul -- subject to gcd wriggles
          • paulunderwooduk
            ... Further, it seems that if gcd(x+1,n) is needed then it is equal to 1 (mod 6) Paul
            Message 5 of 26 , Jan 19, 2013
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
              >
              >
              > I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
              >
              > {tst(n,x)=kronecker(x^2-4,n)==-1&&
              > gcd(x+1,n)==1&&
              > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
              >
              > It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
              >

              Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)

              Paul
            • paulunderwooduk
              ... These ancillary statements are mostly false, except that maybe when gcd(x+1,n) needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and
              Message 6 of 26 , Jan 19, 2013
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
                >
                >
                >
                > --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
                > >
                > >
                > > I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
                > >
                > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                > > gcd(x+1,n)==1&&
                > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
                > >
                > > It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
                > >
                >
                > Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)
                >

                These ancillary statements are mostly false, except that maybe when "gcd(x+1,n)" needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) are either 1 or prime,

                Paul
              • paulunderwooduk
                ... Please accept my apology for my previous statements about this composite test. I am actually running tests for: (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1);
                Message 7 of 26 , Jan 19, 2013
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:


                  > > >
                  > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                  > > > gcd(x+1,n)==1&&
                  > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
                  > > >

                  Please accept my apology for my previous statements about this composite test. I am actually running tests for:
                  (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.

                  Now for some speculation about the results so far:

                  1) taking the mod with "the product" implies gcd(x,n)==1.

                  2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.

                  3) logged gcd(x+1,n) is not 1

                  4) the logged n are all congruent to 5 (mod 6).

                  Paul
                • paulunderwooduk
                  ... Here is another test, on the same theme, for which I cannot also easily find a fraud: {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^2-1,n)==1&&
                  Message 8 of 26 , Jan 21, 2013
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

                    >
                    > > > >
                    > > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                    > > > > gcd(x+1,n)==1&&
                    > > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
                    > > > >
                    >

                    Here is another test, on the same theme, for which I cannot also easily find a fraud:

                    {tst(n,x)=kronecker(x^2-4,n)==-1&&
                    gcd(x^2-1,n)==1&&
                    Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}

                    Paul
                  • paulunderwooduk
                    ... n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and
                    Message 9 of 26 , Jan 27, 2013
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

                      > Here is another test, on the same theme, for which I cannot also easily find a fraud:
                      >
                      > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                      > gcd(x^2-1,n)==1&&
                      > Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}
                      >

                      n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and gcd(x^2-2,n)==31,

                      Paul
                    • paulunderwooduk
                      ... n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be 1 or a product of primes each congruent 5 (mod 6) , but as greater n get tested I guess this rule
                      Message 10 of 26 , Jan 30, 2013
                      • 0 Attachment
                        > --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
                        >
                        >
                        > > > >
                        > > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                        > > > > gcd(x+1,n)==1&&
                        > > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
                        > > > >
                        >
                        > Please accept my apology for my previous statements about this composite test. I am actually running tests for:
                        > (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.
                        >
                        > Now for some speculation about the results so far:
                        >
                        > 1) taking the mod with "the product" implies gcd(x,n)==1.
                        >
                        > 2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.
                        >

                        n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be "1 or a product of primes each congruent 5 (mod 6)", but as greater n get tested I guess this rule will break too...

                        > 3) logged gcd(x+1,n) is not 1
                        >
                        > 4) the logged n are all congruent to 5 (mod 6).
                        >

                        I have verified all n<1.95*10^6

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