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

Re: [PrimeNumbers] An indirect primality test

Expand Messages
  • Phil Carmody
    From: dkandadai ... So x^2+x+1 or x^2+1? ... Well, given that after several pages of random nonsense that s an insult to the
    Message 1 of 4 , Aug 2, 2008
    • 0 Attachment
      From: dkandadai <dkandadai@...>
      > Let the large prime suspect have the shape of a quadratic
      > cyclotomic polynomial.

      So x^2+x+1 or x^2+1?

      > Then a simple indirect test has the
      > following
      > steps: 1) program the failure functions (including the
      > second order
      > failure functions 2) check whether the suspect is covered
      > by any of
      > them. 3)if the result is negative the suspect is a prime
      > number. (For
      > details see heuristic and heuristic (contd) in
      > Planetmath.org (forum-
      > general questions PG/research). The logic is as follows: if
      > the suspect
      > is composite it should have satisfied one or more of the
      > failure
      > functions. In case this is not clear I will be only too
      > happy to
      > illustrate with an example.

      Well, given that after several pages of random nonsense that's an insult to the "post-graduate/research" moniker that the forum carries, I finally found a thread which indicates that you haven't got the faintest clue what constitutes a proof ('test' and 'heuristic' are about as diametrically opposed as you can get, for instance). Progressing to find the thread you refer to, I gave up after finding more of the same.

      Was there any reason you didn't simply reproduce your exposition here?

      Not having seen your test, my guess is that is fundamentally flawed, and that you've only tested it on a small range of candidates. My 2nd guess is that when you do make the test clearer here, Dr. Broadhurst will be the first to find a counter-example.

      Phil
    • Devaraj Kandadai
      INDIRECT PRIMALITY TEST OF LARGE PRIME SUSPECTS WITH THE SHAPE OF QUADRATIC CYCLOTOMIC EXPRESSIONS For the sake of this post I will confine myself to numbers
      Message 2 of 4 , May 26, 2009
      • 0 Attachment
        INDIRECT PRIMALITY TEST OF LARGE PRIME SUSPECTS WITH THE SHAPE OF QUADRATIC
        CYCLOTOMIC EXPRESSIONS


        For the sake of this post I will confine myself to numbers with the shape


        x^2 + 1.


        Preliminary remarks: 1) I am certain about this being a valid test.

        2) This is not a probabality test;

        3) I doubt whether it is a comparitively efficient test when the suspects

        are very large. Members' opinions invited..


        4)_ A property of polynomial functions: Let f(x) be a polynomial in x ( x

        belongs to Z), Then f(x + k*f(x)) is congruent to 0 (mod f(x)).

        Here k belongs to Z. This can be proved by Taylor's theorem.



        At this stage I would prefer to use failure function terminology:

        Definition of failure: A composite number

        Definition of failure function ( in the present context). x = x_0 +
        k*f(x_0)) =x_0 + k*(x_0^2+1) ; here x_0 is a specific value of x. This is
        because x = (x_0 + k*f(x_0)) , when substituted in f(x), results in failures
        (composites) exactly divisible by f(x_0).


        Numerical illustration: Let x_0 = 4. f(x_0) = 4^2 + 1 = 17; x = 4 + k*17
        generates values of x

        such that f(x_0) is composite ( all multiples of 17).

        Note: Whenever f(x) is composite each factor contributes a failure function.

        An important observation: whenever a number with the shape of a quadratic
        cyclotomic expression is composite, the relevant x MUST satisfy a prior
        failure function. This is because a composite number with the shape of a
        quadratic cyclotomic polynomial has one factor less than the relevant x.
        Hence the indirect test consists of just generating values of x by the prior
        failure functions and checking whether x_0

        (where x_0^2 + 1 is the large prime suspect) is generated by one or more of
        these failure functions.


        A numerical illustration of the logic: 99994^2 + 1 is prime because 99994 is
        not generated by any of the failure functions for 1 < x < 99994. On the
        other hand 12^2 + 1 =145 is composite since 12 is generated by the f.f. x =
        2 + 5*k.


        It may be possible to write a program that programs the failure functions
        and also checks whether a given x_0 is generated by these functions or not.


        [Non-text portions of this message have been removed]
      • Maximilian Hasler
        ... ? ... No need, this is trivial. since f(x) = 0 (mod f(x)) you can add any multiple of f(x) anywhere in an algebraic expression without changing the value
        Message 3 of 4 , May 26, 2009
        • 0 Attachment
          --- In primenumbers@yahoogroups.com, Devaraj Kandadai <dkandadai@...> wrote:
          >
          > INDIRECT PRIMALITY TEST OF LARGE PRIME SUSPECTS
          > WITH THE SHAPE OF QUADRATIC CYCLOTOMIC EXPRESSIONS

          why do you precise "large" here, but then you say :

          > 3) I doubt whether it is a comparitively efficient test when the
          > suspects are very large. Members' opinions invited..

          ?

          > 4)_ A property of polynomial functions: Let f(x) be a polynomial
          > in x ( x belongs to Z),
          > Then f(x + k*f(x)) is congruent to 0 (mod f(x)).
          > Here k belongs to Z. This can be proved by Taylor's theorem.

          No need, this is trivial. since f(x) = 0 (mod f(x))
          you can add any multiple of f(x) anywhere in an algebraic
          expression without changing the value (mod f(x)).
          Adding zero never changes anything (this is the definition of zero),
          so why should it be different in Z/f(x)Z ?


          > Definition of failure: A composite number

          but this definition does not cover all aspects of "failure"...
          and it disagrees with http://en.wikipedia.org/wiki/Failure
          (nice picture, b.t.w.)

          > Definition of failure function (in the present context). x = x_0 +
          > k*f(x_0)) =x_0 + k*(x_0^2+1) ; here x_0 is a specific value of x.
          > This is because x = (x_0 + k*f(x_0)) , when substituted in f(x),
          > results in failures (composites) exactly divisible by f(x_0).

          If something is divisible by f(x_0) this does not necessarily mean that it is composite.
          (See below for an explanation.)


          > Numerical illustration: Let x_0 = 4.
          > f(x_0) = 4^2 + 1 = 17;
          > such that f(x_0) is composite

          aha... nice illustration of a failure !

          With this, I don't even need to give further explanations on my earlier statement.

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