Re: [PrimeNumbers] An indirect primality test
- From: dkandadai <dkandadai@...>
> Let the large prime suspect have the shape of a quadraticSo x^2+x+1 or x^2+1?
> cyclotomic polynomial.
> Then a simple indirect test has theWell, 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.
> 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
> functions. In case this is not clear I will be only too
> happy to
> illustrate with an example.
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.
- INDIRECT PRIMALITY TEST OF LARGE PRIME SUSPECTS WITH THE SHAPE OF QUADRATIC
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]
- --- In email@example.com, Devaraj Kandadai <dkandadai@...> wrote:
>why do you precise "large" here, but then you say :
> INDIRECT PRIMALITY TEST OF LARGE PRIME SUSPECTS
> WITH THE SHAPE OF QUADRATIC CYCLOTOMIC EXPRESSIONS
> 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 polynomialNo need, this is trivial. since f(x) = 0 (mod f(x))
> 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.
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 numberbut 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 +If something is divisible by f(x_0) this does not necessarily mean that it is composite.
> 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).
(See below for an explanation.)
> Numerical illustration: Let x_0 = 4.aha... nice illustration of a failure !
> f(x_0) = 4^2 + 1 = 17;
> such that f(x_0) is composite
With this, I don't even need to give further explanations on my earlier statement.