-- |
-- Module:      Math.NumberTheory.Primes.Testing.Probabilistic
-- Copyright:   (c) 2011 Daniel Fischer, 2017 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Daniel Fischer <daniel.is.fischer@googlemail.com>
--
-- Probabilistic primality tests, Miller-Rabin and Baillie-PSW.

{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE MagicHash           #-}
{-# LANGUAGE ScopedTypeVariables #-}

module Math.NumberTheory.Primes.Testing.Probabilistic
  ( isPrime
  , millerRabinV
  , bailliePSW
  , isStrongFermatPP
  , isFermatPP
  , lucasTest
  ) where

import Data.Bits
import Data.Mod
import Data.Proxy
import GHC.Exts (Word(..), Int(..), (-#), (<#), isTrue#)
import GHC.Integer.GMP.Internals
import GHC.TypeNats (KnownNat, SomeNat(..), someNatVal)

import Math.NumberTheory.Moduli.JacobiSymbol
import Math.NumberTheory.Primes.Small
import Math.NumberTheory.Roots
import Math.NumberTheory.Utils

-- | @isPrime n@ tests whether @n@ is a prime (negative or positive).
--   It is a combination of trial division and Baillie-PSW test.
--
--   If @isPrime n@ returns @False@ then @n@ is definitely composite.
--   There is a theoretical possibility that @isPrime n@ is @True@,
--   but in fact @n@ is not prime. However, no such numbers are known
--   and none exist below @2^64@. If you have found one, please report it,
--   because it is a major discovery.
isPrime :: Integer -> Bool
isPrime :: Integer -> Bool
isPrime Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0       = Integer -> Bool
isPrime (-Integer
n)
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
2       = Bool
False
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
4       = Bool
True
  | Bool
otherwise   = Int -> Integer -> Bool
millerRabinV Int
0 Integer
n -- trial division test
                  Bool -> Bool -> Bool
&& Integer -> Bool
bailliePSW Integer
n

-- | Miller-Rabin probabilistic primality test. It consists of the trial
-- division test and several rounds of the strong Fermat test with different
-- bases. The choice of trial divisors and bases are
-- implementation details and may change in future silently.
--
-- First argument stands for the number of rounds of strong Fermat test.
-- If it is 0, only trial division test is performed.
--
-- If @millerRabinV k n@ returns @False@ then @n@ is definitely composite.
-- Otherwise @n@ may appear composite with probability @1/4^k@.
millerRabinV :: Int -> Integer -> Bool
millerRabinV :: Int -> Integer -> Bool
millerRabinV Int
k Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0       = Int -> Integer -> Bool
millerRabinV Int
k (-Integer
n)
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
2       = Bool
False
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
4       = Bool
True
  | Bool
otherwise   = [Integer] -> Bool
go [Integer]
smallPrimes
    where
      go :: [Integer] -> Bool
go (Integer
p:[Integer]
ps)
        | Integer
pInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
n   = Bool
True
        | Bool
otherwise = (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
0) Bool -> Bool -> Bool
&& [Integer] -> Bool
go [Integer]
ps
      go [] = (Integer -> Bool) -> [Integer] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Integer -> Integer -> Bool
isStrongFermatPP Integer
n) (Int -> [Integer] -> [Integer]
forall a. Int -> [a] -> [a]
take Int
k [Integer]
smallPrimes)
      smallPrimes :: [Integer]
smallPrimes = (Word16 -> Integer) -> [Word16] -> [Integer]
forall a b. (a -> b) -> [a] -> [b]
map Word16 -> Integer
forall a. Integral a => a -> Integer
toInteger ([Word16] -> [Integer]) -> [Word16] -> [Integer]
forall a b. (a -> b) -> a -> b
$ Word16 -> Word16 -> [Word16]
smallPrimesFromTo Word16
forall a. Bounded a => a
minBound Word16
forall a. Bounded a => a
maxBound

-- | @'isStrongFermatPP' n b@ tests whether non-negative @n@ is
--   a strong Fermat probable prime for base @b@.
--
--   Apart from primes, also some composite numbers have the tested
--   property, but those are rare. Very rare are composite numbers
--   having the property for many bases, so testing a large prime
--   candidate with several bases can identify composite numbers
--   with high probability. An odd number @n > 3@ is prime if and
--   only if @'isStrongFermatPP' n b@ holds for all @b@ with
--   @2 <= b <= (n-1)/2@, but of course checking all those bases
--   would be less efficient than trial division, so one normally
--   checks only a relatively small number of bases, depending on
--   the desired degree of certainty. The probability that a randomly
--   chosen base doesn't identify a composite number @n@ is less than
--   @1/4@, so five to ten tests give a reasonable level of certainty
--   in general.
--
--   Please consult <https://miller-rabin.appspot.com Deterministic variants of the Miller-Rabin primality test>
--   for the best choice of bases.
isStrongFermatPP :: Integer -> Integer -> Bool
isStrongFermatPP :: Integer -> Integer -> Bool
isStrongFermatPP Integer
n Integer
b
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0          = [Char] -> Bool
forall a. HasCallStack => [Char] -> a
error [Char]
"isStrongFermatPP: negative argument"
  | 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
  | Bool
otherwise      = case Natural -> SomeNat
someNatVal (Integer -> Natural
forall a. Num a => Integer -> a
fromInteger Integer
n) of
                     SomeNat (Proxy n
_ :: Proxy t) -> Mod n -> Bool
forall (n :: Nat). KnownNat n => Mod n -> Bool
isStrongFermatPPMod (Integer -> Mod n
forall a. Num a => Integer -> a
fromInteger Integer
b :: Mod t)

isStrongFermatPPMod :: KnownNat n => Mod n -> Bool
isStrongFermatPPMod :: Mod n -> Bool
isStrongFermatPPMod Mod n
b = Mod n
b Mod n -> Mod n -> Bool
forall a. Eq a => a -> a -> Bool
== Mod n
0 Bool -> Bool -> Bool
|| Mod n
a Mod n -> Mod n -> Bool
forall a. Eq a => a -> a -> Bool
== Mod n
1 Bool -> Bool -> Bool
|| Word -> Mod n -> Bool
forall t. (Eq t, Num t) => t -> Mod n -> Bool
go Word
t Mod n
a
  where
    m :: Mod n
m = -Mod n
1
    (Word
t, Natural
u) = Natural -> (Word, Natural)
forall a. Integral a => a -> (Word, a)
shiftToOddCount (Natural -> (Word, Natural)) -> Natural -> (Word, Natural)
forall a b. (a -> b) -> a -> b
$ Mod n -> Natural
forall (m :: Nat). Mod m -> Natural
unMod Mod n
m
    a :: Mod n
a = Mod n
b Mod n -> Natural -> Mod n
forall (m :: Nat) a.
(KnownNat m, Integral a) =>
Mod m -> a -> Mod m
^% Natural
u

    go :: t -> Mod n -> Bool
go t
0 Mod n
_ = Bool
False
    go t
k Mod n
x = Mod n
x Mod n -> Mod n -> Bool
forall a. Eq a => a -> a -> Bool
== Mod n
m Bool -> Bool -> Bool
|| t -> Mod n -> Bool
go (t
k t -> t -> t
forall a. Num a => a -> a -> a
- t
1) (Mod n
x Mod n -> Mod n -> Mod n
forall a. Num a => a -> a -> a
* Mod n
x)

-- | @'isFermatPP' n b@ tests whether @n@ is a Fermat probable prime
--   for the base @b@, that is, whether @b^(n-1) `mod` n == 1@.
--   This is a weaker but simpler condition. However, more is lost
--   in strength than is gained in simplicity, so for primality testing,
--   the strong check should be used. The remarks about
--   the choice of bases to test from @'isStrongFermatPP'@ apply
--   with the modification that if @a@ and @b@ are Fermat bases
--   for @n@, then @a*b@ /always/ is a Fermat base for @n@ too.
--   A /Charmichael number/ is a composite number @n@ which is a
--   Fermat probable prime for all bases @b@ coprime to @n@. By the
--   above, only primes @p <= n/2@ not dividing @n@ need to be tested
--   to identify Carmichael numbers (however, testing all those
--   primes would be less efficient than determining Carmichaelness
--   from the prime factorisation; but testing an appropriate number
--   of prime bases is reasonable to find out whether it's worth the
--   effort to undertake the prime factorisation).
isFermatPP :: Integer -> Integer -> Bool
isFermatPP :: Integer -> Integer -> Bool
isFermatPP Integer
n Integer
b = case Natural -> SomeNat
someNatVal (Integer -> Natural
forall a. Num a => Integer -> a
fromInteger Integer
n) of
  SomeNat (Proxy n
_ :: Proxy t) -> (Integer -> Mod n
forall a. Num a => Integer -> a
fromInteger Integer
b :: Mod t) Mod n -> Integer -> Mod n
forall (m :: Nat) a.
(KnownNat m, Integral a) =>
Mod m -> a -> Mod m
^% (Integer
nInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
1) Mod n -> Mod n -> Bool
forall a. Eq a => a -> a -> Bool
== Mod n
1

-- | Primality test after Baillie, Pomerance, Selfridge and Wagstaff.
--   The Baillie-PSW test consists of a strong Fermat probable primality
--   test followed by a (strong) Lucas primality test. This implementation
--   assumes that the number @n@ to test is odd and larger than @3@.
--   Even and small numbers have to be handled before. Also, before
--   applying this test, trial division by small primes should be performed
--   to identify many composites cheaply (although the Baillie-PSW test is
--   rather fast, about the same speed as a strong Fermat test for four or
--   five bases usually, it is, for large numbers, much more costly than
--   trial division by small primes, the primes less than @1000@, say, so
--   eliminating numbers with small prime factors beforehand is more efficient).
--
--   The Baillie-PSW test is very reliable, so far no composite numbers
--   passing it are known, and it is known (Gilchrist 2010) that no
--   Baillie-PSW pseudoprimes exist below @2^64@. However, a heuristic argument
--   by Pomerance indicates that there are likely infinitely many Baillie-PSW
--   pseudoprimes. On the other hand, according to
--   <http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html> there is
--   reason to believe that there are none with less than several
--   thousand digits, so that for most use cases the test can be
--   considered definitive.
bailliePSW :: Integer -> Bool
bailliePSW :: Integer -> Bool
bailliePSW Integer
n = Integer -> Integer -> Bool
isStrongFermatPP Integer
n Integer
2 Bool -> Bool -> Bool
&& Integer -> Bool
lucasTest Integer
n

-- precondition: n odd, > 3 (no small prime factors, typically large)
-- | The Lucas-Selfridge test, including square-check, but without
--   the Fermat test. For package-internal use only.
lucasTest :: Integer -> Bool
lucasTest :: Integer -> Bool
lucasTest Integer
n
  | Integer -> Bool
forall a. Integral a => a -> Bool
isSquare Integer
n Bool -> Bool -> Bool
|| Integer
d Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Bool
False
  | Integer
d Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1               = Bool
True
  | Bool
otherwise            = Integer
uo Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
|| Word -> Integer -> Integer -> Bool
forall t. (Eq t, Num t) => t -> Integer -> Integer -> Bool
go Word
t Integer
vo Integer
qo
    where
      d :: Integer
d = Bool -> Integer -> Integer
find Bool
True Integer
5
      find :: Bool -> Integer -> Integer
find !Bool
pos Integer
cd = case Integer -> Integer -> JacobiSymbol
forall a. (Integral a, Bits a) => a -> a -> JacobiSymbol
jacobi (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
cd) Integer
cd of
                       JacobiSymbol
MinusOne -> if Bool
pos then Integer
cd else (-Integer
cd)
                       JacobiSymbol
Zero     -> if Integer
cd Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
n then Integer
1 else Integer
0
                       JacobiSymbol
One      -> Bool -> Integer -> Integer
find (Bool -> Bool
not Bool
pos) (Integer
cdInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
2)
      q :: Integer
q = (Integer
1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
d) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
4
      (Word
t,Integer
o) = Integer -> (Word, Integer)
forall a. Integral a => a -> (Word, a)
shiftToOddCount (Integer
nInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
+Integer
1)
      (Integer
uo, Integer
vo, Integer
qo) = Integer -> Integer -> Integer -> (Integer, Integer, Integer)
testLucas Integer
n Integer
q Integer
o
      go :: t -> Integer -> Integer -> Bool
go t
0 Integer
_ Integer
_ = Bool
False
      go t
s Integer
vn Integer
qn = Integer
vn Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
|| t -> Integer -> Integer -> Bool
go (t
st -> t -> t
forall a. Num a => a -> a -> a
-t
1) ((Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n) ((Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n)


-- n odd positive, n > abs q, index odd
testLucas :: Integer -> Integer -> Integer -> (Integer, Integer, Integer)
testLucas :: Integer -> Integer -> Integer -> (Integer, Integer, Integer)
testLucas Integer
n Integer
q (S# Int#
i#) = Int -> (Integer, Integer, Integer)
look (Word -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
2)
  where
    j :: Int
j = Int# -> Int
I# Int#
i#
    look :: Int -> (Integer, Integer, Integer)
look Int
k
      | Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
j Int
k = Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Integer
1 Integer
1 Integer
1 Integer
q
      | Bool
otherwise   = Int -> (Integer, Integer, Integer)
look (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
    go :: Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go Int
k Integer
un Integer
un1 Integer
vn Integer
qn
      | Int
k Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0       = (Integer
un, Integer
vn, Integer
qn)
      | Int -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Int
j Int
k = Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Integer
u2n1 Integer
u2n2 Integer
v2n1 Integer
q2n1
      | Bool
otherwise   = Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go (Int
kInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Integer
u2n Integer
u2n1 Integer
v2n Integer
q2n
        where
          u2n :: Integer
u2n   = (Integer
unInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          u2n1 :: Integer
u2n1  = (Integer
un1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          u2n2 :: Integer
u2n2  = ((Integer
un1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
un)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          v2n :: Integer
v2n   = (Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          v2n1 :: Integer
v2n1  = ((Integer
un1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- (Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
un)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          q2n :: Integer
q2n   = (Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          q2n1 :: Integer
q2n1  = (Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
testLucas Integer
n Integer
q (Jp# BigNat
bn#) = Int# -> (Integer, Integer, Integer)
test (Int#
s# Int# -> Int# -> Int#
-# Int#
1#)
  where
    s# :: Int#
s# = BigNat -> Int#
sizeofBigNat# BigNat
bn#
    test :: Int# -> (Integer, Integer, Integer)
test Int#
j# = case BigNat -> Int# -> GmpLimb#
indexBigNat# BigNat
bn# Int#
j# of
                GmpLimb#
0## -> Int# -> (Integer, Integer, Integer)
test (Int#
j# Int# -> Int# -> Int#
-# Int#
1#)
                GmpLimb#
w# -> Int# -> Word -> Int -> (Integer, Integer, Integer)
look (Int#
j# Int# -> Int# -> Int#
-# Int#
1#) (GmpLimb# -> Word
W# GmpLimb#
w#) (Word -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
    look :: Int# -> Word -> Int -> (Integer, Integer, Integer)
look Int#
j# Word
w Int
i
      | Word -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Word
w Int
i = Int#
-> Word
-> Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go Int#
j# Word
w (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Integer
1 Integer
1 Integer
1 Integer
q
      | Bool
otherwise   = Int# -> Word -> Int -> (Integer, Integer, Integer)
look Int#
j# Word
w (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1)
    go :: Int#
-> Word
-> Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go Int#
k# Word
w Int
i Integer
un Integer
un1 Integer
vn Integer
qn
      | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0       = if Int# -> Bool
isTrue# (Int#
k# Int# -> Int# -> Int#
<# Int#
0#)
                         then (Integer
un,Integer
vn,Integer
qn)
                         else Int#
-> Word
-> Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go (Int#
k# Int# -> Int# -> Int#
-# Int#
1#) (GmpLimb# -> Word
W# (BigNat -> Int# -> GmpLimb#
indexBigNat# BigNat
bn# Int#
k#)) (Word -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Word
0 :: Word) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) Integer
un Integer
un1 Integer
vn Integer
qn
      | Word -> Int -> Bool
forall a. Bits a => a -> Int -> Bool
testBit Word
w Int
i = Int#
-> Word
-> Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go Int#
k# Word
w (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Integer
u2n1 Integer
u2n2 Integer
v2n1 Integer
q2n1
      | Bool
otherwise   = Int#
-> Word
-> Int
-> Integer
-> Integer
-> Integer
-> Integer
-> (Integer, Integer, Integer)
go Int#
k# Word
w (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Integer
u2n Integer
u2n1 Integer
v2n Integer
q2n
        where
          u2n :: Integer
u2n   = (Integer
unInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          u2n1 :: Integer
u2n1  = (Integer
un1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          u2n2 :: Integer
u2n2  = ((Integer
un1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
un)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          v2n :: Integer
v2n   = (Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          v2n1 :: Integer
v2n1  = ((Integer
un1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- (Integer
2Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
un)Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
vnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          q2n :: Integer
q2n   = (Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qn) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
          q2n1 :: Integer
q2n1  = (Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
qnInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
q) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`rem` Integer
n
-- Listed as a precondition of lucasTest
testLucas Integer
_ Integer
_ Integer
_ = [Char] -> (Integer, Integer, Integer)
forall a. HasCallStack => [Char] -> a
error [Char]
"lucasTest: negative argument"