-- | Cyclotomic polynomials
-- 
-- See <https://en.wikipedia.org/wiki/Cyclotomic_polynomial>
--

{-# LANGUAGE DataKinds, TypeSynonymInstances, FlexibleContexts, FlexibleInstances, BangPatterns, ScopedTypeVariables #-}
module Math.Algebra.Polynomial.Univariate.Cyclotomic 
  ( cyclotomic
  , cyclotomicMoebius
  , cyclotomicNaive
  ) 
  where

--------------------------------------------------------------------------------

import Data.Ratio

import Data.Semigroup
import Data.Monoid

import qualified Math.Algebra.Polynomial.FreeModule as ZMod
import Math.Algebra.Polynomial.FreeModule ( FreeMod , FreeModule(..) , ZMod , QMod )

import Math.Algebra.Polynomial.Univariate

import Math.Algebra.Polynomial.Class
import Math.Algebra.Polynomial.Pretty
import Math.Algebra.Polynomial.Misc

--------------------------------------------------------------------------------

-- | test whether the product of cyclotomic polynomials @Phi_d$ for the divisors @d@ of @n@ is @x^n-1@
test_product :: Int -> Bool
test_product :: Int -> Bool
test_product Int
n = Univariate Integer "x"
lhs Univariate Integer "x" -> Univariate Integer "x" -> Bool
forall a. Eq a => a -> a -> Bool
== Univariate Integer "x"
forall (var :: Symbol). Univariate Integer var
rhs where
  lhs :: Univariate Integer "x"
lhs = [Univariate Integer "x"] -> Univariate Integer "x"
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [ Int -> Univariate Integer "x"
cyclotomic Int
d | Int
d <- Int -> [Int]
divisors Int
n ] 
  rhs :: Univariate Integer var
rhs = FreeMod Integer (U var) -> Univariate Integer var
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod Integer (U var) -> Univariate Integer var)
-> FreeMod Integer (U var) -> Univariate Integer var
forall a b. (a -> b) -> a -> b
$ [(U var, Integer)] -> FreeMod Integer (U var)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
n , Integer
1) , (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
0 , -Integer
1) ]

-- | Synonym to 'cyclotomicMoebius'
cyclotomic :: Int -> Univariate Integer "x" 
cyclotomic :: Int -> Univariate Integer "x"
cyclotomic = Int -> Univariate Integer "x"
cyclotomicMoebius 

--------------------------------------------------------------------------------
-- * Implementation via Moebius inversion

-- | Cyclotomic polynomials via Moebius inversion
cyclotomicMoebius :: Int -> Univariate Integer "x"
cyclotomicMoebius :: Int -> Univariate Integer "x"
cyclotomicMoebius = FreeMod Integer (U "x") -> Univariate Integer "x"
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod Integer (U "x") -> Univariate Integer "x")
-> (Int -> FreeMod Integer (U "x"))
-> Int
-> Univariate Integer "x"
forall b c a. (b -> c) -> (a -> b) -> a -> c
. QMod (U "x") -> FreeMod Integer (U "x")
forall b. Ord b => QMod b -> ZMod b
ZMod.unsafeZModFromQMod (QMod (U "x") -> FreeMod Integer (U "x"))
-> (Int -> QMod (U "x")) -> Int -> FreeMod Integer (U "x")
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Univariate Rational "x" -> QMod (U "x")
forall c (v :: Symbol). Univariate c v -> FreeMod c (U v)
unUni (Univariate Rational "x" -> QMod (U "x"))
-> (Int -> Univariate Rational "x") -> Int -> QMod (U "x")
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Univariate Rational "x"
cyclotomicMoebiusQ

