## Re: [PrimeNumbers] An indirect primality test

Expand Messages
• 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
> 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
• 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.

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]
• ... ? ... 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
>
> 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.