How do I make a Mod type with a variable as a parameter?

Question

Here's my partially written Haskell code to search for a number of maximum multiplicative order:

{-# LANGUAGE DataKinds #-}
module Cryptography.WringTwistree.Mix3
  ( mix
  , fiboPair
  , searchDir
  ) where

import Data.Bits
import Data.Word
import qualified Data.Sequence as Seq
import Data.Sequence ((><), (<|), (|>), Seq((:<|)), Seq((:|>)))
import Math.NumberTheory.ArithmeticFunctions
import GHC.TypeLits (Nat)
import Data.Mod
import Math.NumberTheory.Primes

mix :: (Num t,Bits t) => t -> t -> t -> t
mix a b c = xor a mask
  where mask = (a .|. b .|. c) - (a .&. b .&. c)

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

fiboPair :: Integer -> [Integer]
fiboPair n = take 2 $ dropWhile (<= n) fibonacci

searchDir :: Integer -> (Integer,Int)
-- fst=n/φ rounded to nearest. snd=+1 or -1, indicating search direction.
-- e.g. if n=89, returns (55,1). Search 55,56,54,57,53...
-- if n=144, returns (89,(-1)). Search 89,88,90,87,91...
searchDir n
  | r*2 < den = (q,1)
  | otherwise = (q+1,(-1))
  where [num,den] = fiboPair (2*n)
        (q,r) = (n*num) `divMod` den

isMaxOrder :: Integral a => Nat -> a -> [a] -> a -> Bool
-- isMaxOrder modl car fac n
-- where modl is the modulus, car is its Carmichael function,
-- fac is the set of prime factors of car (without multiplicities),
-- and n is the number being tested.
-- Returns true if n has maximum order, which implies it's a primitive root
-- if modulus has any primitive roots.
isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
  where modln = (fromIntegral n) :: Mod modl
        modl1 = 1 :: Mod modl
        powns = map ((modln ^%) . (car `div`)) fac
        allnot1 = foldl (&&) True (map (/= modl1) powns)

I try to compile this and get these errors:

/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:43:36: error:
    • Could not deduce (GHC.TypeNats.KnownNat m0)
        arising from a use of ‘^%’
      from the context: Integral a
        bound by the type signature for:
                   isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
        at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
      The type variable ‘m0’ is ambiguous
    • In the first argument of ‘(==)’, namely ‘(modln ^% car)’
      In the first argument of ‘(&&)’, namely ‘(modln ^% car) == modl1’
      In the expression: (modln ^% car) == modl1 && allnot1
   |
43 | isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
   |                                    ^^

/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:44:18: error:
    • Could not deduce (GHC.TypeNats.KnownNat modl1)
        arising from a use of ‘fromIntegral’
      from the context: Integral a
        bound by the type signature for:
                   isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
        at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
      Possible fix:
        add (GHC.TypeNats.KnownNat modl1) to the context of
          an expression type signature:
            forall (modl1 :: Nat). Mod modl1
    • In the expression: (fromIntegral n) :: Mod modl
      In an equation for ‘modln’: modln = (fromIntegral n) :: Mod modl
      In an equation for ‘isMaxOrder’:
          isMaxOrder modl car fac n
            = (modln ^% car) == modl1 && allnot1
            where
                modln = (fromIntegral n) :: Mod modl
                modl1 = 1 :: Mod modl
                powns = map ((modln ^%) . (car `div`)) fac
                allnot1 = foldl (&&) True (map (/= modl1) powns)
   |
44 |   where modln = (fromIntegral n) :: Mod modl
   |                  ^^^^^^^^^^^^

/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:45:17: error:
    • Could not deduce (GHC.TypeNats.KnownNat modl1)
        arising from the literal ‘1’
      from the context: Integral a
        bound by the type signature for:
                   isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
        at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
      Possible fix:
        add (GHC.TypeNats.KnownNat modl1) to the context of
          an expression type signature:
            forall (modl1 :: Nat). Mod modl1
    • In the expression: 1 :: Mod modl
      In an equation for ‘modl1’: modl1 = 1 :: Mod modl
      In an equation for ‘isMaxOrder’:
          isMaxOrder modl car fac n
            = (modln ^% car) == modl1 && allnot1
            where
                modln = (fromIntegral n) :: Mod modl
                modl1 = 1 :: Mod modl
                powns = map ((modln ^%) . (car `div`)) fac
                allnot1 = foldl (&&) True (map (/= modl1) powns)
   |
45 |         modl1 = 1 :: Mod modl
   |                 ^

/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:46:29: error:
    • Could not deduce (GHC.TypeNats.KnownNat m1)
        arising from a use of ‘^%’
      from the context: Integral a
        bound by the type signature for:
                   isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
        at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
      The type variable ‘m1’ is ambiguous
      Relevant bindings include
        powns :: [Mod m1]
          (bound at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:46:9)
    • In the first argument of ‘(.)’, namely ‘(modln ^%)’
      In the first argument of ‘map’, namely ‘((modln ^%) . (car `div`))’
      In the expression: map ((modln ^%) . (car `div`)) fac
   |
46 |         powns = map ((modln ^%) . (car `div`)) fac
   |                             ^^

The parameters to isMaxOrder are positive integers and a list of positive integers. I first tried making modl of type a, then tried Nat (and importing GHC.TypeLits unqualified resulted in a conflict of mod or something). I can type 1 :: Mod 89 and it works, but 1 :: Mod (fromIntegral 89) results in an error.

How do I make a Mod type with a variable as a parameter?

Answers (1)

Related Questions