An Indirect Primality Test
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 N. 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.
- Planetary Bugs
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff