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

25241Re: 4 Fermat and 1 Lucas [freely admitted by its author to be hopeless]

Expand Messages
  • djbroadhurst
    Jul 19, 2013
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "paulunderwooduk" <paulunderwood@...> wrote:

      > Francois Arnault's paper, which I must learn

      Here, as patiently as I am able, is how to fool any "tst(n,a)"
      with, at is heart, in general terms, a Lucas test of type

      L^((n+1)/2) = +/- 1 mod (n, L^2 - y*L +1)

      with y some rational function of the parameter 'a' in terms
      of which you have defined your effete additional
      Fermat/Euler/M-R tests and gcd wriggles.

      For some obscure reason, your last choice was
      y = 2*(5*a^2-1)/(3*a^2+1). Now you have made a new choice.
      But who cares? The fooling method would be the same.

      OK, Paul? Have you got that? All we care about,
      for Lucas, are powers of L mod (n, L^2 - y*L + 1).

      Then here is the trick.

      Chose some small odd number k > 1 (like k = 19 in my last hints)
      and semiprimes of the form n=p*q with primes p = -1 mod k
      and q = 1 + 2*k*m*(p-1), where m is small. (I usually choose m=1.)

      Then find the irreducible polynomial P(x), with degree
      eulerphi(k)/2, satisfied by 2*cos(2*Pi/k), and solve
      for P(+/-y) = 0 mod n. For k = 19, P(x) is

      ? print(algdep(2*cos(2*Pi/19),9))
      x^9 + x^8 - 8*x^7 - 7*x^6 + 21*x^5 + 15*x^4 - 20*x^3 - 10*x^2 + 5*x + 1

      Exercise: Show that with x = +/- 2*(5*a^2-1)/(3*a^2+1),
      the numerators give

      {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]);
      ...

      as in the Gremlins latest totally successful attack.

      Now all we have to do, for a given prime pair (p,q), is to
      find the roots of these bizarre polys, mod n, using
      polrootsmod and the CRT.

      Up to effete signs, we have solved the Lucas problem.
      Up to effete signs, we have solved all the additional
      Fermat/Euler bolt-ons, mod p. All that is left are the
      Fermats mod q. As is clear from Arnault, you will
      not need to spend long looping on p, k, m, to solve
      Fermats mod q = 1 + 2*k*m*(p-1), for at least one
      of the many chinese roots.

      That's it. All that can happen is that the deviser of the
      hopeless test may wriggle with gcds, and arbitrarily bolt on
      additional Fermats/Euler/M-R's, thereby filling PrimeNumbers
      with lots of noise that cannot change the fact that she/he is
      bound to lose, because, in your own words:

      > one parameter Lucas plus N Fermat/Euler/M-R PRP test
      > can be counterexampled

      End of story? End of long repetitious posts?

      David
    • Show all 11 messages in this topic