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

mod quartic composite tests

Expand Messages
  • paulunderwooduk
    Hi, I have devised a new composite test for odd n with x: gcd(x^3-x,n)==1 (mod n) kronecker(x^2-4,n)==-1 and the sub-test: (L+1)^n==-L^3+(x^2-2)*L+1 (mod n,
    Message 1 of 26 , Jan 9, 2013
    • 0 Attachment
      Hi,

      I have devised a new composite test for odd n with x:
      gcd(x^3-x,n)==1 (mod n)
      kronecker(x^2-4,n)==-1

      and the sub-test:
      (L+1)^n==-L^3+(x^2-2)*L+1 (mod n, (L^2-x*L+1)*(L^2+x*L+1))

      Can you find a counterexample? If this is too easy for you, please try:

      (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))

      Paul
    • paulunderwooduk
      ... n=287051 and x=3988 is a counterexample. ... This test is (1)+(1)+(2)+(2)+9 selfridge for small x, where (1) is a fermat test and (2) is a frobenius test
      Message 2 of 26 , Jan 9, 2013
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
        >
        > Hi,
        >
        > I have devised a new composite test for odd n with x:
        > gcd(x^3-x,n)==1 (mod n)
        > kronecker(x^2-4,n)==-1
        >
        > and the sub-test:
        > (L+1)^n==-L^3+(x^2-2)*L+1 (mod n, (L^2-x*L+1)*(L^2+x*L+1))
        >
        > Can you find a counterexample?

        n=287051 and x=3988 is a counterexample.

        > If this is too easy for you, please try:
        >
        > (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))
        >

        This test is (1)+(1)+(2)+(2)+9 selfridge for small x, where (1) is a fermat test and (2) is a frobenius test over L^2-x*L+1 or L^2+x*L+1.

        I already have:
        "Non-square N>1 is prime if and only if for any integer x such that
        KoneckerSymbol(x^2-4,N)==-1
        then both (L+-2)^(N+1)==5+-2*x (mod N, L^2-x*L+1) (Both L+-2 needed.)
        Verified for odd N< 10^7."

        Paul
      • djbroadhurst
        ... I can do it in 6 selfridges for generic x. Where do your 9 selfridges come from, Paul? With kronecker(x^4-2,n) = -1 and prime n, we have (L+a)^n = a+x-L
        Message 3 of 26 , Jan 9, 2013
        • 0 Attachment
          --- In primenumbers@yahoogroups.com,
          Paul Underwood wrote:

          > (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))
          > This test is (1)+(1)+(2)+(2)+9 selfridge for small x

          I can do it in 6 selfridges for generic x.
          Where do your "9" selfridges come from, Paul?

          With kronecker(x^4-2,n) = -1 and prime n, we have

          (L+a)^n = a+x-L mod(n, L^2-L*x+1) ... [1]
          (L+a)^n = a-x-L mod(n, L^2+L*x+1) ... [2]

          and the two Frobenius tests cost 3+3=6 selfridges, generically.

          Now let f(x,L) = -L^3+(x^2-2)*L and observe
          from simple algebra (no modularity involved) that

          f(x,L) + a = (a+x-L) - (L+x)*(L^2-x*L+1)
          f(x,L) + a = (a-x-L) - (L-x)*(L^2+x*L+1)

          Hence [1] and [2] imply that

          (L+a)^n = f(x,L) + a mod(n, (L^2-x*L+1)*(L^2+x*L+1)) ... [3]

          and Paul has set a = 2 in [3].

          Since this is a double-Frobenius test, the gremlins
          reserve the right to choose /both/ parameters (a,x) in [3].

          David
        • djbroadhurst
          ... but meant to write x^2-4, not x^4-2
          Message 4 of 26 , Jan 9, 2013
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            "djbroadhurst" wrote:
            > With kronecker(x^4-2,n) = -1
            but meant to write x^2-4, not x^4-2
          • paulunderwooduk
            ... Thanks for the algebra -- it was worrying me. Yes, the gremlins will not like this test: gcd(x^3-x,n) kronecker(x^2-4,n)==-1 gcd(x^2-2,n)==1
            Message 5 of 26 , Jan 9, 2013
            • 0 Attachment
              --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote:
              >
              >
              >
              > --- In primenumbers@yahoogroups.com,
              > Paul Underwood wrote:
              >
              > > (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))
              > > This test is (1)+(1)+(2)+(2)+9 selfridge for small x
              >
              > I can do it in 6 selfridges for generic x.
              > Where do your "9" selfridges come from, Paul?
              >
              > With (ed.) kronecker(x^2-4,n) = -1 and prime n, we have
              >
              > (L+a)^n = a+x-L mod(n, L^2-L*x+1) ... [1]
              > (L+a)^n = a-x-L mod(n, L^2+L*x+1) ... [2]
              >
              > and the two Frobenius tests cost 3+3=6 selfridges, generically.
              >
              > Now let f(x,L) = -L^3+(x^2-2)*L and observe
              > from simple algebra (no modularity involved) that
              >
              > f(x,L) + a = (a+x-L) - (L+x)*(L^2-x*L+1)
              > f(x,L) + a = (a-x-L) - (L-x)*(L^2+x*L+1)
              >
              > Hence [1] and [2] imply that
              >
              > (L+a)^n = f(x,L) + a mod(n, (L^2-x*L+1)*(L^2+x*L+1)) ... [3]
              >
              > and Paul has set a = 2 in [3].
              >
              > Since this is a double-Frobenius test, the gremlins
              > reserve the right to choose /both/ parameters (a,x) in [3].
              >

              Thanks for the algebra -- it was worrying me.

              Yes, the gremlins will not like this test:

              gcd(x^3-x,n)
              kronecker(x^2-4,n)==-1
              gcd(x^2-2,n)==1
              (L+x^2-2)^n==-L^3+(x^2-2)*L+(x^2-2) (mod n, (L^2-x*L+1)*(L^2+x*L+1))

              Paul
            • paulunderwooduk
              ... I have verified this test for all x for all n
              Message 6 of 26 , Jan 10, 2013
              • 0 Attachment
                --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

                > gcd(x^3-x,n)==1
                > kronecker(x^2-4,n)==-1
                > gcd(x^2-2,n)==1
                > (L+x^2-2)^n==-L^3+(x^2-2)*L+(x^2-2) (mod n, (L^2-x*L+1)*(L^2+x*L+1))

                I have verified this test for all x for all n<10^6 co-prime to 30,

                Paul
              • paulunderwooduk
                ... ? {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;} ?
                Message 7 of 26 , Jan 11, 2013
                • 0 Attachment
                  --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
                  >
                  >
                  >
                  > --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
                  >
                  > > gcd(x^3-x,n)==1
                  > > kronecker(x^2-4,n)==-1
                  > > gcd(x^2-2,n)==1
                  > > (L+x^2-2)^n==-L^3+(x^2-2)*L+(x^2-2) (mod n, (L^2-x*L+1)*(L^2+x*L+1))
                  >
                  > I have verified this test for all x for all n<10^6 co-prime to 30,
                  >

                  ? {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("underw297.txt");}
                  2/297 counterexamples left in underw297.txt
                  ? {tstfile("underw65.txt");}
                  5146/12846 counterexamples left in underw65.txt

                  Paul
                • paulunderwooduk
                  ... Adding gcd(x^2-3,n)==1 makes sense because x^2-2==1 (mod x^2-3). So the resurrected test is: {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^3-x,n)==1&&
                  Message 8 of 26 , Jan 11, 2013
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

                    >
                    > ? {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("underw297.txt");}
                    > 2/297 counterexamples left in underw297.txt
                    > ? {tstfile("underw65.txt");}
                    > 5146/12846 counterexamples left in underw65.txt
                    >

                    Adding gcd(x^2-3,n)==1 makes sense because x^2-2==1 (mod x^2-3). So the resurrected test is:

                    {tst(n,x)=kronecker(x^2-4,n)==-1&&
                    gcd(x^3-x,n)==1&&
                    gcd(x^2-2,n)==1&&
                    gcd(x^2-3,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;}

                    Then checking David's files at:
                    http://physics.open.ac.uk/~dbroadhu/cert/

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

                    ? {tstfile("underbh4.txt");}
                    0/33445 counterexamples left in underbh4.txt
                    ? {tstfile("underbh6.txt");}
                    0/308619 counterexamples left in underbh6.txt
                    ? {tstfile("underw97.txt");}
                    0/97 counterexamples left in underw97.txt
                    ? {tstfile("underw297.txt");}
                    0/297 counterexamples left in underw297.txt
                    ? {tstfile("underw65.txt");}
                    0/12846 counterexamples left in underw65.txt
                    ? {tstfile("underw65x.txt");}
                    0/10220 counterexamples left in underw65x.txt
                    ? {tstfile("underwg.txt");}
                    0/100000 counterexamples left in underwg.txt

                    Paul
                  • paulunderwooduk
                    ... n=2672279 and x=89805 forms a near-counterexample, saved only by gcd(x^3-x,n)==2672279. Since gcd(x^3-x,n)==1 is required I do not have to verify numbers
                    Message 9 of 26 , Jan 15, 2013
                    • 0 Attachment
                      --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:

                      > {tst(n,x)=kronecker(x^2-4,n)==-1&&
                      > gcd(x^3-x,n)==1&&
                      > gcd(x^2-2,n)==1&&
                      > gcd(x^2-3,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;}
                      >

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

                      Since gcd(x^3-x,n)==1 is required I do not have to verify numbers divisible by 2 or 3, and with kronecker(x^2-4,n)==-1, I do not have to verify numbers divisible by 5. Also the squares modulo 7 are 0, 1, 4, and 2, and because I am checking gcd(x^3-x,n)==1, kronecker(x^2-4,n)==-1 and gcd(x^2-2,n)==1, I can skip numbers divisible by 7. All in all, I need only verify numbers co-prime to 210,

                      Paul
                    • paulunderwooduk
                      ... That should read gcd(x^2-3,n)==2672279. Paul
                      Message 10 of 26 , Jan 15, 2013
                      • 0 Attachment
                        --- 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 11 of 26 , Jan 15, 2013
                        • 0 Attachment
                          --- 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 12 of 26 , Jan 17, 2013
                          • 0 Attachment
                            --- 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 13 of 26 , Jan 17, 2013
                            • 0 Attachment
                              --- 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 14 of 26 , Jan 17, 2013
                              • 0 Attachment
                                --- 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 15 of 26 , Jan 18, 2013
                                • 0 Attachment
                                  > 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 16 of 26 , Jan 18, 2013
                                  • 0 Attachment
                                    --- 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 17 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 18 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 19 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 20 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 21 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 22 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 23 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 24 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 25 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 26 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.