Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Testing Fermat's little theorem on Haskell
{-
Testing Fermat's little theorem on Haskell
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
\begin{align*}
a^p &\equiv a \pmod{p}
\end{align*}
-}
import Test.QuickCheck
import Debug.Trace
-- a prime number (beware of overflow)
prime :: Integer
prime = 13
-- left hand side
funcLHS :: Integer -> Integer
funcLHS x = rem (x^prime) prime
-- right hand side
funcRHS :: Integer -> Integer
funcRHS x = rem x prime
checkFermatsLittleTheorem :: Integer -> Bool
checkFermatsLittleTheorem a = (funcLHS x) == (funcRHS x)
where x = trace ("in=" ++ (show a) ++ ", funcLHS=" ++ (show $ funcLHS a) ++ ", funcRHS=" ++ (show $ funcRHS a)) a
main :: IO ()
main = quickCheck checkFermatsLittleTheorem
Owner

naoto-ogawa commented May 6, 2017

*Main> main
in=0, funcLHS=0, funcRHS=0
in=0, funcLHS=0, funcRHS=0
in=2, funcLHS=2, funcRHS=2
in=3, funcLHS=3, funcRHS=3
in=3, funcLHS=3, funcRHS=3
in=-5, funcLHS=-5, funcRHS=-5
in=0, funcLHS=0, funcRHS=0
in=-3, funcLHS=-3, funcRHS=-3
in=8, funcLHS=8, funcRHS=8
in=8, funcLHS=8, funcRHS=8
in=5, funcLHS=5, funcRHS=5
in=-7, funcLHS=-7, funcRHS=-7
in=-2, funcLHS=-2, funcRHS=-2
in=-12, funcLHS=-12, funcRHS=-12
in=4, funcLHS=4, funcRHS=4
in=9, funcLHS=9, funcRHS=9
in=-3, funcLHS=-3, funcRHS=-3
in=-13, funcLHS=0, funcRHS=0
in=0, funcLHS=0, funcRHS=0
in=16, funcLHS=3, funcRHS=3
in=-13, funcLHS=0, funcRHS=0
in=2, funcLHS=2, funcRHS=2
in=-2, funcLHS=-2, funcRHS=-2
in=-13, funcLHS=0, funcRHS=0
in=-14, funcLHS=-1, funcRHS=-1
in=23, funcLHS=10, funcRHS=10
in=24, funcLHS=11, funcRHS=11
in=1, funcLHS=1, funcRHS=1
in=-18, funcLHS=-5, funcRHS=-5
in=16, funcLHS=3, funcRHS=3
in=-21, funcLHS=-8, funcRHS=-8
in=17, funcLHS=4, funcRHS=4
in=32, funcLHS=6, funcRHS=6
in=12, funcLHS=12, funcRHS=12
in=-11, funcLHS=-11, funcRHS=-11
in=-16, funcLHS=-3, funcRHS=-3
in=-30, funcLHS=-4, funcRHS=-4
in=-12, funcLHS=-12, funcRHS=-12
in=7, funcLHS=7, funcRHS=7
in=-22, funcLHS=-9, funcRHS=-9
in=38, funcLHS=12, funcRHS=12
in=8, funcLHS=8, funcRHS=8
in=-13, funcLHS=0, funcRHS=0
in=-30, funcLHS=-4, funcRHS=-4
in=1, funcLHS=1, funcRHS=1
in=-24, funcLHS=-11, funcRHS=-11
in=-31, funcLHS=-5, funcRHS=-5
in=28, funcLHS=2, funcRHS=2
in=30, funcLHS=4, funcRHS=4
in=21, funcLHS=8, funcRHS=8
in=-20, funcLHS=-7, funcRHS=-7
in=21, funcLHS=8, funcRHS=8
in=-18, funcLHS=-5, funcRHS=-5
in=-7, funcLHS=-7, funcRHS=-7
in=40, funcLHS=1, funcRHS=1
in=-22, funcLHS=-9, funcRHS=-9
in=37, funcLHS=11, funcRHS=11
in=-4, funcLHS=-4, funcRHS=-4
in=57, funcLHS=5, funcRHS=5
in=-35, funcLHS=-9, funcRHS=-9
in=-39, funcLHS=0, funcRHS=0
in=27, funcLHS=1, funcRHS=1
in=43, funcLHS=4, funcRHS=4
in=24, funcLHS=11, funcRHS=11
in=-32, funcLHS=-6, funcRHS=-6
in=59, funcLHS=7, funcRHS=7
in=-51, funcLHS=-12, funcRHS=-12
in=-51, funcLHS=-12, funcRHS=-12
in=58, funcLHS=6, funcRHS=6
in=-25, funcLHS=-12, funcRHS=-12
in=-24, funcLHS=-11, funcRHS=-11
in=-18, funcLHS=-5, funcRHS=-5
in=-69, funcLHS=-4, funcRHS=-4
in=-47, funcLHS=-8, funcRHS=-8
in=33, funcLHS=7, funcRHS=7
in=8, funcLHS=8, funcRHS=8
in=-56, funcLHS=-4, funcRHS=-4
in=29, funcLHS=3, funcRHS=3
in=20, funcLHS=7, funcRHS=7
in=-30, funcLHS=-4, funcRHS=-4
in=30, funcLHS=4, funcRHS=4
in=68, funcLHS=3, funcRHS=3
in=-61, funcLHS=-9, funcRHS=-9
in=-39, funcLHS=0, funcRHS=0
in=-32, funcLHS=-6, funcRHS=-6
in=34, funcLHS=8, funcRHS=8
in=-13, funcLHS=0, funcRHS=0
in=54, funcLHS=2, funcRHS=2
in=-87, funcLHS=-9, funcRHS=-9
in=32, funcLHS=6, funcRHS=6
in=47, funcLHS=8, funcRHS=8
in=-62, funcLHS=-10, funcRHS=-10
in=23, funcLHS=10, funcRHS=10
in=49, funcLHS=10, funcRHS=10
in=-31, funcLHS=-5, funcRHS=-5
in=91, funcLHS=0, funcRHS=0
in=75, funcLHS=10, funcRHS=10
in=28, funcLHS=2, funcRHS=2
in=82, funcLHS=4, funcRHS=4
in=58, funcLHS=6, funcRHS=6
+++ OK, passed 100 tests.
*Main>

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment