1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
-- |
-- Module: Math.NumberTheory.Moduli.Multiplicative
-- Copyright: (c) 2017 Andrew Lelechenko
-- Licence: MIT
-- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Multiplicative groups of integers modulo m.
--
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE ViewPatterns #-}
module Math.NumberTheory.Moduli.Multiplicative
( -- * Multiplicative group
MultMod
, multElement
, isMultElement
, invertGroup
-- * Primitive roots
, PrimitiveRoot
, unPrimitiveRoot
, isPrimitiveRoot
, discreteLogarithm
) where
import Control.Monad
import Data.Constraint
import Data.Mod
import Data.Semigroup
import GHC.TypeNats (KnownNat, natVal)
import Numeric.Natural
import Math.NumberTheory.Moduli.Internal
import Math.NumberTheory.Moduli.Singleton
import Math.NumberTheory.Primes
-- | This type represents elements of the multiplicative group mod m, i.e.
-- those elements which are coprime to m. Use @isMultElement@ to construct.
newtype MultMod m = MultMod {
multElement :: Mod m -- ^ Unwrap a residue.
} deriving (Eq, Ord, Show)
instance KnownNat m => Semigroup (MultMod m) where
MultMod a <> MultMod b = MultMod (a * b)
stimes k a@(MultMod a')
| k >= 0 = MultMod (a' ^% k)
| otherwise = invertGroup $ stimes (-k) a
-- ^ This Semigroup is in fact a group, so @stimes@ can be called with a negative first argument.
instance KnownNat m => Monoid (MultMod m) where
mempty = MultMod 1
instance KnownNat m => Bounded (MultMod m) where
minBound = MultMod 1
maxBound = MultMod (-1)
-- | Attempt to construct a multiplicative group element.
isMultElement :: KnownNat m => Mod m -> Maybe (MultMod m)
isMultElement a = if unMod a `gcd` natVal a == 1
then Just $ MultMod a
else Nothing
-- | For elements of the multiplicative group, we can safely perform the inverse
-- without needing to worry about failure.
invertGroup :: KnownNat m => MultMod m -> MultMod m
invertGroup (MultMod a) = case invertMod a of
Just b -> MultMod b
Nothing -> error "Math.NumberTheory.Moduli.invertGroup: failed to invert element"
-- | 'PrimitiveRoot' m is a type which is only inhabited
-- by <https://en.wikipedia.org/wiki/Primitive_root_modulo_n primitive roots> of m.
newtype PrimitiveRoot m = PrimitiveRoot
{ unPrimitiveRoot :: MultMod m -- ^ Extract primitive root value.
}
deriving (Eq, Show)
-- | Check whether a given modular residue is
-- a <https://en.wikipedia.org/wiki/Primitive_root_modulo_n primitive root>.
--
-- >>> :set -XDataKinds
-- >>> import Data.Maybe
-- >>> isPrimitiveRoot (fromJust cyclicGroup) (1 :: Mod 13)
-- Nothing
-- >>> isPrimitiveRoot (fromJust cyclicGroup) (2 :: Mod 13)
-- Just (PrimitiveRoot {unPrimitiveRoot = MultMod {multElement = (2 `modulo` 13)}})
isPrimitiveRoot
:: (Integral a, UniqueFactorisation a)
=> CyclicGroup a m
-> Mod m
-> Maybe (PrimitiveRoot m)
isPrimitiveRoot cg r = case proofFromCyclicGroup cg of
Sub Dict -> do
r' <- isMultElement r
guard $ isPrimitiveRoot' cg (fromIntegral (unMod r))
return $ PrimitiveRoot r'
-- | Computes the discrete logarithm. Currently uses a combination of the baby-step
-- giant-step method and Pollard's rho algorithm, with Bach reduction.
--
-- >>> :set -XDataKinds
-- >>> import Data.Maybe
-- >>> let cg = fromJust cyclicGroup :: CyclicGroup Integer 13
-- >>> let rt = fromJust (isPrimitiveRoot cg 2)
-- >>> let x = fromJust (isMultElement 11)
-- >>> discreteLogarithm cg rt x
-- 7
discreteLogarithm :: CyclicGroup Integer m -> PrimitiveRoot m -> MultMod m -> Natural
discreteLogarithm cg (multElement . unPrimitiveRoot -> a) (multElement -> b) = case cg of
CG2
-> 0
-- the only valid input was a=1, b=1
CG4
-> if unMod b == 1 then 0 else 1
-- the only possible input here is a=3 with b = 1 or 3
CGOddPrimePower (unPrime -> p) k
-> discreteLogarithmPP p k (toInteger (unMod a)) (toInteger (unMod b))
CGDoubleOddPrimePower (unPrime -> p) k
-> discreteLogarithmPP p k (toInteger (unMod a) `rem` p^k) (toInteger (unMod b) `rem` p^k)
-- we have the isomorphism t -> t `rem` p^k from (Z/2p^kZ)* -> (Z/p^kZ)*
|
