Primality Test Using Chebyshev Polynomials

sci.math #256904 (13 + 2533 more)                                [1]+-[1]--[1]
From: rayes@goat.mcs.kent.edu ( Mohamed Omar Rayes)                 \-[1]
[1] Primality Test Using Chebyshev Polynomials!
Date: Wed Feb 18 16:45:44 EST 1998
An odd integer n > 0 is prime if and only if the Chebyshev
polynomial of the first kind T(n,x), divided by x, is irreducible over the integers.
For a proof, see
Technical report Title: Factorization of Chebyshev Polynomials, Number:ICM-199802-0001
--
   Education, my friend, is the greatest profession in the world.
Where else can so much be accomplished for so many? The feelings
of achievement  and satisfaction are life-long and life-sustaining.
As a leader in this phenomenal process called education, you have
a future. Do not cheat yourself and all those others who look to you
for leadership. Establish the standard, be the exemplar, and set the pace!
End of article 256904 (of 257282) -- what next? [npq]

sci.math #256987 (12 + 2533 more)                                (1)+-[1]--[1]
Date: Thu Feb 19 08:26:53 EST 1998                                  \-[1]
From: Dario Alejandro Alpern 
[1] Re: Primality Test Using Chebyshev Polynomials!
>
Very interesting, but how much does it help? Suppose that we have a 40-digit
number that we want to check whether it is prime or not. Then we have a
computer, imagine what are the values of the coefficients of that polynomial)
and finally we have to prove it is irreducible over the integers!!
Do you have a more complicated test?
--
Dario Alejandro Alpern
Buenos Aires - Argentina
http://members.tripod.com/~alpertron      (en castellano)
http://members.tripod.com/~alpertron/ENGLISH.HTM  (English)
Si su navegador no soporta JavaScript:
http://members.tripod.com/~alpertron/INDEX2.HTM
If your browser does not support JavaScript:
http://members.tripod.com/~alpertron/ENGLISH2.HTM
Antes era fanfarron... Ahora soy perfecto!!
End of article 256987 (of 257282) -- what next? [npq]

sci.math #257086 (11 + 2533 more)                                (1)+-(1)--[1]
From: NoJunkMail@this.address (Gerry Myerson)                       \-[1]
[1] Re: Primality Test Using Chebyshev Polynomials!
Date: Thu Feb 19 20:08:08 EST 1998
=> >
=> Very interesting, but how much does it help?
Assuming the result is correct, its value comes from reading it the other
way around: if n is an odd, positive integer, then the Chebyshev polynomial
of the first kind T(n,x), divided by x, is irreducible if and only if
n is prime. That is, it is valuable for what it tells us about the Chebyshev
polynomials, not for what it tells us about the primes.
Gerry Myerson (gerry@mpce.mq.edu.au)

From: Robin Chapman                             \-[1]
[1] Re: Primality Test Using Chebyshev Polynomials!
Date: Fri Feb 20 05:35:18 EST 1998
Its roots are the non-zero numbers of the form cos(pi/2n + 2j pi)
where j is an integer. They include cos(pi/2n) whic generates the
real subfield of the cyclotomic field Q(exp(2 pi i/4n)). This cyclotomic
field has degree phi(4n) = 2 phi(n) (where phi is the Euler function)
and its real subfield has degree phi(n) [this is due to the
irreducibility of the cyclotomic polynomials]. So the minimal polynomial of
cos(pi/2n) has degree phi(n), and so equals the Chebyshev divided by x
iff phi(n) = n-1 iff n is prime.
A related but simpler "primality test" is that p is prime iff
Of course both of these "tests" are useless in practical terms.
Robin Chapman                           "256 256 256.
Department of Mathematics                O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK        12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk                   2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html  Iain M. Banks - Feersum Endjinn
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
End of article 257164 (of 257282) -- what next? [npq]

See also
http://icm.mcs.kent.edu/reports/1999/chebpol.pdf
http://icm.mcs.kent.edu/reports/1998/cheby1.pdf
Both of which deal with integer primality and Chebyshev polynomials. Thank you very much. Mohamed Omar Rayes