Cyclotomic polynomial: Difference between revisions
J: add some comments
m (J: fix "skip zero" optimization in pDiv) |
(J: add some comments) |
||
Line 2,062:
end.q
}}</lang>
If you take all the divisors of a number. (For example, for 12, the divisors are: 1, 2, 3, 4, 6 and 12) and find the product of their cyclotomic polynomials (for example, for 12, x-1, x+1, x<sup>2</sup>+x+1, x<sup>2</sup>+1, x<sup>2</sup>-x+1, and x<sup>4</sup>-x<sup>2</sup>+1) you get x<sup>n</sup>-1 (for 12, that would of course be x<sup>12</sup>-1).
Notes:
* the coefficients of a cyclotomic polynomials after 1 form a palindrome (that's the <tt>q#1</tt> phrase in the implementation).
* the coefficients of the cyclotomic polynomial for a prime number has as many terms as that number, and the coefficients are all 1.
* powers of primes add zero coefficients to the polynomial (that's the <tt>,(y%*/q) {."0</tt> ... phrase in the implementation). This means that we can mostly ignore powers of prime numbers -- they're just going to correspond to zeros we add to the base polynomial.
* an even base cyclotomic polynomial is the same as the corresponding odd base cyclotomic polynomial except with x replaced by negative x. (that's the <tt>(* 1 _1 $~ #)</tt> phrase in the implementation.
* To deal with the general case, we use polynomial division, x<sup>n</sup>-1 divided by the polynomial product the cyclotomic polynomials of the proper divisors of number we're looking for.
Task examples:
| |||