    {-# LANGUAGE BangPatterns #-}

    -- |
    -- Module      : Crypto.Number.Prime
    -- License     : BSD-style
    -- Maintainer  : Vincent Hanquez <vincent@snarc.org>
    -- Stability   : experimental
    -- Portability : Good
    module Crypto.Number.Prime (
        generatePrime,
        generateSafePrime,
        isProbablyPrime,
        findPrimeFrom,
        findPrimeFromWith,
        primalityTestMillerRabin,
        primalityTestNaive,
        primalityTestFermat,
        isCoprime,
    ) where

    import Crypto.Error
    import Crypto.Number.Basic (gcde, sqrti)
    import Crypto.Number.Compat
    import Crypto.Number.Generate
    import Crypto.Number.ModArithmetic (expSafe)
    import Crypto.Random.Probabilistic
    import Crypto.Random.Types

    import Data.Bits

    -- | Returns if the number is probably prime.
    -- First a list of small primes are implicitely tested for divisibility,
    -- then a fermat primality test is used with arbitrary numbers and
    -- then the Miller Rabin algorithm is used with an accuracy of 30 recursions.
    isProbablyPrime :: Integer -> Bool
    isProbablyPrime :: Integer -> Bool
    isProbablyPrime !Integer
    n
        | (Integer -> Bool) -> [Integer] -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    any (\Integer
    p -> Integer
    p Integer -> Integer -> Bool
    `divides` Integer
    n) ((Integer -> Bool) -> [Integer] -> [Integer]
    forall a. (a -> Bool) -> [a] -> [a]
    filter (Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    < Integer
    n) [Integer]
    firstPrimes) = Bool
    False
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Integer
    2 Bool -> Bool -> Bool
    && Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Integer
    2903 = Bool
    True
        | Int -> Integer -> Integer -> Bool
    primalityTestFermat Int
    50 (Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2) Integer
    n =
            Int -> Integer -> Bool
    primalityTestMillerRabin Int
    30 Integer
    n
        | Bool
    otherwise = Bool
    False

    -- | Generate a prime number of the required bitsize (i.e. in the range
    -- [2^(b-1)+2^(b-2), 2^b)).
    --
    -- May throw a 'CryptoError_PrimeSizeInvalid' if the requested size is less
    -- than 5 bits, as the smallest prime meeting these conditions is 29.
    -- This function requires that the two highest bits are set, so that when
    -- multiplied with another prime to create a key, it is guaranteed to be of
    -- the proper size.
    generatePrime :: MonadRandom m => Int -> m Integer
    generatePrime :: forall (m :: * -> *). MonadRandom m => Int -> m Integer
    generatePrime Int
    bits = do
        if Int
    bits Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    5
            then
                CryptoFailable (m Integer) -> m Integer
    forall a. CryptoFailable a -> a
    throwCryptoError (CryptoFailable (m Integer) -> m Integer)
    -> CryptoFailable (m Integer) -> m Integer
    forall a b. (a -> b) -> a -> b
    $ CryptoError -> CryptoFailable (m Integer)
    forall a. CryptoError -> CryptoFailable a
    CryptoFailed (CryptoError -> CryptoFailable (m Integer))
    -> CryptoError -> CryptoFailable (m Integer)
    forall a b. (a -> b) -> a -> b
    $ CryptoError
    CryptoError_PrimeSizeInvalid
            else do
                sp <- Int -> Maybe GenTopPolicy -> Bool -> m Integer
    forall (m :: * -> *).
    MonadRandom m =>
    Int -> Maybe GenTopPolicy -> Bool -> m Integer
    generateParams Int
    bits (GenTopPolicy -> Maybe GenTopPolicy
    forall a. a -> Maybe a
    Just GenTopPolicy
    SetTwoHighest) Bool
    True
                let prime = Integer -> Integer
    findPrimeFrom Integer
    sp
                if prime < 1 `shiftL` bits
                    then
                        return $ prime
                    else generatePrime bits

    -- | Generate a prime number of the form 2p+1 where p is also prime.
    -- it is also knowed as a Sophie Germaine prime or safe prime.
    --
    -- The number of safe prime is significantly smaller to the number of prime,
    -- as such it shouldn't be used if this number is supposed to be kept safe.
    --
    -- May throw a 'CryptoError_PrimeSizeInvalid' if the requested size is less than
    -- 6 bits, as the smallest safe prime with the two highest bits set is 59.
    generateSafePrime :: MonadRandom m => Int -> m Integer
    generateSafePrime :: forall (m :: * -> *). MonadRandom m => Int -> m Integer
    generateSafePrime Int
    bits = do
        if Int
    bits Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    6
            then
                CryptoFailable (m Integer) -> m Integer
    forall a. CryptoFailable a -> a
    throwCryptoError (CryptoFailable (m Integer) -> m Integer)
    -> CryptoFailable (m Integer) -> m Integer
    forall a b. (a -> b) -> a -> b
    $ CryptoError -> CryptoFailable (m Integer)
    forall a. CryptoError -> CryptoFailable a
    CryptoFailed (CryptoError -> CryptoFailable (m Integer))
    -> CryptoError -> CryptoFailable (m Integer)
    forall a b. (a -> b) -> a -> b
    $ CryptoError
    CryptoError_PrimeSizeInvalid
            else do
                sp <- Int -> Maybe GenTopPolicy -> Bool -> m Integer
    forall (m :: * -> *).
    MonadRandom m =>
    Int -> Maybe GenTopPolicy -> Bool -> m Integer
    generateParams Int
    bits (GenTopPolicy -> Maybe GenTopPolicy
    forall a. a -> Maybe a
    Just GenTopPolicy
    SetTwoHighest) Bool
    True
                let p = (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith (\Integer
    i -> Integer -> Bool
    isProbablyPrime (Integer
    2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    i Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    1)) (Integer
    sp Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `div` Integer
    2)
                let val = Integer
    2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    p Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    1
                if val < 1 `shiftL` bits
                    then
                        return $ val
                    else generateSafePrime bits

    -- | Find a prime from a starting point where the property hold.
    findPrimeFromWith :: (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith :: (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith Integer -> Bool
    prop !Integer
    n
        | Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    n = (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith Integer -> Bool
    prop (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    1)
        | Bool
    otherwise =
            if Bool -> Bool
    not (Integer -> Bool
    isProbablyPrime Integer
    n)
                then (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith Integer -> Bool
    prop (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    2)
                else
                    if Integer -> Bool
    prop Integer
    n
                        then Integer
    n
                        else (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith Integer -> Bool
    prop (Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    2)

    -- | Find a prime from a starting point with no specific property.
    findPrimeFrom :: Integer -> Integer
    findPrimeFrom :: Integer -> Integer
    findPrimeFrom Integer
    n =
        case Integer -> GmpSupported Integer
    gmpNextPrime Integer
    n of
            GmpSupported Integer
    p -> Integer
    p
            GmpSupported Integer
    GmpUnsupported -> (Integer -> Bool) -> Integer -> Integer
    findPrimeFromWith (\Integer
    _ -> Bool
    True) Integer
    n

    -- | Miller Rabin algorithm return if the number is probably prime or composite.
    -- the tries parameter is the number of recursion, that determines the accuracy of the test.
    primalityTestMillerRabin :: Int -> Integer -> Bool
    primalityTestMillerRabin :: Int -> Integer -> Bool
    primalityTestMillerRabin Int
    tries !Integer
    n =
        case Int -> Integer -> GmpSupported Bool
    gmpTestPrimeMillerRabin Int
    tries Integer
    n of
            GmpSupported Bool
    b -> Bool
    b
            GmpSupported Bool
    GmpUnsupported -> MonadPseudoRandom ChaChaDRG Bool -> Bool
    forall a. MonadPseudoRandom ChaChaDRG a -> a
    probabilistic MonadPseudoRandom ChaChaDRG Bool
    run
      where
        run :: MonadPseudoRandom ChaChaDRG Bool
    run
            | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Integer
    3 = [Char] -> MonadPseudoRandom ChaChaDRG Bool
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Miller-Rabin requires tested value to be > 3"
            | Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    n = Bool -> MonadPseudoRandom ChaChaDRG Bool
    forall a. a -> MonadPseudoRandom ChaChaDRG a
    forall (m :: * -> *) a. Monad m => a -> m a
    return Bool
    False
            | Int
    tries Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = [Char] -> MonadPseudoRandom ChaChaDRG Bool
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Miller-Rabin tries need to be > 0"
            | Bool
    otherwise = [Integer] -> Bool
    loop ([Integer] -> Bool)
    -> MonadPseudoRandom ChaChaDRG [Integer]
    -> MonadPseudoRandom ChaChaDRG Bool
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> MonadPseudoRandom ChaChaDRG [Integer]
    forall {t} {m :: * -> *}.
    (Eq t, Num t, MonadRandom m) =>
    t -> m [Integer]
    generateTries Int
    tries

        !nm1 :: Integer
    nm1 = Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    1
        !nm2 :: Integer
    nm2 = Integer
    n Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    2

        (!Integer
    s, !Integer
    d) = (Integer -> Integer -> (Integer, Integer)
    factorise Integer
    0 Integer
    nm1)

        generateTries :: t -> m [Integer]
    generateTries t
    0 = [Integer] -> m [Integer]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return []
        generateTries t
    t = do
            v <- Integer -> Integer -> m Integer
    forall (m :: * -> *).
    MonadRandom m =>
    Integer -> Integer -> m Integer
    generateBetween Integer
    2 Integer
    nm2
            vs <- generateTries (t - 1)
            return (v : vs)

        -- factorise n-1 into the form 2^s*d
        factorise :: Integer -> Integer -> (Integer, Integer)
        factorise :: Integer -> Integer -> (Integer, Integer)
    factorise !Integer
    si !Integer
    vi
            | Integer
    vi Integer -> Int -> Bool
    forall a. Bits a => a -> Int -> Bool
    `testBit` Int
    0 = (Integer
    si, Integer
    vi)
            | Bool
    otherwise = Integer -> Integer -> (Integer, Integer)
    factorise (Integer
    si Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    1) (Integer
    vi Integer -> Int -> Integer
    forall a. Bits a => a -> Int -> a
    `shiftR` Int
    1) -- probably faster to not shift v continuously, but just once.
        expmod :: Integer -> Integer -> Integer -> Integer
    expmod = Integer -> Integer -> Integer -> Integer
    expSafe

        -- when iteration reach zero, we have a probable prime
        loop :: [Integer] -> Bool
    loop [] = Bool
    True
        loop (Integer
    w : [Integer]
    ws) =
            let x :: Integer
    x = Integer -> Integer -> Integer -> Integer
    expmod Integer
    w Integer
    d Integer
    n
             in if Integer
    x Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == (Integer
    1 :: Integer) Bool -> Bool -> Bool
    || Integer
    x Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    nm1
                    then [Integer] -> Bool
    loop [Integer]
    ws
                    else [Integer] -> Integer -> Integer -> Bool
    loop' [Integer]
    ws ((Integer
    x Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    x) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    n) Integer
    1

        -- loop from 1 to s-1. if we reach the end then it's composite
        loop' :: [Integer] -> Integer -> Integer -> Bool
    loop' [Integer]
    ws !Integer
    x2 !Integer
    r
            | Integer
    r Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    s = Bool
    False
            | Integer
    x2 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1 = Bool
    False
            | Integer
    x2 Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Integer
    nm1 = [Integer] -> Integer -> Integer -> Bool
    loop' [Integer]
    ws ((Integer
    x2 Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    * Integer
    x2) Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    n) (Integer
    r Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    1)
            | Bool
    otherwise = [Integer] -> Bool
    loop [Integer]
    ws

    {-
        n < z -> witness to test
                  1373653 [2,3]
                  9080191 [31,73]
                  4759123141 [2,7,61]
                  2152302898747 [2,3,5,7,11]
                  3474749660383 [2,3,5,7,11,13]
                  341550071728321 [2,3,5,7,11,13,17]
    -}

    -- | Probabilitic Test using Fermat primility test.
    -- Beware of Carmichael numbers that are Fermat liars, i.e. this test
    -- is useless for them. always combines with some other test.
    primalityTestFermat
        :: Int
        -- ^ number of iterations of the algorithm
        -> Integer
        -- ^ starting a
        -> Integer
        -- ^ number to test for primality
        -> Bool
    primalityTestFermat :: Int -> Integer -> Integer -> Bool
    primalityTestFermat Int
    n Integer
    a Integer
    p = [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and ([Bool] -> Bool) -> [Bool] -> Bool
    forall a b. (a -> b) -> a -> b
    $ (Integer -> Bool) -> [Integer] -> [Bool]
    forall a b. (a -> b) -> [a] -> [b]
    map Integer -> Bool
    expTest [Integer
    a .. (Integer
    a Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Int -> Integer
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    n)]
      where
        !pm1 :: Integer
    pm1 = Integer
    p Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    - Integer
    1
        expTest :: Integer -> Bool
    expTest Integer
    i = Integer -> Integer -> Integer -> Integer
    expSafe Integer
    i Integer
    pm1 Integer
    p Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1

    -- | Test naively is integer is prime.
    -- while naive, we skip even number and stop iteration at i > sqrt(n)
    primalityTestNaive :: Integer -> Bool
    primalityTestNaive :: Integer -> Bool
    primalityTestNaive Integer
    n
        | Integer
    n Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Integer
    1 = Bool
    False
        | Integer
    n Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    2 = Bool
    True
        | Integer -> Bool
    forall a. Integral a => a -> Bool
    even Integer
    n = Bool
    False
        | Bool
    otherwise = Integer -> Bool
    search Integer
    3
      where
        !ubound :: Integer
    ubound = (Integer, Integer) -> Integer
    forall a b. (a, b) -> b
    snd ((Integer, Integer) -> Integer) -> (Integer, Integer) -> Integer
    forall a b. (a -> b) -> a -> b
    $ Integer -> (Integer, Integer)
    sqrti Integer
    n
        search :: Integer -> Bool
    search !Integer
    i
            | Integer
    i Integer -> Integer -> Bool
    forall a. Ord a => a -> a -> Bool
    > Integer
    ubound = Bool
    True
            | Integer
    i Integer -> Integer -> Bool
    `divides` Integer
    n = Bool
    False
            | Bool
    otherwise = Integer -> Bool
    search (Integer
    i Integer -> Integer -> Integer
    forall a. Num a => a -> a -> a
    + Integer
    2)

    -- | Test is two integer are coprime to each other
    isCoprime :: Integer -> Integer -> Bool
    isCoprime :: Integer -> Integer -> Bool
    isCoprime Integer
    m Integer
    n = case Integer -> Integer -> (Integer, Integer, Integer)
    gcde Integer
    m Integer
    n of (Integer
    _, Integer
    _, Integer
    d) -> Integer
    d Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    1

    -- | List of the first primes till 2903.
    firstPrimes :: [Integer]
    firstPrimes :: [Integer]
    firstPrimes =
        [ Integer
    2
        , Integer
    3
        , Integer
    5
        , Integer
    7
        , Integer
    11
        , Integer
    13
        , Integer
    17
        , Integer
    19
        , Integer
    23
        , Integer
    29
        , Integer
    31
        , Integer
    37
        , Integer
    41
        , Integer
    43
        , Integer
    47
        , Integer
    53
        , Integer
    59
        , Integer
    61
        , Integer
    67
        , Integer
    71
        , Integer
    73
        , Integer
    79
        , Integer
    83
        , Integer
    89
        , Integer
    97
        , Integer
    101
        , Integer
    103
        , Integer
    107
        , Integer
    109
        , Integer
    113
        , Integer
    127
        , Integer
    131
        , Integer
    137
        , Integer
    139
        , Integer
    149
        , Integer
    151
        , Integer
    157
        , Integer
    163
        , Integer
    167
        , Integer
    173
        , Integer
    179
        , Integer
    181
        , Integer
    191
        , Integer
    193
        , Integer
    197
        , Integer
    199
        , Integer
    211
        , Integer
    223
        , Integer
    227
        , Integer
    229
        , Integer
    233
        , Integer
    239
        , Integer
    241
        , Integer
    251
        , Integer
    257
        , Integer
    263
        , Integer
    269
        , Integer
    271
        , Integer
    277
        , Integer
    281
        , Integer
    283
        , Integer
    293
        , Integer
    307
        , Integer
    311
        , Integer
    313
        , Integer
    317
        , Integer
    331
        , Integer
    337
        , Integer
    347
        , Integer
    349
        , Integer
    353
        , Integer
    359
        , Integer
    367
        , Integer
    373
        , Integer
    379
        , Integer
    383
        , Integer
    389
        , Integer
    397
        , Integer
    401
        , Integer
    409
        , Integer
    419
        , Integer
    421
        , Integer
    431
        , Integer
    433
        , Integer
    439
        , Integer
    443
        , Integer
    449
        , Integer
    457
        , Integer
    461
        , Integer
    463
        , Integer
    467
        , Integer
    479
        , Integer
    487
        , Integer
    491
        , Integer
    499
        , Integer
    503
        , Integer
    509
        , Integer
    521
        , Integer
    523
        , Integer
    541
        , Integer
    547
        , Integer
    557
        , Integer
    563
        , Integer
    569
        , Integer
    571
        , Integer
    577
        , Integer
    587
        , Integer
    593
        , Integer
    599
        , Integer
    601
        , Integer
    607
        , Integer
    613
        , Integer
    617
        , Integer
    619
        , Integer
    631
        , Integer
    641
        , Integer
    643
        , Integer
    647
        , Integer
    653
        , Integer
    659
        , Integer
    661
        , Integer
    673
        , Integer
    677
        , Integer
    683
        , Integer
    691
        , Integer
    701
        , Integer
    709
        , Integer
    719
        , Integer
    727
        , Integer
    733
        , Integer
    739
        , Integer
    743
        , Integer
    751
        , Integer
    757
        , Integer
    761
        , Integer
    769
        , Integer
    773
        , Integer
    787
        , Integer
    797
        , Integer
    809
        , Integer
    811
        , Integer
    821
        , Integer
    823
        , Integer
    827
        , Integer
    829
        , Integer
    839
        , Integer
    853
        , Integer
    857
        , Integer
    859
        , Integer
    863
        , Integer
    877
        , Integer
    881
        , Integer
    883
        , Integer
    887
        , Integer
    907
        , Integer
    911
        , Integer
    919
        , Integer
    929
        , Integer
    937
        , Integer
    941
        , Integer
    947
        , Integer
    953
        , Integer
    967
        , Integer
    971
        , Integer
    977
        , Integer
    983
        , Integer
    991
        , Integer
    997
        , Integer
    1009
        , Integer
    1013
        , Integer
    1019
        , Integer
    1021
        , Integer
    1031
        , Integer
    1033
        , Integer
    1039
        , Integer
    1049
        , Integer
    1051
        , Integer
    1061
        , Integer
    1063
        , Integer
    1069
        , Integer
    1087
        , Integer
    1091
        , Integer
    1093
        , Integer
    1097
        , Integer
    1103
        , Integer
    1109
        , Integer
    1117
        , Integer
    1123
        , Integer
    1129
        , Integer
    1151
        , Integer
    1153
        , Integer
    1163
        , Integer
    1171
        , Integer
    1181
        , Integer
    1187
        , Integer
    1193
        , Integer
    1201
        , Integer
    1213
        , Integer
    1217
        , Integer
    1223
        , Integer
    1229
        , Integer
    1231
        , Integer
    1237
        , Integer
    1249
        , Integer
    1259
        , Integer
    1277
        , Integer
    1279
        , Integer
    1283
        , Integer
    1289
        , Integer
    1291
        , Integer
    1297
        , Integer
    1301
        , Integer
    1303
        , Integer
    1307
        , Integer
    1319
        , Integer
    1321
        , Integer
    1327
        , Integer
    1361
        , Integer
    1367
        , Integer
    1373
        , Integer
    1381
        , Integer
    1399
        , Integer
    1409
        , Integer
    1423
        , Integer
    1427
        , Integer
    1429
        , Integer
    1433
        , Integer
    1439
        , Integer
    1447
        , Integer
    1451
        , Integer
    1453
        , Integer
    1459
        , Integer
    1471
        , Integer
    1481
        , Integer
    1483
        , Integer
    1487
        , Integer
    1489
        , Integer
    1493
        , Integer
    1499
        , Integer
    1511
        , Integer
    1523
        , Integer
    1531
        , Integer
    1543
        , Integer
    1549
        , Integer
    1553
        , Integer
    1559
        , Integer
    1567
        , Integer
    1571
        , Integer
    1579
        , Integer
    1583
        , Integer
    1597
        , Integer
    1601
        , Integer
    1607
        , Integer
    1609
        , Integer
    1613
        , Integer
    1619
        , Integer
    1621
        , Integer
    1627
        , Integer
    1637
        , Integer
    1657
        , Integer
    1663
        , Integer
    1667
        , Integer
    1669
        , Integer
    1693
        , Integer
    1697
        , Integer
    1699
        , Integer
    1709
        , Integer
    1721
        , Integer
    1723
        , Integer
    1733
        , Integer
    1741
        , Integer
    1747
        , Integer
    1753
        , Integer
    1759
        , Integer
    1777
        , Integer
    1783
        , Integer
    1787
        , Integer
    1789
        , Integer
    1801
        , Integer
    1811
        , Integer
    1823
        , Integer
    1831
        , Integer
    1847
        , Integer
    1861
        , Integer
    1867
        , Integer
    1871
        , Integer
    1873
        , Integer
    1877
        , Integer
    1879
        , Integer
    1889
        , Integer
    1901
        , Integer
    1907
        , Integer
    1913
        , Integer
    1931
        , Integer
    1933
        , Integer
    1949
        , Integer
    1951
        , Integer
    1973
        , Integer
    1979
        , Integer
    1987
        , Integer
    1993
        , Integer
    1997
        , Integer
    1999
        , Integer
    2003
        , Integer
    2011
        , Integer
    2017
        , Integer
    2027
        , Integer
    2029
        , Integer
    2039
        , Integer
    2053
        , Integer
    2063
        , Integer
    2069
        , Integer
    2081
        , Integer
    2083
        , Integer
    2087
        , Integer
    2089
        , Integer
    2099
        , Integer
    2111
        , Integer
    2113
        , Integer
    2129
        , Integer
    2131
        , Integer
    2137
        , Integer
    2141
        , Integer
    2143
        , Integer
    2153
        , Integer
    2161
        , Integer
    2179
        , Integer
    2203
        , Integer
    2207
        , Integer
    2213
        , Integer
    2221
        , Integer
    2237
        , Integer
    2239
        , Integer
    2243
        , Integer
    2251
        , Integer
    2267
        , Integer
    2269
        , Integer
    2273
        , Integer
    2281
        , Integer
    2287
        , Integer
    2293
        , Integer
    2297
        , Integer
    2309
        , Integer
    2311
        , Integer
    2333
        , Integer
    2339
        , Integer
    2341
        , Integer
    2347
        , Integer
    2351
        , Integer
    2357
        , Integer
    2371
        , Integer
    2377
        , Integer
    2381
        , Integer
    2383
        , Integer
    2389
        , Integer
    2393
        , Integer
    2399
        , Integer
    2411
        , Integer
    2417
        , Integer
    2423
        , Integer
    2437
        , Integer
    2441
        , Integer
    2447
        , Integer
    2459
        , Integer
    2467
        , Integer
    2473
        , Integer
    2477
        , Integer
    2503
        , Integer
    2521
        , Integer
    2531
        , Integer
    2539
        , Integer
    2543
        , Integer
    2549
        , Integer
    2551
        , Integer
    2557
        , Integer
    2579
        , Integer
    2591
        , Integer
    2593
        , Integer
    2609
        , Integer
    2617
        , Integer
    2621
        , Integer
    2633
        , Integer
    2647
        , Integer
    2657
        , Integer
    2659
        , Integer
    2663
        , Integer
    2671
        , Integer
    2677
        , Integer
    2683
        , Integer
    2687
        , Integer
    2689
        , Integer
    2693
        , Integer
    2699
        , Integer
    2707
        , Integer
    2711
        , Integer
    2713
        , Integer
    2719
        , Integer
    2729
        , Integer
    2731
        , Integer
    2741
        , Integer
    2749
        , Integer
    2753
        , Integer
    2767
        , Integer
    2777
        , Integer
    2789
        , Integer
    2791
        , Integer
    2797
        , Integer
    2801
        , Integer
    2803
        , Integer
    2819
        , Integer
    2833
        , Integer
    2837
        , Integer
    2843
        , Integer
    2851
        , Integer
    2857
        , Integer
    2861
        , Integer
    2879
        , Integer
    2887
        , Integer
    2897
        , Integer
    2903
        ]

    {-# INLINE divides #-}
    divides :: Integer -> Integer -> Bool
    divides :: Integer -> Integer -> Bool
    divides Integer
    i Integer
    n = Integer
    n Integer -> Integer -> Integer
    forall a. Integral a => a -> a -> a
    `mod` Integer
    i Integer -> Integer -> Bool
    forall a. Eq a => a -> a -> Bool
    == Integer
    0