cyclotomicMoebiusQ :: Int -> Univariate Rational "x" 
cyclotomicMoebiusQ :: Int -> Univariate Rational "x"
cyclotomicMoebiusQ Int
n = Univariate Rational "x"
-> Univariate Rational "x" -> Univariate Rational "x"
forall p. (Polynomial p, Fractional (CoeffP p)) => p -> p -> p
unsafeDivide (QMod (U "x") -> Univariate Rational "x"
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni QMod (U "x")
forall (var :: Symbol). FreeMod Rational (U var)
numer) (QMod (U "x") -> Univariate Rational "x"
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni QMod (U "x")
forall (var :: Symbol). FreeMod Rational (U var)
denom) where
  sqfd :: [(Int, Sign)]
sqfd   = Int -> [(Int, Sign)]
squareFreeDivisors Int
n 
  numer :: FreeMod Rational (U var)
numer  = [FreeMod Rational (U var)] -> FreeMod Rational (U var)
forall b c.
(Ord b, Monoid b, Eq c, Num c) =>
[FreeMod c b] -> FreeMod c b
ZMod.product [ Int -> FreeMod Rational (U var)
forall c (var :: Symbol). (Eq c, Num c) => Int -> FreeMod c (U var)
term Int
d | (Int
d,Sign
Plus ) <- [(Int, Sign)]
sqfd ]
  denom :: FreeMod Rational (U var)
denom  = [FreeMod Rational (U var)] -> FreeMod Rational (U var)
forall b c.
(Ord b, Monoid b, Eq c, Num c) =>
[FreeMod c b] -> FreeMod c b
ZMod.product [ Int -> FreeMod Rational (U var)
forall c (var :: Symbol). (Eq c, Num c) => Int -> FreeMod c (U var)
term Int
d | (Int
d,Sign
Minus) <- [(Int, Sign)]
sqfd ]
  term :: Int -> FreeMod c (U var)
term Int
d = [(U var, c)] -> FreeMod c (U var)
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ (Int -> U var
forall (var :: Symbol). Int -> U var
U (Int -> Int -> Int
forall a. Integral a => a -> a -> a
div Int
n Int
d) , c
1) , (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
0 , -c
1) ]

polynomialLongDivision :: forall p. (Polynomial p, Fractional (CoeffP p)) => p -> p -> (p,p)
polynomialLongDivision :: p -> p -> (p, p)
polynomialLongDivision p
p0 p
q = p -> p -> (p, p)
go p
forall p. AlmostPolynomial p => p
zeroP p
p0 where

  (BaseF p
bq,CoeffF p
cq) = case p -> Maybe (BaseF p, CoeffF p)
forall f. FreeModule f => f -> Maybe (BaseF f, CoeffF f)
findMaxTerm p
q of
    Just (BaseF p, CoeffF p)
bc -> (BaseF p, CoeffF p)
bc
    Maybe (BaseF p, CoeffF p)
Nothing -> [Char] -> (BaseF p, CoeffF p)
forall a. HasCallStack => [Char] -> a
error [Char]
"polynomialLongDivision: division by zero"

  go :: p -> p -> (p, p)
go !p
acc !p
p = case p -> Maybe (BaseF p, CoeffF p)
forall f. FreeModule f => f -> Maybe (BaseF f, CoeffF f)
findMaxTerm p
p of
    Maybe (BaseF p, CoeffF p)
Nothing      -> (p
acc,p
forall p. AlmostPolynomial p => p
zeroP)
    Just (BaseF p
bp,CoeffF p
cp) -> case BaseF p -> BaseF p -> Maybe (BaseF p)
forall m. Monomial m => m -> m -> Maybe m
divM BaseF p
bp BaseF p
bq of
      Maybe (BaseF p)
Nothing      -> (p
acc,p
p)
      Just BaseF p
br      -> let cr :: CoeffF p
cr = (CoeffF p
cpCoeffF p -> CoeffF p -> CoeffF p
forall a. Fractional a => a -> a -> a
/CoeffF p
cq)
                          u :: p
