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

Prime Test polynomial

Expand Messages
  • Kermit Rose
    http://www.mathpages.com/home/kmath347/kmath347.htm claims that the first exception to the conjecture that n is a prime if and only if f(r**n) = 0 (mod n)
    Message 1 of 6 , Nov 3, 2010
    • 0 Attachment
      http://www.mathpages.com/home/kmath347/kmath347.htm

      claims that the first exception to the conjecture that

      n is a prime if and only if f(r**n) = 0 (mod n)
      where r is any root of f(x) = x**5 - x**3 - 2x**2 + 1.

      is n = 2258745004684033 = 27439297 * 82317889.


      What is x**n mod n if

      x**5 = x**3 + 2 x**2 - 1?

      what procedure would be used to calculate

      the roots x**n mod n

      when x is constrained to satisfy

      x**5 = x**3 + 2 x**2 - 1?

      x**6 = x**4 + 2 x**3 - x

      x**7 = x**5 + 2 x**4 - x**2

      x**7 = (x**3 + 2 x**2 - 1) + 2 x**4 - x**2

      x**7 = 2 x**4 + x**3 + (2 - 1) x**2 - 1

      x**8 = 2 x**5 + x**4 + (2 - 1) x**3 - x

      x**8 = 2 [x**3 + 2 x**2 - 1] + x**4 + (2-1) x**3 - x

      x**8 = x**4 + (2+ 2 - 1) x**3 + (2 * 2) x**2 - x - 2*1

      Clearly this implies a recurrence relation on the
      coefficients of x**4, x**3, x**2, x, and 1.

      Then it is clear that

      x**n = 0 mod n if and only if

      x**n = a4 x**4 + a3 x**3 + a2 x**2 + a1 x + a0
      is, in mod n, some polynomial multiple of

      x**3 + 2 x**2 - 1 .


      2 x**4 + x**3 + (2 - 1) x**2 - 1

      2 x**4 + x**3 + x**2 - 1

      (x**3+2 x**2 -1)(b4 x**4 +b3 x**3 +b2 x**2 +b1 x + b0) =0 mod 7

      reduces to a 4th degree equation = 0 mod 7,
      which supposedly determines unique values of
      b4, b3, b2, b1, b0.

      It is reasonable to guess that if n is prime,
      that the corresponding b4,b3,b2,b1,b0 can always
      be solved mod n,

      but if n is not prime, it might not be possible
      to solve for the b4,b3,b2,b1,b0.

      It is still not clear what algorithm had probably been used to prove
      that x**n is not 0 mod n for each composite number tested.

      Another approach:

      f(x) = x**5 - x**3 - 2x**2 + 1.

      f(x**2) = x**10 - x**6 - 2 x**4 + 1
      = x**10 - x**6 + 1 mod 2

      f(x**3) = x**15 - x**9 - 2 x**6 + 1
      = x**15 - x**9 - 2 x**6 + 1 mod 3

      Is this polynomial = 0 mod 3?


      supposedly we could use the recurrence relations to reduce
      f(x**m) to a fourth degree polynomial, and determine whether or not it
      is equivalent to 0 mod m.

      Does anyone see a simpler approach?


      Kermit
    • Kermit Rose
      ... f(x) = x**5 - x**3 - 2x**2 + 1. f(r**n) = 0 (mod n) f(x**2) = x**10 - x**6 - 2 x**4 + 1 if f(x) = 0, then x**5 = x**3 + 2 x**2 - 1 x**6 = x**4 + 2 x**3 - x
      Message 2 of 6 , Nov 4, 2010
      • 0 Attachment
        On 11/4/2010 3:54 PM, Maximilian Hasler wrote:
        >
        > er, I'm not sure to understand.
        >
        > For primes p=2 or p=3, do we have f(r^p) = 0 (mod p) ??
        >
        > If so, for which of the roots ?
        >
        > M.

        f(x) = x**5 - x**3 - 2x**2 + 1.

        f(r**n) = 0 (mod n)

        f(x**2) = x**10 - x**6 - 2 x**4 + 1

        if f(x) = 0, then

        x**5 = x**3 + 2 x**2 - 1
        x**6 = x**4 + 2 x**3 - x
        x**7 = x**5 + 2 x**4 - x**2
        x**8 = x**6 + 2 x**5 - x**3
        x**9 = x**7 + 2 x**6 - x**4
        x**10 = x**8 + 2 x**7 - x**5

        f(x**2) = x**10 - x**6 - 2 x**4 + 1
        = [x**8 + 2 x**7 - x**5] - [x**4 + 2 x**3 - x ] - 2 x**4 + 1

        = x**8 + 2 x**7 - x**5 - x**4 - 2 x**3 + x - 2 x**4 + 1
        = x**8 + 2 x**7 - x**5 - 3 x**4 - 2 x**3 + x - 1
        = [x**6 + 2 x**5 - x**3] + 2 x**7 - x**5 - 3 x**4 - 2 x**3 + x - 1
        = 2 x**7 + x**6 + x**5 - 3 x**4 - 3 x**3 + x - 1
        = 2 [x**5 + 2 x**4 - x**2] + x**6 + x**5 - 3 x**4 - 3 x**3 + x - 1
        = x**6 + 3 x**5 + x**4 - 3 x**3 - 2 x**2 + x - 1
        = [ x**4 + 2 x**3 - x ] + 3 x**5 + x**4 - 3 x**3 - 2 x**2 + x - 1
        = 3 x**5 + 2 x**4 - x**3 - 2 x**2 - 1
        = 3 [ x**3 + 2 x**2 - 1 ] + 2 x**4 - x**3 - 2 x**2 - 1
        = 2 x**4 + 2 x**3 -4 = 0 mod 2

        Proves that for the prime 2, if x is ANY root of

        f(x) = x**5 - x**3 - 2x**2 + 1,

        then

        f(x**2) = 0 mod 2.


        Similar laborious proof can be constructed for
        f(x**3) = 0.


        Kermit
      • Maximilian Hasler
        I do agree that ... but I do not agree that ... For example, one root of f(x) is r1 = 0.64879067514879204822278147415791168556... and f( r^2 ) =
        Message 3 of 6 , Nov 4, 2010
        • 0 Attachment
          I do agree that

          > f(x**2) = 2 x**4 + 2 x**3 -4 (mod x**5 - x**3 - 2x**2 + 1)

          but I do not agree that

          > 2 x**4 + 2 x**3 -4 = 0 mod 2
          > if x is ANY root of
          > f(x) = x**5 - x**3 - 2x**2 + 1,

          For example, one root of f(x) is
          r1 = 0.64879067514879204822278147415791168556...

          and
          f( r^2 ) = 0.584270441039927278546515102139504666...

          which is not zero mod 2.

          Note that the roots of f are not integers, and therefore
          2 x is not = 0 (mod 2), i.e. a multiple of 2.

          Maximilian
        • Kermit Rose
          ... I see. Thank you for pointing out this distinction. It is only in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, 2) that (x**2)**5 - (x**2)**3 -
          Message 4 of 6 , Nov 5, 2010
          • 0 Attachment
            On 11/4/2010 11:09 PM, Maximilian Hasler wrote:
            >
            > I do agree that
            >
            >> f(x**2) = 2 x**4 + 2 x**3 -4 (mod x**5 - x**3 - 2x**2 + 1)
            >
            > but I do not agree that
            >
            >> 2 x**4 + 2 x**3 -4 = 0 mod 2
            >> if x is ANY root of
            >> f(x) = x**5 - x**3 - 2x**2 + 1,
            >
            > For example, one root of f(x) is
            > r1 = 0.64879067514879204822278147415791168556...
            >
            > and
            > f( r^2 ) = 0.584270441039927278546515102139504666...
            >
            > which is not zero mod 2.
            >
            > Note that the roots of f are not integers, and therefore
            > 2 x is not = 0 (mod 2), i.e. a multiple of 2.


            I see.

            Thank you for pointing out this distinction.

            It is only in the ring

            polynomials mod ( x**5 - x**3 - 2x**2 + 1, 2)

            that (x**2)**5 - (x**2)**3 - 2(x**2)**2 + 1 = 0

            Is it true that for every positive prime p,

            that in the ring

            polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),

            that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?


            Is this type of relationship true for most irreducible polynomials?

            for all irreducible polynomials?

            for any polynomial?

            What condition, if any, must be imposed on a polynomial F,
            in order for it to be true,


            that for any positive prime q,


            that in the ring of polynomials mod (F(x),q)

            that F(x**q) = 0?


            Kermit
          • djbroadhurst
            ... Yes. Moreover there are no pseudoprimes less than 10^5: f(x)=x^5-x^3-2*x^2+1; for(p=2,10^5,if(isprime(p)!=(0==f(Mod(Mod(1,p)*x,f(x))^p)),print(p))); [The
            Message 5 of 6 , Nov 5, 2010
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              Kermit Rose <kermit@...> asked:

              > Is it true that for every positive prime p,
              > that in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),
              > that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?

              Yes. Moreover there are no pseudoprimes less than 10^5:

              f(x)=x^5-x^3-2*x^2+1;
              for(p=2,10^5,if(isprime(p)!=(0==f(Mod(Mod(1,p)*x,f(x))^p)),print(p)));

              [The rest is silence.]

              David
            • Kermit Rose
              ... Yes. I am ok with using the language of ring polynomial mod ( particular polynomial, integer). I will not quibble with you about whether or not it is
              Message 6 of 6 , Nov 5, 2010
              • 0 Attachment
                On 11/5/2010 2:22 PM, Maximilian Hasler wrote:
                >
                > On Fri, Nov 5, 2010 at 10:18 AM, djbroadhurst<d.broadhurst@...> wrote:
                >>
                >>
                >> --- In primenumbers@yahoogroups.com,
                >> Kermit Rose<kermit@...> asked:
                >>
                >>> Is it true that for every positive prime p,
                >>> that in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),
                >>> that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?
                >
                > This is a valid formulation ; not so, to my eyes, the one in terms of
                > the roots of that polynomial, which are irrational numbers x=r[i] for
                > which e.g. p*x is not an element of pZ<=> congruent to zero (mod p).
                >
                > M.
                >


                Yes. I am ok with using the language of

                ring polynomial mod ( particular polynomial, integer).

                I will not quibble with you about whether or not it is valid to
                define parity for numbers in algebraic extensions of integers mod 2.


                Now that that is settled, how about my question?



                >>> Is it true that for every positive prime p,
                >>> that in the ring polynomials mod ( x**5 - x**3 - 2x**2 + 1, p),
                >>> that (x**p)**5 - (x**p)**3 - 2 (x**p)**2 + 1 = 0 ?



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