原始根を求めるHaskellプログラムの例
奇素数を法とする原始根を求める Haskell プログラムの例。
プログラム例
main = printElems 14 $ listPrimitiveRoots $ sieve $ filter odd [3..]
-- リストの各要素を表示
printElems :: Show a => Int -> [a] -> IO()
printElems n xs = mapM_ print $ take n $ xs
-- 素数 p と、p を法とする原始根との組
listPrimitiveRoots :: [Integer] -> [(Integer, [Integer])]
listPrimitiveRoots primes = [ (p, primitiveRoots p) | p <- primes ]
-- 与えられた素数を法とする原始根を求める
primitiveRoots :: Integer -> [Integer]
primitiveRoots p = filter (isPrimitive 1 0) [2 .. p-1]
where
-- x^i mod p /= 1 (i=1,...,p-2) かどうか
isPrimitive :: Integer -> Integer -> Integer -> Bool
isPrimitive a i x
| i >= p - 1 = True
| i == 0 = isPrimitive x 1 x
| otherwise = a `mod` p /= 1 &&
isPrimitive (a * x) (i + 1) x
-- 素数リスト (エラトステネスの篩)
sieve :: [Integer] -> [Integer]
sieve (p : xs) = p : sieve [ n | n <- xs, n `mod` p /= 0 ]
実行結果：
(3,[2]) (5,[2,3]) (7,[3,5]) (11,[2,6,7,8]) (13,[2,6,7,11]) (17,[3,5,6,7,10,11,12,14]) (19,[2,3,10,13,14,15]) (23,[5,7,10,11,14,15,17,19,20,21]) (29,[2,3,8,10,11,14,15,18,19,21,26,27]) (31,[3,11,12,13,17,21,22,24]) (37,[2,5,13,15,17,18,19,20,22,24,32,35]) (41,[6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35]) (43,[3,5,12,18,19,20,26,28,29,30,33,34]) (47,[5,10,11,13,15,19,20,22,23,26,29,30,31,33,35,38,39,40,41,43,44,45])
