Cyclotomic polynomial: Difference between revisions
Content added Content deleted
m (J: fix "skip zero" optimization in pDiv) |
(J: add some comments) |
||
Line 2,062: | Line 2,062: | ||
end.q |
end.q |
||
}}</lang> |
}}</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: |
Task examples: |