-- |
-- Module:      Math.NumberTheory.Primes.Testing.Certified
-- Copyright:   (c) 2011 Daniel Fischer
-- Licence:     MIT
-- Maintainer:  Daniel Fischer <daniel.is.fischer@googlemail.com>
--
-- Deterministic primality testing.

{-# LANGUAGE MagicHash           #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UnboxedTuples       #-}
{-# LANGUAGE ViewPatterns        #-}
{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}

module Math.NumberTheory.Primes.Testing.Certified
  ( isCertifiedPrime
  ) where

import Data.List (foldl')
import Data.Bits ((.&.))
import Data.Mod
import Data.Proxy
import GHC.Num.Integer
import GHC.TypeNats (SomeNat(..), someNatVal)

import Math.NumberTheory.Roots (integerSquareRoot)
import Math.NumberTheory.Primes (unPrime)
import Math.NumberTheory.Primes.Factorisation.TrialDivision (trialDivisionPrimeTo, trialDivisionTo, trialDivisionWith)
import Math.NumberTheory.Primes.Factorisation.Montgomery (montgomeryFactorisation, smallFactors, findParms)
import Math.NumberTheory.Primes.Testing.Probabilistic (bailliePSW, isPrime, isStrongFermatPP, lucasTest)
import Math.NumberTheory.Primes.Sieve.Eratosthenes (primeList, primeSieve)
import Math.NumberTheory.Utils (splitOff)

-- | @'isCertifiedPrime' n@ tests primality of @n@, first trial division
--   by small primes is performed, then a Baillie PSW test and finally a
--   prime certificate is constructed and verified, provided no step before
--   found @n@ to be composite. Constructing prime certificates can take
--   a /very/ long time, so use this with care.
isCertifiedPrime :: Integer -> Bool
isCertifiedPrime :: Integer -> Bool
isCertifiedPrime Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
0     = Integer -> Bool
isCertifiedPrime (-Integer
n)
    | Bool
otherwise = Integer -> Bool
isPrime Integer
n Bool -> Bool -> Bool
&& ((Integer
n forall a. Ord a => a -> a -> Bool
< Integer
bpbd) Bool -> Bool -> Bool
|| PrimalityProof -> Bool
checkPrimalityProof (Integer -> PrimalityProof
certifyBPSW Integer
n))
      where
        bpbd :: Integer
bpbd = Integer
100000000000000000
-- Although it is known that there are no Baillie PSW pseudoprimes below 2^64,
-- use the verified bound 10^17, I don't know whether Gilchrist's result has been
-- verified yet.

-- | A proof of primality of a positive number. The type is
--   abstract to ensure the validity of proofs.
data PrimalityProof
    = Pocklington { PrimalityProof -> Integer
cprime :: !Integer          -- ^ The number whose primality is proved.
                  , PrimalityProof -> Integer
_factorisedPart, PrimalityProof -> Integer
_cofactor :: !Integer
                  , PrimalityProof -> [(Integer, Word, Integer, PrimalityProof)]
_knownFactors :: ![(Integer, Word, Integer, PrimalityProof)]
                  }
    | TrialDivision { cprime :: !Integer        -- ^ The number whose primality is proved.
                    , PrimalityProof -> Integer
_tdLimit :: !Integer }
    | Trivial { cprime :: !Integer              -- ^ The number whose primality is proved.
              }
      deriving Int -> PrimalityProof -> ShowS
[PrimalityProof] -> ShowS
PrimalityProof -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [PrimalityProof] -> ShowS
$cshowList :: [PrimalityProof] -> ShowS
show :: PrimalityProof -> String
$cshow :: PrimalityProof -> String
showsPrec :: Int -> PrimalityProof -> ShowS
$cshowsPrec :: Int -> PrimalityProof -> ShowS
Show

-- | Check the validity of a 'PrimalityProof'. Since it should be
--   impossible to create invalid proofs by the public interface, this
--   should never return 'False'.
checkPrimalityProof :: PrimalityProof -> Bool
checkPrimalityProof :: PrimalityProof -> Bool
checkPrimalityProof (Trivial Integer
n) = Integer -> Bool
isTrivialPrime Integer
n
checkPrimalityProof (TrialDivision Integer
p Integer
b) = Integer
p forall a. Ord a => a -> a -> Bool
<= Integer
bforall a. Num a => a -> a -> a
*Integer
b Bool -> Bool -> Bool
&& Integer -> Integer -> Bool
trialDivisionPrimeTo Integer
b Integer
p
checkPrimalityProof (Pocklington Integer
p Integer
a Integer
b [(Integer, Word, Integer, PrimalityProof)]
fcts) = Integer
b forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& Integer
a forall a. Ord a => a -> a -> Bool
> Integer
b Bool -> Bool -> Bool
&& Integer
aforall a. Num a => a -> a -> a
*Integer
b forall a. Eq a => a -> a -> Bool
== Integer
pm1 Bool -> Bool -> Bool
&& Integer
a forall a. Eq a => a -> a -> Bool
== forall {b} {a} {c} {d}. (Integral b, Num a) => [(a, b, c, d)] -> a
ppProd [(Integer, Word, Integer, PrimalityProof)]
fcts Bool -> Bool -> Bool
&& forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all forall {b}. (Integer, b, Integer, PrimalityProof) -> Bool
verify [(Integer, Word, Integer, PrimalityProof)]
fcts
  where
    pm1 :: Integer
pm1 = Integer
pforall a. Num a => a -> a -> a
-Integer
1
    ppProd :: [(a, b, c, d)] -> a
ppProd [(a, b, c, d)]
pps = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [a
pfforall a b. (Num a, Integral b) => a -> b -> a
^b
e | (a
pf,b
e,c
_,d
_) <- [(a, b, c, d)]
pps]
    verify :: (Integer, b, Integer, PrimalityProof) -> Bool
verify (Integer
pf,b
_,Integer
base,PrimalityProof
proof) = Integer
pf forall a. Eq a => a -> a -> Bool
== PrimalityProof -> Integer
cprime PrimalityProof
proof Bool -> Bool -> Bool
&& Integer -> Integer -> Bool
crit Integer
pf Integer
base Bool -> Bool -> Bool
&& PrimalityProof -> Bool
checkPrimalityProof PrimalityProof
proof
    crit :: Integer -> Integer -> Bool
crit Integer
pf Integer
base = forall a. Integral a => a -> a -> a
gcd Integer
p (forall a. Integral a => a -> Integer
toInteger Natural
xforall a. Num a => a -> a -> a
-Integer
1) forall a. Eq a => a -> a -> Bool
== Integer
1 Bool -> Bool -> Bool
&& Natural
y forall a. Eq a => a -> a -> Bool
== Natural
1
      where
        (# Natural
x | #) = Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# Integer
base (Integer
pm1 forall a. Integral a => a -> a -> a
`quot` Integer
pf) (forall a. Num a => Integer -> a
fromInteger Integer
p)
        (# Natural
y | #) = Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# (forall a. Integral a => a -> Integer
toInteger Natural
x) Integer
pf (forall a. Num a => Integer -> a
fromInteger Integer
p)

-- | @'isTrivialPrime'@ checks whether its argument is a trivially
--   known prime.
isTrivialPrime :: Integer -> Bool
isTrivialPrime :: Integer -> Bool
isTrivialPrime Integer
n = Integer
n forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
`elem` [Integer]
trivialPrimes

-- | List of trivially known primes.
trivialPrimes :: [Integer]
trivialPrimes :: [Integer]
trivialPrimes = [Integer
2,Integer
3,Integer
5,Integer
7,Integer
11,Integer
13,Integer
17,Integer
19,Integer
23,Integer
29]

-- | Certify a small number. This is not exposed and should only
--   be used where correct. It is always checked after use, though,
--   so it shouldn't be able to lie.
smallCert :: Integer -> PrimalityProof
smallCert :: Integer -> PrimalityProof
smallCert Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
30    = Integer -> PrimalityProof
Trivial Integer
n
    | Bool
otherwise = Integer -> Integer -> PrimalityProof
TrialDivision Integer
n (forall a. Integral a => a -> a
integerSquareRoot Integer
n forall a. Num a => a -> a -> a
+ Integer
1)

-- | @'certify' n@ constructs, for @n > 1@, a proof of either
--   primality or compositeness of @n@. This may take a very long
--   time if the number has no small(ish) prime divisors
certify :: Integer -> Maybe PrimalityProof
certify :: Integer -> Maybe PrimalityProof
certify Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
2     = forall a. HasCallStack => String -> a
error String
"Only numbers larger than 1 can be certified"
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
31    = case [Integer] -> Integer -> [(Integer, Word)]
trialDivisionWith [Integer]
trivialPrimes Integer
n of
                    ((Integer
p,Word
_):[(Integer, Word)]
_) | Integer
p forall a. Ord a => a -> a -> Bool
< Integer
n     -> forall a. Maybe a
Nothing
                              | Bool
otherwise -> forall a. a -> Maybe a
Just (Integer -> PrimalityProof
Trivial Integer
n)
                    [(Integer, Word)]
_ -> forall a. HasCallStack => String -> a
error String
"Impossible"
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
billi = let r2 :: Integer
r2 = forall a. Integral a => a -> a
integerSquareRoot Integer
n forall a. Num a => a -> a -> a
+ Integer
2 in
                  case Integer -> Integer -> [(Integer, Word)]
trialDivisionTo Integer
r2 Integer
n of
                    ((Integer
p,Word
_):[(Integer, Word)]
_) | Integer
p forall a. Ord a => a -> a -> Bool
< Integer
n       -> forall a. Maybe a
Nothing
                              | Bool
otherwise   -> forall a. a -> Maybe a
Just (Integer -> Integer -> PrimalityProof
TrialDivision Integer
n Integer
r2)
                    [(Integer, Word)]
_ -> forall a. HasCallStack => String -> a
error String
"Impossible"
    | Bool
otherwise = case Natural -> ([(Natural, Word)], Maybe Natural)
smallFactors (forall a. Num a => Integer -> a
fromInteger (forall a. Num a => a -> a
abs Integer
n)) of
                    ([], Just Natural
_) | Bool -> Bool
not (Integer -> Integer -> Bool
isStrongFermatPP Integer
n Integer
2) -> forall a. Maybe a
Nothing
                                 | Bool -> Bool
not (Integer -> Bool
lucasTest Integer
n) -> forall a. Maybe a
Nothing
                                 | Bool
otherwise -> forall a. a -> Maybe a
Just (Integer -> PrimalityProof
certifyBPSW Integer
n)       -- if it isn't we error and ask for a report.
                    ((forall a. Integral a => a -> Integer
toInteger -> Integer
p,Word
_):[(Natural, Word)]
_, Maybe Natural
_)
                      | Integer
p forall a. Eq a => a -> a -> Bool
== Integer
n -> forall a. a -> Maybe a
Just (Integer -> Integer -> PrimalityProof
TrialDivision Integer
n (forall a. Ord a => a -> a -> a
min Integer
100000 Integer
n))
                      | Bool
otherwise -> forall a. Maybe a
Nothing
                    ([(Natural, Word)], Maybe Natural)
_ -> forall a. HasCallStack => String -> a
error (String
"***Error factorising " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
n forall a. [a] -> [a] -> [a]
++ String
"! Please report this to maintainer of arithmoi.")
      where
        billi :: Integer
billi = Integer
1000000000000

-- | Certify a number known to be not too small, having no small prime divisors and having
--   passed the Baillie PSW test. So we assume it's prime, erroring if not.
--   Since it's presumably a large number, we don't bother with trial division and
--   construct a Pocklington certificate.
certifyBPSW :: Integer -> PrimalityProof
certifyBPSW :: Integer -> PrimalityProof
certifyBPSW Integer
n = Integer
-> Integer
-> Integer
-> [(Integer, Word, Integer, PrimalityProof)]
-> PrimalityProof
Pocklington Integer
n Integer
a Integer
b [(Integer, Word, Integer, PrimalityProof)]
kfcts
  where
    nm1 :: Integer
nm1 = Integer
nforall a. Num a => a -> a -> a
-Integer
1
    h :: Integer
h = Integer
nm1 forall a. Integral a => a -> a -> a
`quot` Integer
2
    m3 :: Bool
m3 = forall a. Num a => Integer -> a
fromInteger Integer
n forall a. Bits a => a -> a -> a
.&. (Int
3 :: Int) forall a. Eq a => a -> a -> Bool
== Int
3
    (Integer
a,[(Integer, Word, Bool)]
pp,Integer
b) = Integer -> (Integer, [(Integer, Word, Bool)], Integer)
findDecomposition Integer
nm1
    kfcts0 :: [(Integer, Word, Integer, PrimalityProof)]
kfcts0 = forall a b. (a -> b) -> [a] -> [b]
map forall {b}.
(Integer, b, Bool) -> (Integer, b, Integer, PrimalityProof)
check [(Integer, Word, Bool)]
pp
    kfcts :: [(Integer, Word, Integer, PrimalityProof)]
kfcts = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall {a} {b} {c} {a}.
[(a, b, c, a)] -> (a, b, c, a) -> [(a, b, c, a)]
force [] [(Integer, Word, Integer, PrimalityProof)]
kfcts0
    force :: [(a, b, c, a)] -> (a, b, c, a) -> [(a, b, c, a)]
force [(a, b, c, a)]
xs t :: (a, b, c, a)
t@(a
_,b
_,c
_,a
prf) = a
prf seq :: forall a b. a -> b -> b
`seq` ((a, b, c, a)
tforall a. a -> [a] -> [a]
:[(a, b, c, a)]
xs)
    check :: (Integer, b, Bool) -> (Integer, b, Integer, PrimalityProof)
check (Integer
p,b
e,Bool
byTD) = Integer -> (Integer, b, Integer, PrimalityProof)
go Integer
2
      where
        go :: Integer -> (Integer, b, Integer, PrimalityProof)
go Integer
bs
            | Integer
bs forall a. Ord a => a -> a -> Bool
> Integer
h    = forall a. HasCallStack => String -> a
error (Integer -> String
bpswMessage Integer
n)
            | Natural
x forall a. Eq a => a -> a -> Bool
== Natural
1    = if Bool
m3 Bool -> Bool -> Bool
&& (Integer
p forall a. Eq a => a -> a -> Bool
== Integer
2) then (Integer
p,b
e,Integer
nforall a. Num a => a -> a -> a
-Integer
bs,Integer -> PrimalityProof
Trivial Integer
2) else Integer -> (Integer, b, Integer, PrimalityProof)
go (Integer
bsforall a. Num a => a -> a -> a
+Integer
1)
            | Integer
g forall a. Eq a => a -> a -> Bool
/= Integer
1    = forall a. HasCallStack => String -> a
error (Integer -> String
bpswMessage Integer
n forall a. [a] -> [a] -> [a]
++ Integer -> String
found Integer
g)
            | Natural
y forall a. Eq a => a -> a -> Bool
/= Natural
1    = forall a. HasCallStack => String -> a
error (Integer -> String
bpswMessage Integer
n forall a. [a] -> [a] -> [a]
++ Integer -> String
fermat Integer
bs)
            | Bool
byTD      = (Integer
p,b
e,Integer
bs, Integer -> PrimalityProof
smallCert Integer
p)
            | Bool
otherwise = case Integer -> Maybe PrimalityProof
certify Integer
p of
                            Maybe PrimalityProof
Nothing -> forall a. HasCallStack => String -> a
error (String
"***Error in factorisation code: " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
p
                                                        forall a. [a] -> [a] -> [a]
++ String
" was supposed to be prime but isn't.\n"
                                                        forall a. [a] -> [a] -> [a]
++ String
"Please report this to the maintainer.\n\n")
                            Just PrimalityProof
ppr ->(Integer
p,b
e,Integer
bs,PrimalityProof
ppr)
              where
                q :: Integer
q = Integer
nm1 forall a. Integral a => a -> a -> a
`quot` Integer
p
                (# Natural
x | #) = Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# Integer
bs Integer
q (forall a. Num a => Integer -> a
fromInteger Integer
n)
                (# Natural
y | #) = Integer -> Integer -> Natural -> (# Natural | () #)
integerPowMod# (forall a. Integral a => a -> Integer
toInteger Natural
x) Integer
p (forall a. Num a => Integer -> a
fromInteger Integer
n)
                g :: Integer
g = forall a. Integral a => a -> a -> a
gcd Integer
n (forall a. Integral a => a -> Integer
toInteger Natural
xforall a. Num a => a -> a -> a
-Integer
1)

-- | Find a decomposition of p-1 for the pocklington certificate.
--   Usually bloody slow if p-1 has two (or more) /large/ prime divisors.
findDecomposition :: Integer -> (Integer, [(Integer, Word, Bool)], Integer)
findDecomposition :: Integer -> (Integer, [(Integer, Word, Bool)], Integer)
findDecomposition Integer
n = Integer
-> Integer
-> [(Integer, Word, Bool)]
-> [Integer]
-> (Integer, [(Integer, Word, Bool)], Integer)
go Integer
1 Integer
n [] [Integer]
prms
  where
    sr :: Integer
sr = forall a. Integral a => a -> a
integerSquareRoot Integer
n
    pbd :: Integer
pbd = forall a. Ord a => a -> a -> a
min Integer
1000000 (Integer
srforall a. Num a => a -> a -> a
+Integer
20)
    prms :: [Integer]
prms = forall a b. (a -> b) -> [a] -> [b]
map forall a. Prime a -> a
unPrime forall a b. (a -> b) -> a -> b
$ forall a. Integral a => PrimeSieve -> [Prime a]
primeList (Integer -> PrimeSieve
primeSieve Integer
pbd)
    go :: Integer
-> Integer
-> [(Integer, Word, Bool)]
-> [Integer]
-> (Integer, [(Integer, Word, Bool)], Integer)
go Integer
a Integer
b [(Integer, Word, Bool)]
afs (Integer
p:[Integer]
ps)
        | Integer
a forall a. Ord a => a -> a -> Bool
> Integer
b     = (Integer
a,[(Integer, Word, Bool)]
afs,Integer
b)
        | Bool
otherwise = case forall a. (Eq a, GcdDomain a) => a -> a -> (Word, a)
splitOff Integer
p Integer
b of
                        (Word
0,Integer
_) -> Integer
-> Integer
-> [(Integer, Word, Bool)]
-> [Integer]
-> (Integer, [(Integer, Word, Bool)], Integer)
go Integer
a Integer
b [(Integer, Word, Bool)]
afs [Integer]
ps
                        (Word
e,Integer
q) -> Integer
-> Integer
-> [(Integer, Word, Bool)]
-> [Integer]
-> (Integer, [(Integer, Word, Bool)], Integer)
go (Integer
aforall a. Num a => a -> a -> a
*Integer
pforall a b. (Num a, Integral b) => a -> b -> a
^Word
e) Integer
q ((Integer
p,Word
e,Bool
True)forall a. a -> [a] -> [a]
:[(Integer, Word, Bool)]
afs) [Integer]
ps
    go Integer
a Integer
b [(Integer, Word, Bool)]
afs []
        | Integer
a forall a. Ord a => a -> a -> Bool
> Integer
b     = (Integer
a,[(Integer, Word, Bool)]
afs,Integer
b)
        | Integer -> Bool
bailliePSW Integer
b  = (Integer
b,[(Integer
b,Word
1,Bool
False)],Integer
a)   -- Until a Baillie PSW pseudoprime is found, I'm going with this
        | Word
e forall a. Eq a => a -> a -> Bool
== Word
0    = forall a. HasCallStack => String -> a
error (String
"Error in factorisation, " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
p forall a. [a] -> [a] -> [a]
++ String
" was found as a factor of " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
b forall a. [a] -> [a] -> [a]
++ String
" but isn't.")
        | Bool
otherwise = Integer
-> Integer
-> [(Integer, Word, Bool)]
-> [Integer]
-> (Integer, [(Integer, Word, Bool)], Integer)
go (Integer
aforall a. Num a => a -> a -> a
*Integer
pforall a b. (Num a, Integral b) => a -> b -> a
^Word
e) Integer
q ((Integer
p,Word
e,Bool
False)forall a. a -> [a] -> [a]
:[(Integer, Word, Bool)]
afs) []
          where
            p :: Integer
p = Integer -> Int -> Integer -> Integer
findFactor Integer
b Int
8 Integer
6
            (Word
e,Integer
q) = forall a. (Eq a, GcdDomain a) => a -> a -> (Word, a)
splitOff Integer
p Integer
b

-- | Find a factor of a known composite with approximately digits digits,
--   starting with curve s. Actually, this may loop infinitely, but the
--   loop should not be entered before the heat death of the universe.
findFactor :: Integer -> Int -> Integer -> Integer
findFactor :: Integer -> Int -> Integer -> Integer
findFactor Integer
n Int
digits Integer
s = case Integer
-> Word -> Word -> Word -> Integer -> Either Integer Integer
findLoop Integer
n Word
lo Word
hi Word
count Integer
s of
                          Left Integer
t  -> Integer -> Int -> Integer -> Integer
findFactor Integer
n (Int
digitsforall a. Num a => a -> a -> a
+Int
5) Integer
t
                          Right Integer
f -> Integer
f
  where
    (Word
lo,Word
hi,Word
count) = Int -> (Word, Word, Word)
findParms Int
digits

-- | Find a factor or say with which curve to continue.
findLoop :: Integer -> Word -> Word -> Word -> Integer -> Either Integer Integer
findLoop :: Integer
-> Word -> Word -> Word -> Integer -> Either Integer Integer
findLoop Integer
_ Word
_  Word
_  Word
0  Integer
s = forall a b. a -> Either a b
Left Integer
s
findLoop Integer
n Word
lo Word
hi Word
ct Integer
s
    | Integer
n forall a. Ord a => a -> a -> Bool
<= Integer
sforall a. Num a => a -> a -> a
+Integer
2  = forall a b. a -> Either a b
Left Integer
6
    | Bool
otherwise = case Natural -> SomeNat
someNatVal (forall a. Num a => Integer -> a
fromInteger Integer
n) of
                    SomeNat (Proxy n
_ :: Proxy t) -> case forall (n :: Natural).
KnownNat n =>
Word -> Word -> Mod n -> Maybe Integer
montgomeryFactorisation Word
lo Word
hi (forall a. Num a => Integer -> a
fromInteger Integer
s :: Mod t) of
                      Maybe Integer
Nothing -> Integer
-> Word -> Word -> Word -> Integer -> Either Integer Integer
findLoop Integer
n Word
lo Word
hi (Word
ctforall a. Num a => a -> a -> a
-Word
1) (Integer
sforall a. Num a => a -> a -> a
+Integer
1)
                      Just Integer
fct
                        | Integer -> Bool
bailliePSW Integer
fct -> forall a b. b -> Either a b
Right Integer
fct
                        | Bool
otherwise -> forall a b. b -> Either a b
Right (Integer -> Int -> Integer -> Integer
findFactor Integer
fct Int
8 (Integer
sforall a. Num a => a -> a -> a
+Integer
1))

-- | Message in the unlikely case a Baillie PSW pseudoprime is found.
bpswMessage :: Integer -> String
bpswMessage :: Integer -> String
bpswMessage Integer
n = [String] -> String
unlines
                    [ String
"\n***Congratulations! You found a Baillie PSW pseudoprime!"
                    , String
"Please report this finding to the maintainers:"
                    , String
"<daniel.is.fischer@googlemail.com>,"
                    , String
"<andrew.lelechenko@gmail.com>"
                    , String
"The number in question is:\n"
                    , forall a. Show a => a -> String
show Integer
n
                    , String
"\nOther parties like wikipedia might also be interested."
                    , String
"\nSorry for aborting your programm, but this is a major discovery."
                    ]

-- | Found a factor
found :: Integer -> String
found :: Integer -> String
found Integer
g = String
"\nA nontrivial divisor is:\n" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
g

-- | Fermat failure
fermat :: Integer -> String
fermat :: Integer -> String
fermat Integer
b = String
"\nThe Fermat test fails for base\n" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Integer
b