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

Re: Fermat+Euler+Frobenius

Expand Messages
  • djbroadhurst
    ... After tidying up your request, the Gremlims happily obliged: {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]); sum(k=1,#v,gcd(v[k],n) 1)==0;}
    Message 1 of 24 , Jul 18, 2013
      --- In primenumbers@yahoogroups.com,
      "paulunderwooduk" <paulunderwood@...> wrote:

      > > David, sorry for the noise. Here is what I have in mind:
      > Oh dear, I meant ...
      > Paul -- suffering from error-after-posting syndrome

      After tidying up your request, the Gremlims happily obliged:

      {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
      sum(k=1,#v,gcd(v[k],n)>1)==0;}

      {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
      Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
      Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
      Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
      Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
      Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

      {if(tst(9526822969*133375521553,244578343630781166947),
      print(" Gremlins rule OK"));}

      Gremlins rule OK

      David (their minder)
    • paulunderwooduk
      ... They do indeed rule. I now present a puzzle: make all the tests strong i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas
      Message 2 of 24 , Jul 18, 2013
        --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
        >
        >
        >
        > --- In primenumbers@yahoogroups.com,
        > "paulunderwooduk" <paulunderwood@> wrote:
        >
        > > > David, sorry for the noise. Here is what I have in mind:
        > > Oh dear, I meant ...
        > > Paul -- suffering from error-after-posting syndrome
        >
        > After tidying up your request, the Gremlims happily obliged:
        >
        > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
        > sum(k=1,#v,gcd(v[k],n)>1)==0;}
        >
        > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
        > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
        > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
        > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
        > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
        > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
        >
        > {if(tst(9526822969*133375521553,244578343630781166947),
        > print(" Gremlins rule OK"));}
        >
        > Gremlins rule OK
        >

        They do indeed rule. I now present a puzzle: make all the tests "strong" i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas test will be enough,

        With thanks,

        Paul
      • paulunderwooduk
        ... I mean check that square roots, where the exist, of all 1 are +-1, Paul
        Message 3 of 24 , Jul 18, 2013
          --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:



          > > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,3*a^2-7]);
          > > sum(k=1,#v,gcd(v[k],n)>1)==0;}
          > >
          > > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
          > > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
          > > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
          > > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
          > > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
          > > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

          > I now present a puzzle: make all the tests "strong" i.e. check roots of 1 where possible. Of course, if n==3 (mod 4) a strong Lucas test will be enough,
          >

          I mean check that square roots, where the exist, of all 1 are +-1,

          Paul
        • djbroadhurst
          ... That s your job; not the Gremlins :-) To show that they can still work at 120 digits, even after all your wriggling, they invite you to find gcd s that
          Message 4 of 24 , Jul 18, 2013
            --- In primenumbers@yahoogroups.com,
            "paulunderwooduk" <paulunderwood@...> wrote:

            > I now present a puzzle: make all the tests "strong"

            That's your job; not the Gremlins' :-)

            To show that they can still work at 120 digits,
            even after all your wriggling, they invite you to find
            gcd's that stop these pseudoprimes fooling your test:

            {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
            sum(k=1,#v,gcd(v[k],n)>1)==0;}

            {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
            Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
            Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
            Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
            Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
            Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

            {fooling=[

            [16212200212765236462624941301662595905969969921486185624581\
            42710646148264113979405459683534701445570403174269878228032843,

            148751952532863090430663215218366305961343757352250610518989\
            959178089757327365262627066765931489564753215534936293595719],

            [92856680188887785533016964629715768104484119019221599899820\
            26844918042826013874700027439880606063780672269637251932365051,

            246307830695230159344853971299085504661118671451065969332908\
            6522201134308546059459112977581864702729364124320490100075243]];

            for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];
            if(tst(n,a)&&!isprime(n),print(" Gremlins rule OK")));}

            Gremlins rule OK
            Gremlins rule OK

            They prefer to work around 120 digits, since then
            you have to be a little smarter to factor the semiprimes.
            I believe that Kermit will be able to factorize the two
            above, since he has been using other lists as practice.

            David
          • paulunderwooduk
            ... Well, I can t do what the Gremlins have done to refute my efforts so far, let alone to solve my own puzzle! But I will make a silver sub-puzzle by dropping
            Message 5 of 24 , Jul 18, 2013
              --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
              >
              >
              >
              > --- In primenumbers@yahoogroups.com,
              > "paulunderwooduk" <paulunderwood@> wrote:
              >
              > > I now present a puzzle: make all the tests "strong"
              >
              > That's your job; not the Gremlins' :-)
              >

              Well, I can't do what the Gremlins have done to refute my efforts so far, let alone to solve my own puzzle! But I will make a silver sub-puzzle by dropping any PRP test on "a", but still insisting on strong tests for the other PRP sub-tests including the Lucas PRP test.

              > To show that they can still work at 120 digits,
              > even after all your wriggling, they invite you to find
              > gcd's that stop these pseudoprimes fooling your test:
              >

              I am unable to crack the gcd tricks and I am in the dark as to how Kermit factored the numbers in:
              http://tech.groups.yahoo.com/group/primenumbers/message/25227

              > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
              > sum(k=1,#v,gcd(v[k],n)>1)==0;}
              >
              > {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
              > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
              > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
              > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
              > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
              > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}
              >
              > {fooling=[
              >
              > [16212200212765236462624941301662595905969969921486185624581\
              > 42710646148264113979405459683534701445570403174269878228032843,
              >
              > 148751952532863090430663215218366305961343757352250610518989\
              > 959178089757327365262627066765931489564753215534936293595719],
              >
              > [92856680188887785533016964629715768104484119019221599899820\
              > 26844918042826013874700027439880606063780672269637251932365051,
              >
              > 246307830695230159344853971299085504661118671451065969332908\
              > 6522201134308546059459112977581864702729364124320490100075243]];
              >
              > for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];
              > if(tst(n,a)&&!isprime(n),print(" Gremlins rule OK")));}
              >
              > Gremlins rule OK
              > Gremlins rule OK
              >
              > They prefer to work around 120 digits, since then
              > you have to be a little smarter to factor the semiprimes.
              > I believe that Kermit will be able to factorize the two
              > above, since he has been using other lists as practice.
              >

              Paul
            • djbroadhurst
              ... When n = 3 mod 4, Euler is identical to Miller-Rabin, since (n-1)/2 is odd. Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1. Then the only
              Message 6 of 24 , Jul 18, 2013
                --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

                > strong tests

                When n = 3 mod 4, Euler is identical to Miller-Rabin,
                since (n-1)/2 is odd.

                Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1.
                Then the only stengthening of Lucas is to show that
                L^((n+1)/4) (mod all that other stuff) is +1 or -1.
                since (n+1)/4 is odd.

                {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                sum(k=1,#v,gcd(v[k],n)>1)==0;}

                {tst3mod8(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                !isprime(n)&&n%8==3&&kronecker(Q,n)==1&& \\ just to keep Paul happy
                Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&(
                Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==+1||
                Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==-1);}

                {if(tst3mod8(1080534578729388602707,3487806307751356235),
                print(" Done!"));}

                Done!

                David
              • paulunderwooduk
                ... Wonderful! Thanks for the exposition. It is another example of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test can be counterexampled. Once
                Message 7 of 24 , Jul 18, 2013
                  --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
                  >
                  >
                  >
                  > --- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@> wrote:
                  >
                  > > strong tests
                  >
                  > When n = 3 mod 4, Euler is identical to Miller-Rabin,
                  > since (n-1)/2 is odd.
                  >
                  > Now suppose that n = 3 mod 8 and kronecker(Q,n) = +1.
                  > Then the only stengthening of Lucas is to show that
                  > L^((n+1)/4) (mod all that other stuff) is +1 or -1.
                  > since (n+1)/4 is odd.
                  >
                  > {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                  > sum(k=1,#v,gcd(v[k],n)>1)==0;}
                  >
                  > {tst3mod8(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                  > !isprime(n)&&n%8==3&&kronecker(Q,n)==1&& \\ just to keep Paul happy
                  > Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                  > Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                  > Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                  > Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&(
                  > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==+1||
                  > Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/4)==-1);}
                  >
                  > {if(tst3mod8(1080534578729388602707,3487806307751356235),
                  > print(" Done!"));}
                  >
                  > Done!
                  >

                  Wonderful! Thanks for the exposition. It is another example of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test can be counterexampled. Once again you and the Gremlins have rescued a core or two from inane computation,

                  Paul
                • djbroadhurst
                  ... That s what Gremlins are for. ... Here is one of many ways to evade your wriggles, which had trivial gcds. I give a pair of smarter gcds, which serve for
                  Message 8 of 24 , Jul 19, 2013
                    --- In primenumbers@yahoogroups.com,
                    "paulunderwooduk" <paulunderwood@...> wrote:

                    > Wonderful! Thanks for the exposition. It is another example
                    > of how a one parameter Lucas plus N Fermat/Euler/M-R PRP test
                    > can be counterexampled.

                    That's what Gremlins are for.

                    > I am unable to crack the gcd tricks

                    Here is one of many ways to evade your wriggles, which had
                    trivial gcds. I give a pair of smarter gcds, which serve
                    for three small examples, But as soon as we include this trap
                    the Gremlins will find another smart way out.

                    {wriggle(a,n)=local(v=[a,3*a^2+1,5*a^2-1,13*a^2-1,7*a^2-3]);
                    sum(k=1,#v,gcd(v[k],n)>1)==0;}

                    {tst(n,a)=local(Q=3*a^2+1);kronecker(a^2-1,n)==-1&&wriggle(a,n)&&
                    Mod(a,n)^((n-1)/2)==kronecker(a,n)&&
                    Mod(a-1,n)^((n-1)/2)==kronecker(a-1,n)&&
                    Mod(a+1,n)^((n-1)/2)==kronecker(a+1,n)&&
                    Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
                    Mod(Mod(1,n)*L,L^2-lift(Mod((10*a^2-2)/Q,n))*L+1)^((n+1)/2)==kronecker(Q,n);}

                    {smart(a,n)=local(v=[
                    581130733*a^18-1549681961*a^16+1598109492*a^14-815197364*a^12
                    +219605318*a^10-31108446*a^8+2189796*a^6-67524*a^4+693*a^2-1,
                    290565367*a^18-920123659*a^16+1150154588*a^14-728431196*a^12
                    +250797682*a^10-47124218*a^8+4637292*a^6-217740*a^4+4047*a^2-19]);
                    sum(k=1,#v,gcd(v[k],n)>1)>0;}

                    {fooling=[
                    [2972225251*112944559501,48957135643862669970],
                    [3047555083*115807093117,49017305561177450303],
                    [3130042291*118941607021,169666628495887666139]];

                    for(k=1,#fooling,n=fooling[k][1];a=fooling[k][2];if(tst(n,a)
                    &&smart(a,n),print(" fooled wriggle, trapped smartly")));}

                    fooled wriggle, trapped smartly
                    fooled wriggle, trapped smartly
                    fooled wriggle, trapped smartly

                    The derivation of the pair of polynomials, for
                    these particular cases, is left as an exercise.

                    David (spilling the Gremlins' secrets)
                  • djbroadhurst
                    ... Maybe Kermit read http://selmer.warwick.ac.uk/onelinefactor.pdf {OLF(x)=;i=1;while(i
                    Message 9 of 24 , Jul 31, 2013
                      --- In primenumbers@yahoogroups.com,
                      "paulunderwooduk" <paulunderwood@...> wrote:

                      > I am in the dark as to how Kermit factored the numbers in:
                      > http://tech.groups.yahoo.com/group/primenumbers/message/25227

                      Maybe Kermit read
                      http://selmer.warwick.ac.uk/onelinefactor.pdf

                      {OLF(x)=;i=1;while(i<x,if(issquare(ceil(sqrt(i*x))^2%x),
                      return(gcd(x,floor(ceil(sqrt(i*x))-sqrt((ceil(sqrt(i*x))^2)%x)))));i++);}

                      {default(realprecision,130);gettime;
                      N1=16212200212765236462624941301662595905969969921486185624581
                      42710646148264113979405459683534701445570403174269878228032843;
                      N2=92856680188887785533016964629715768104484119019221599899820
                      26844918042826013874700027439880606063780672269637251932365051;
                      print(OLF(N1)" divides N1");
                      print(OLF(N2)" divides N2");
                      print("This took "gettime" millisecond(s)");}

                      5972172173345601078558810561451365062976970419888735246630677 divides N1
                      11401725845872759790535993230138294233298881744517681451802021 divides N2
                      This took 1 millisecond(s)

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