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

Re: "wriggly" probable primes

Expand Messages
  • djbroadhurst
    ... 4065702994722252685573484796054334194691713593576645739409115721859519 = 5x^2 + 5xy + y^2 Comment: Pari-GP s qfbsolve enables a solution in two minutes.
    Message 1 of 50 , Sep 14, 2010
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "djbroadhurst" <d.broadhurst@...> wrote:

      >> Exercise: Find two pairs of positive integers (x,y) such that
      4065702994722252685573484796054334194691713593576645739409115721859519
      = 5x^2 + 5xy + y^2
      Comment: Pari-GP's "qfbsolve" enables a solution in two minutes.
      Devotees of "issquare", like Aldrich, may take considerably longer.<<

      Here is the 2 minute solution:

      R(v)=local(a=G(v[1]),b=G(v[2]));vecsort([X(a*b),X(a*conj(b))],1);
      G(p)=qfbsolve(Qfb(5,5,1),p)*[2+u,1]~;
      X(z)=vecsort([Z(z),Z(z*u^2),Z(z/u^2)],1)[1];
      Z(z)=local(t=z*sign(imag(z)),a=real(t),b=imag(t));[b,max(a-2*b,-a-3*b)];
      {A=4065702994722252685573484796054334194691713593576645739409115721859519;
      u=quadunit(5);S=R(factorint(A,6)[,1]);T=round(gettime/10^3);
      for(k=1,2,print("x="S[k][1]);print("y="S[k][2]));print(T" seconds");}

      x=8742252927800705984069016007531927
      y=42652016277694077218687373764822402
      x=24507765935843939778835994638318507
      y=8131530641557000519732930155331538
      119 seconds

      David
    • djbroadhurst
      ... [4] is meaningless, as it stands. You should write a double mod: 4. (1+x)^p = 1-x mod(x^2-a,p) ... There is no reason whatsoever to believe that [1] to [4]
      Message 50 of 50 , Sep 29, 2011
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "bhelmes_1" <bhelmes@...> wrote:

        > 1. let a jacobi (a, p)=-1
        > 2. let a^(p-1)/2 = -1 mod p
        > 3. a^6 =/= 1 mod p
        > 4. (1+sqrt (a))^p = 1-sqrt (a)

        [4] is meaningless, as it stands.
        You should write a double mod:

        4. (1+x)^p = 1-x mod(x^2-a,p)

        > 1. Is it possible that there are other exceptions

        There is no reason whatsoever to believe that
        [1] to [4] establish that p is prime. Morevoer,
        some folk believe that, for every epsilon > 0,
        the number of pseudoprimes less than x may
        exceed x^(1-epsilon), for /sufficiently/ large x.

        > 2....
        > there is a cyclic order ...

        > 3....
        > there is a cyclic order ...

        The group of units (Z/nZ)* is /not/ cyclic
        if n has at least two distinct odd prime fators.

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