u  = CoeffP p -> p -> p
forall p. AlmostPolynomial p => CoeffP p -> p -> p
scaleP CoeffF p
CoeffP p
cr (MonomP p -> p -> p
forall p. AlmostPolynomial p => MonomP p -> p -> p
mulByMonomP BaseF p
MonomP p
br p
q)
                          p' :: p
p' = p
p p -> p -> p
forall a. Num a => a -> a -> a
- p
u
                          acc' :: p
acc' = (p
acc p -> p -> p
forall a. Num a => a -> a -> a
+ MonomP p -> CoeffP p -> p
forall p. AlmostPolynomial p => MonomP p -> CoeffP p -> p
monomP' BaseF p
MonomP p
br CoeffF p
CoeffP p
cr) 
                      in  p -> p -> (p, p)
go p
acc' p
p' 

divideMaybe :: (Polynomial p, Fractional (CoeffP p)) => p -> p -> Maybe p
divideMaybe :: p -> p -> Maybe p
divideMaybe p
p p
q = case p -> p -> (p, p)
forall p. (Polynomial p, Fractional (CoeffP p)) => p -> p -> (p, p)
polynomialLongDivision p
p p
q of
  (p
s,p
r) -> if p -> Bool
forall p. AlmostPolynomial p => p -> Bool
isZeroP p
r then p -> Maybe p
forall a. a -> Maybe a
Just p
s else Maybe p
forall a. Maybe a
Nothing

unsafeDivide :: (Polynomial p, Fractional (CoeffP p)) => p -> p -> p
unsafeDivide :: p -> p -> p
unsafeDivide p
p p
q = case p -> p -> Maybe p
forall p.
(Polynomial p, Fractional (CoeffP p)) =>
p -> p -> Maybe p
divideMaybe p
p p
q of
  Just p
s  -> p
s
  Maybe p
Nothing -> [Char] -> p
forall a. HasCallStack => [Char] -> a
error [Char]
"Polynomial/unsafeDivide: not divisible"

