如何创建一个带有变量作为参数的Mod类型?

huangapple go评论70阅读模式
英文:

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

问题

这是您的Haskell代码的部分翻译:

{-# 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)
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 = (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)

关于错误的问题,您提到参数是正整数和正整数列表,但您在函数isMaxOrder中使用了Mod类型。您需要确保将Mod类型的参数限定为适当的类型。以下是可能的修改:

isMaxOrder :: Nat -> Integer -> [Integer] -> Integer -> Bool
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)

这些更改应该有助于解决类型相关的错误。如果问题仍然存在,请提供更多上下文,以便我可以进一步帮助您解决问题。

英文:

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 ((&gt;&lt;), (&lt;|), (|&gt;), Seq((:&lt;|)), Seq((:|&gt;)))
import Math.NumberTheory.ArithmeticFunctions
import GHC.TypeLits (Nat)
import Data.Mod
import Math.NumberTheory.Primes

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

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

fiboPair :: Integer -&gt; [Integer]
fiboPair n = take 2 $ dropWhile (&lt;= n) fibonacci

searchDir :: Integer -&gt; (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 &lt; den = (q,1)
  | otherwise = (q+1,(-1))
  where [num,den] = fiboPair (2*n)
        (q,r) = (n*num) `divMod` den

isMaxOrder :: Integral a =&gt; Nat -&gt; a -&gt; [a] -&gt; a -&gt; 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&#39;s a primitive root
-- if modulus has any primitive roots.
isMaxOrder modl car fac n = (modln ^% car) == modl1 &amp;&amp; allnot1
  where modln = (fromIntegral n) :: Mod modl
        modl1 = 1 :: Mod modl
        powns = map ((modln ^%) . (car `div`)) fac
        allnot1 = foldl (&amp;&amp;) 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 =&gt; Nat -&gt; a -&gt; [a] -&gt; a -&gt; 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 ‘(&amp;&amp;)’, namely ‘(modln ^% car) == modl1’
      In the expression: (modln ^% car) == modl1 &amp;&amp; allnot1
   |
43 | isMaxOrder modl car fac n = (modln ^% car) == modl1 &amp;&amp; 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 =&gt; Nat -&gt; a -&gt; [a] -&gt; a -&gt; 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 &amp;&amp; allnot1
            where
                modln = (fromIntegral n) :: Mod modl
                modl1 = 1 :: Mod modl
                powns = map ((modln ^%) . (car `div`)) fac
                allnot1 = foldl (&amp;&amp;) 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 =&gt; Nat -&gt; a -&gt; [a] -&gt; a -&gt; 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 &amp;&amp; allnot1
            where
                modln = (fromIntegral n) :: Mod modl
                modl1 = 1 :: Mod modl
                powns = map ((modln ^%) . (car `div`)) fac
                allnot1 = foldl (&amp;&amp;) 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 =&gt; Nat -&gt; a -&gt; [a] -&gt; a -&gt; 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.

答案1

得分: 1

你需要 modulo

isMaxOrder modl car fac n = case (modulo n modl, modulo 1 modl) of
(SomeMod modln, SomeMod modl1) -> ...

你也可以在不先解包的情况下使用生成的 SomeMod。所有通常的类型类实例都可用。

英文:

You need modulo.

isMaxOrder modl car fac n = case (modulo n modl, modulo 1 modl) of
    (SomeMod modln, SomeMod modl1) -&gt; ...

You can also use the resulting SomeMods without unwrapping them first if you like. All the usual typeclass instances are available.

huangapple
  • 本文由 发表于 2023年7月18日 12:05:26
  • 转载请务必保留本文链接:https://go.coder-hub.com/76709470.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定