原始根を求める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])