findMaxTerm :: FreeModule f => f -> Maybe (BaseF f, CoeffF f)
findMaxTerm :: f -> Maybe (BaseF f, CoeffF f)
findMaxTerm = FreeMod (CoeffF f) (BaseF f) -> Maybe (BaseF f, CoeffF f)
forall b c. Ord b => FreeMod c b -> Maybe (b, c)
ZMod.findMaxTerm (FreeMod (CoeffF f) (BaseF f) -> Maybe (BaseF f, CoeffF f))
-> (f -> FreeMod (CoeffF f) (BaseF f))
-> f
-> Maybe (BaseF f, CoeffF f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. f -> FreeMod (CoeffF f) (BaseF f)
forall a. FreeModule a => a -> FreeMod (CoeffF a) (BaseF a)
toFreeModule

--------------------------------------------------------------------------------
-- * Naive implementation

newtype E2PiI = E2PiI Rational deriving (E2PiI -> E2PiI -> Bool
(E2PiI -> E2PiI -> Bool) -> (E2PiI -> E2PiI -> Bool) -> Eq E2PiI
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: E2PiI -> E2PiI -> Bool
$c/= :: E2PiI -> E2PiI -> Bool
== :: E2PiI -> E2PiI -> Bool
$c== :: E2PiI -> E2PiI -> Bool
Eq,Eq E2PiI
Eq E2PiI
-> (E2PiI -> E2PiI -> Ordering)
-> (E2PiI -> E2PiI -> Bool)
-> (E2PiI -> E2PiI -> Bool)
-> (E2PiI -> E2PiI -> Bool)
-> (E2PiI -> E2PiI -> Bool)
-> (E2PiI -> E2PiI -> E2PiI)
-> (E2PiI -> E2PiI -> E2PiI)
-> Ord E2PiI
E2PiI -> E2PiI -> Bool
E2PiI -> E2PiI -> Ordering
E2PiI -> E2PiI -> E2PiI
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: E2PiI -> E2PiI -> E2PiI
$cmin :: E2PiI -> E2PiI -> E2PiI
max :: E2PiI -> E2PiI -> E2PiI
$cmax :: E2PiI -> E2PiI -> E2PiI
>= :: E2PiI -> E2PiI -> Bool
$c>= :: E2PiI -> E2PiI -> Bool
> :: E2PiI -> E2PiI -> Bool
$c> :: E2PiI -> E2PiI -> Bool
<= :: E2PiI -> E2PiI -> Bool
$c<= :: E2PiI -> E2PiI -> Bool
< :: E2PiI -> E2PiI -> Bool
$c< :: E2PiI -> E2PiI -> Bool
compare :: E2PiI -> E2PiI -> Ordering
$ccompare :: E2PiI -> E2PiI -> Ordering
$cp1Ord :: Eq E2PiI
Ord,Int -> E2PiI -> ShowS
[E2PiI] -> ShowS
E2PiI -> [Char]
(Int -> E2PiI -> ShowS)
-> (E2PiI -> [Char]) -> ([E2PiI] -> ShowS) -> Show E2PiI
forall a.
(Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
showList :: [E2PiI] -> ShowS
$cshowList :: [E2PiI] -> ShowS
show :: E2PiI -> [Char]
$cshow :: E2PiI -> [Char]
showsPrec :: Int -> E2PiI -> ShowS
$cshowsPrec :: Int -> E2PiI -> ShowS
Show)

instance Pretty E2PiI where
  pretty :: E2PiI -> [Char]
pretty (E2PiI Rational
y) = [Char]
"e^{2*pi*i*" [Char] -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
p [Char] -> ShowS
forall a. [a] -> [a] -> [a]
++ [Char]
"/" [Char] -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> [Char]
forall a. Show a => a -> [Char]
show Integer
q [Char] -> ShowS
forall a. [a] -> [a] -> [a]
++ [Char]
"}" where
    p :: Integer
p = Rational -> Integer
forall a. Ratio a -> a
numerator   Rational
y
    q :: Integer
q = Rational -> Integer
forall a. Ratio a -> a
denominator Rational
y

mod1 :: Rational -> Rational
mod1 :: Rational -> Rational
mod1 Rational
x = Rational
x Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
- Integer -> Rational
forall a. Num a => Integer -> a
fromInteger (Rational -> Integer
forall a b. (RealFrac a, Integral b) => a -> b
floor Rational
x)

mulE2PiI :: E2PiI -> E2PiI -> E2PiI
mulE2PiI :: E2PiI -> E2PiI -> E2PiI
mulE2PiI (E2PiI Rational
x) (E2PiI Rational
y) = Rational -> E2PiI
E2PiI (Rational -> Rational
mod1 (Rational -> Rational) -> Rational -> Rational
forall a b. (a -> b) -> a -> b
$ Rational
xRational -> Rational -> Rational
forall a. Num a => a -> a -> a
+Rational
y)

instance Semigroup E2PiI where
  <> :: E2PiI -> E2PiI -> E2PiI
(<>) = E2PiI -> E2PiI -> E2PiI
mulE2PiI

instance Monoid E2PiI where
  mempty :: E2PiI
mempty  = Rational -> E2PiI
E2PiI Rational
0
  mappend :: E2PiI -> E2PiI -> E2PiI
mappend = E2PiI -> E2PiI -> E2PiI
mulE2PiI

half :: Rational
half :: Rational
half = Rational
1Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/Rational
2

reduce :: ZMod E2PiI -> Either (ZMod E2PiI) Integer
reduce :: ZMod E2PiI -> Either (ZMod E2PiI) Integer
reduce ZMod E2PiI
input = 
  case ZMod E2PiI -> Maybe (E2PiI, Integer)
forall b c. Ord b => FreeMod c b -> Maybe (b, c)
ZMod.findMaxTerm ZMod E2PiI
input of
    Maybe (E2PiI, Integer)
Nothing           -> Integer -> Either (ZMod E2PiI) Integer
forall a b. b -> Either a b
Right Integer
0
    Just (E2PiI Rational
y, Integer
c) 
      | Rational
y Rational -> Rational -> Bool
forall a. Eq a => a -> a -> Bool
== Rational
0        -> Integer -> Either (ZMod E2PiI) Integer
forall a b. b -> Either a b
Right   Integer
c
      | Bool
otherwise     -> case Rational -> Maybe (ZMod E2PiI)
minimalZeroSumCircle Rational
y of
          Just ZMod E2PiI
circle     -> ZMod E2PiI -> Either (ZMod E2PiI) Integer
reduce (ZMod E2PiI -> Either (ZMod E2PiI) Integer)
-> ZMod E2PiI -> Either (ZMod E2PiI) Integer
forall a b. (a -> b) -> a -> b
$ ZMod E2PiI -> ZMod E2PiI -> ZMod E2PiI
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.sub ZMod E2PiI
input (Integer -> ZMod E2PiI -> ZMod E2PiI
forall b c. (Ord b, Eq c, Num c) => c -> FreeMod c b -> FreeMod c b
ZMod.scale Integer
c ZMod E2PiI
circle)
          Maybe (ZMod E2PiI)
Nothing         -> ZMod E2PiI -> Either (ZMod E2PiI) Integer
forall a b. a -> Either a b
Left ZMod E2PiI
input

minimalZeroSumCircle :: Rational -> Maybe (ZMod E2PiI)
minimalZeroSumCircle :: Rational -> Maybe (ZMod E2PiI)
minimalZeroSumCircle Rational
y 
  | Rational
y Rational -> Rational -> Bool
forall a. Ord a => a -> a -> Bool
< Rational
half     = Maybe (ZMod E2PiI)
forall a. Maybe a
Nothing
  | Integer
r Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1       = ZMod E2PiI -> Maybe (ZMod E2PiI)
forall a. a -> Maybe a
Just (ZMod E2PiI -> Maybe (ZMod E2PiI))
-> ZMod E2PiI -> Maybe (ZMod E2PiI)
forall a b. (a -> b) -> a -> b
$ [(E2PiI, Integer)] -> ZMod E2PiI
forall c b. (Eq c, Num c, Ord b) => [(b, c)] -> FreeMod c b
ZMod.fromList [ (Rational -> E2PiI
E2PiI (Integer
i Integer -> Integer -> Rational
forall a. Integral a => a -> a -> Ratio a
% Integer
q) , Integer
1) | Integer
i<-[Integer
0..Integer
qInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
1] ]
  | Bool
otherwise    = Maybe (ZMod E2PiI)
forall a. Maybe a
Nothing
  where
    p :: Integer
p = Rational -> Integer
forall a. Ratio a -> a
numerator   Rational
y
    q :: Integer
q = Rational -> Integer
forall a. Ratio a -> a
denominator Rational
y
    r :: Integer
r = Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
p

--------------------------------------------------------------------------------

type X   = U "x"
type Pre = ZMod E2PiI

instance IsSigned Pre where
  signOf :: ZMod E2PiI -> Maybe Sign
signOf ZMod E2PiI
_ = Sign -> Maybe Sign
forall a. a -> Maybe a
Just Sign
Plus

preCyclotomic :: Int -> FreeMod Pre X
preCyclotomic :: Int -> FreeMod (ZMod E2PiI) (U "x")
preCyclotomic Int
n = [FreeMod (ZMod E2PiI) (U "x")] -> FreeMod (ZMod E2PiI) (U "x")
forall b c.
(Ord b, Monoid b, Eq c, Num c) =>
[FreeMod c b] -> FreeMod c b
ZMod.product [FreeMod (ZMod E2PiI) (U "x")]
forall (var :: Symbol). [FreeMod (ZMod E2PiI) (U var)]
terms where
  terms :: [FreeMod (ZMod E2PiI) (U var)]
terms = [ FreeMod (ZMod E2PiI) (U var)
-> FreeMod (ZMod E2PiI) (U var) -> FreeMod (ZMod E2PiI) (U var)
forall b c.
(Ord b, Eq c, Num c) =>
FreeMod c b -> FreeMod c b -> FreeMod c b
ZMod.sub FreeMod (ZMod E2PiI) (U var)
forall (var :: Symbol). FreeMod (ZMod E2PiI) (U var)
x (ZMod E2PiI -> FreeMod (ZMod E2PiI) (U var)
forall b c. (Monoid b, Eq c, Num c) => c -> FreeMod c b
ZMod.konst (Int -> ZMod E2PiI
forall a. Integral a => a -> ZMod E2PiI
e Int
k)) | Int
k <- [Int
1..Int
n] , Int -> Int -> Int
forall a. Integral a => a -> a -> a
gcd Int
k Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 ] where
  x :: FreeMod (ZMod E2PiI) (U var)
x   = U var -> FreeMod (ZMod E2PiI) (U var)
forall c b. Num c => b -> FreeMod c b
ZMod.generator (Int -> U var
forall (var :: Symbol). Int -> U var
U Int
1)
  qn :: Rational
qn  = Int -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n :: Rational
  e :: a -> ZMod E2PiI
e a
k = E2PiI -> ZMod E2PiI
forall c b. Num c => b -> FreeMod c b
ZMod.generator (E2PiI -> ZMod E2PiI) -> E2PiI -> ZMod E2PiI
forall a b. (a -> b) -> a -> b
$ Rational -> E2PiI
E2PiI (Rational -> Rational
mod1 (Rational -> Rational) -> Rational -> Rational
forall a b. (a -> b) -> a -> b
$ a -> Rational
forall a b. (Integral a, Num b) => a -> b
fromIntegral a
k Rational -> Rational -> Rational
forall a. Fractional a => a -> a -> a
/ Rational
qn) :: ZMod E2PiI

-- | Naive algorithm (using the direct definition of cyclotomic polynomials, and reducing
-- sums of roots of unity till they become integers)
cyclotomicNaive :: Int -> Univariate Integer "x"
cyclotomicNaive :: Int -> Univariate Integer "x"
cyclotomicNaive = FreeMod Integer (U "x") -> Univariate Integer "x"
forall coeff (var :: Symbol).
FreeMod coeff (U var) -> Univariate coeff var
Uni (FreeMod Integer (U "x") -> Univariate Integer "x")
-> (Int -> FreeMod Integer (U "x"))
-> Int
-> Univariate Integer "x"
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ZMod E2PiI -> Integer)
-> FreeMod (ZMod E2PiI) (U "x") -> FreeMod Integer (U "x")
forall b c2 c1.
(Ord b, Eq c2, Num c2) =>
(c1 -> c2) -> FreeMod c1 b -> FreeMod c2 b
ZMod.mapCoeff ZMod E2PiI -> Integer
fun (FreeMod (ZMod E2PiI) (U "x") -> FreeMod Integer (U "x"))
-> (Int -> FreeMod (ZMod E2PiI) (U "x"))
-> Int
-> FreeMod Integer (U "x")
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> FreeMod (ZMod E2PiI) (U "x")
preCyclotomic where
  fun :: ZMod E2PiI -> Integer
fun ZMod E2PiI
term = case ZMod E2PiI -> Either (ZMod E2PiI) Integer
reduce ZMod E2PiI
term of
    Right Integer
c -> Integer
c
    Left {} -> [Char] -> Integer
forall a. HasCallStack => [Char] -> a
error [Char]
"cyclotomicNaive: shouldn't happen" 

--------------------------------------------------------------------------------