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
|
{-# LANGUAGE RankNTypes #-}
{-# OPTIONS_GHC -fno-warn-type-defaults #-}
module Math.NumberTheory.PrimitiveRootsBench
( benchSuite
) where
import Test.Tasty.Bench
import Data.Constraint
import Data.Maybe
import Math.NumberTheory.Moduli.Multiplicative
import Math.NumberTheory.Moduli.Singleton
import Math.NumberTheory.Primes
primRootWrap :: Integer -> Word -> Integer -> Bool
primRootWrap p k g = case fromJust $ cyclicGroupFromFactors [(p', k)] of
Some cg -> case proofFromCyclicGroup cg of
Sub Dict -> isJust $ isPrimitiveRoot cg (fromInteger g)
where
p' = fromJust $ isPrime p
primRootWrap2 :: Integer -> Word -> Integer -> Bool
primRootWrap2 p k g = case fromJust $ cyclicGroupFromFactors [(two, 1), (p', k)] of
Some cg -> case proofFromCyclicGroup cg of
Sub Dict -> isJust $ isPrimitiveRoot cg (fromInteger g)
where
two = fromJust $ isPrime 2
p' = fromJust $ isPrime p
cyclicWrap :: Integer -> Maybe (Some (CyclicGroup Integer))
cyclicWrap = cyclicGroupFromModulo
benchSuite :: Benchmark
benchSuite = bgroup "PrimRoot"
[ bgroup "groupFromModulo"
[ bench "3^20000" $ nf cyclicWrap (3^20000) -- prime to large power
, bench "10000000000000061" $ nf cyclicWrap (10^16 + 61) -- large prime
, bench "2*3^20000" $ nf cyclicWrap (2*3^20000) -- twice prime to large power
, bench "10000000000000046" $ nf cyclicWrap (10^16 + 46) -- twice large prime
, bench "224403121196654400" $ nf cyclicWrap 224403121196654400 -- highly composite
]
, bgroup "check prim roots"
[ bench "3^20000" $ nf (primRootWrap 3 20000) 2 -- prime to large power
, bench "10000000000000061" $ nf (primRootWrap (10^16 + 61) 1) 3 -- large prime
, bench "10000000000000061^2" $ nf (primRootWrap (10^16 + 61) 2) 3 -- large prime squared
, bench "2*3^20000" $ nf (primRootWrap2 3 20000) 5 -- twice prime to large power
, bench "10000000000000046" $ nf (primRootWrap2 (5*10^15 + 23) 1) 5 -- twice large prime
]
]
|
