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, seeTechnical 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 AlpernSee also[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]

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