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

Re: mod quartic composite tests

Expand Messages
  • paulunderwooduk
    ... That should read gcd(x^2-3,n)==2672279. Paul
    Message 1 of 26 , Jan 15, 2013
      --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

      > n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279.

      That should read gcd(x^2-3,n)==2672279.

      Paul
    • djbroadhurst
      ... A wise wriggle :-) Without it, you left yourself wide open to fraud. With it, you seem to be much more secure. I believe, yet cannot show, that there are
      Message 2 of 26 , Jan 15, 2013
        --- In primenumbers@yahoogroups.com,
        "paulunderwooduk" wrote:

        > Adding gcd(x^2-3,n)==1

        A wise "wriggle" :-)

        Without it, you left yourself wide open to fraud.
        With it, you seem to be much more secure.

        I believe, yet cannot show, that there are zillions of
        counterexamples to your single-parameter, double-Frobenius
        test, yet the prospects of finding one, now that you
        have bolted the stable door, seem to be minuscule.

        Thanks, Paul, for your responsiveness.

        David
      • djbroadhurst
        ... http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz provides 352869 such frauds: {tst(n,x)=kronecker(x^2-4,n)==-1&&gcd(x^3-x,n)==1&&gcd(x^2-2,n)==1&&
        Message 3 of 26 , Jan 17, 2013
          --- In primenumbers@yahoogroups.com,
          "paulunderwooduk" wrote:

          > n=2672279 and x=89805

          http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz
          provides 352869 such frauds:

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

          {tstfile(file)=local(v=readvec(file),c);
          c=sum(k=1,#v,tst(v[k][1],v[k][2])&&!isprime(v[k][1]));
          print(c"/"#v" counterexamples left in "file);c;}

          tstfile("underwqd.txt");

          352869/352869 counterexamples left in underwqd.txt

          All are trapped by Paul's latest wriggle,
          which requires x^2-3 to be coprime to n.

          David
        • paulunderwooduk
          ... Thanks for these, David. Is it a comprehensive list for all n
          Message 4 of 26 , Jan 17, 2013
            --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:

            > http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz

            >
            > 352869/352869 counterexamples left in underwqd.txt
            >
            > All are trapped by Paul's latest wriggle,
            > which requires x^2-3 to be coprime to n.
            >

            Thanks for these, David. Is it a comprehensive list for all n <= 97847746461047271599?

            Paul
          • djbroadhurst
            ... By no means. However the updated file http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz now has more:
            Message 5 of 26 , Jan 17, 2013
              --- In primenumbers@yahoogroups.com,
              "paulunderwooduk" wrote:

              > Is it a comprehensive list for all n <= 97847746461047271599?

              By no means. However the updated file
              http://physics.open.ac.uk/~dbroadhu/cert/underwqd.txt.gz
              now has more:

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

              {tstfile(file)=local(v=readvec(file),c);
              c=sum(k=1,#v,tst(v[k][1],v[k][2])&&!isprime(v[k][1]));
              print(c"/"#v" counterexamples left in "file);c;}

              tstfile("underwqd.txt");

              422355/422355 counterexamples left in underwqd.txt

              Challenge: Find a composite 10^10-smooth positive
              integer, n, such that:
              1) there exist an integer x that passes tst(n,x),
              2) n is not in underwqd.txt.

              Comment: I do not know of any such integer. Nor do I know
              how to search for one. So I guess that means my gremlins
              are comprehensively exhausted, though the question is not.

              David
            • djbroadhurst
              ... Exercise: Show that Paul s test Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2 requires n to be a Fermat pseudoprime in base
              Message 6 of 26 , Jan 18, 2013
                > All are trapped by Paul's latest wriggle,
                > which requires x^2-3 to be coprime to n.

                Exercise: Show that Paul's test
                Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2
                requires n to be a Fermat pseudoprime in base 1+(x^2-3)*(x^2-2)^3
                and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.

                David
              • paulunderwooduk
                ... ? M=[0,(x^2-2),0,-1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^2-2)==1+(x^2-3)*(x^2-2)^3 1 Thanks for the insight. This can be split into 2 Fermat tests: ?
                Message 7 of 26 , Jan 18, 2013
                  --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
                  >
                  >
                  >
                  > > All are trapped by Paul's latest wriggle,
                  > > which requires x^2-3 to be coprime to n.
                  >
                  > Exercise: Show that Paul's test
                  > Mod(Mod(1,n)*(L+x^2-2),(L^2-x*L+1)*(L^2+x*L+1))^n==-L^3+(x^2-2)*L+x^2-2
                  > requires n to be a Fermat pseudoprime in base 1+(x^2-3)*(x^2-2)^3
                  > and thus loses (at least) one selfridge of potency for x^2 = 3 mod n.
                  >

                  ? M=[0,(x^2-2),0,-1;1,0,0,0;0,1,0,0;0,0,1,0];matdet(M+x^2-2)==1+(x^2-3)*(x^2-2)^3
                  1

                  Thanks for the insight.

                  This can be split into 2 Fermat tests:

                  ? M=[x,-1;1,0];matdet(M+x^2-2)
                  x^4 + x^3 - 4*x^2 - 2*x + 5
                  ? M=[-x,-1;1,0];matdet(M+x^2-2)
                  x^4 - x^3 - 4*x^2 + 2*x + 5

                  which are equal to:

                  ? M=[x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x+2)*(x-1)+1
                  1
                  ? M=[-x,-1;1,0];matdet(M+x^2-2)==(x^2-2)*(x-2)*(x+1)+1
                  1

                  Paul
                • 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 8 of 26 , Jan 18, 2013
                    --- 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 9 of 26 , Jan 18, 2013
                      --- 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 10 of 26 , Jan 18, 2013
                        --- 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 11 of 26 , Jan 19, 2013
                          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 12 of 26 , Jan 19, 2013
                            --- 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 13 of 26 , Jan 19, 2013
                              --- 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 14 of 26 , Jan 19, 2013
                                --- 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 15 of 26 , Jan 21, 2013
                                  --- 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 16 of 26 , Jan 27, 2013
                                    --- 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 17 of 26 , Jan 30, 2013
                                      > --- 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.