modular_cyclotomic_polynomial.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 27 May 2019
# https://github.com/trizen

# Efficient formula for computing the n-th cyclotomic polynomial.

# Formula:
#   cyclotomic(n, x) = Prod_{d|n} (x^(n/d) - 1)^moebius(d)

# Optimization: by generating only the squarefree divisors of n and keeping track of
# the number of prime factors of each divisor, we do not need the Moebius function.

# See also:
#   https://en.wikipedia.org/wiki/Cyclotomic_polynomial

func modular_cyclotomic_polynomial(n, x, m) {

    var d = []
    for p in (n.factor.uniq) {
        d << d.map_2d {|q,e| [(p*q)%m, e+1] }...
        d << [p, 1]
    }

    d << [1, 0]

    var prod = 1

    for p,e in (d) {
        var t = powmod(x, n/p, m)-1
        t = invmod(t, m) if e.is_odd
        prod *= t   #=
        prod %= m   #=
    }

    return prod
}

say 20.of { modular_cyclotomic_polynomial(_, 2, 2017) }     #=> [0, 1, 3, 7, 5, 31, 3, 127, 17, 73, 11, 30, 13, 123, 43, 151, 257, 1983, 57, 1884]