Math.NumberTheory.Moduli.Jacobi

Jacobi symbol is a generalization of the Legendre symbol, useful for primality testing and integer factorization.

Documentation

data JacobiSymbol

Represents three possible values of Jacobi symbol.

Constructors

MinusOne

Zero

One

Instances

Eq JacobiSymbol

Defined in Math.NumberTheory.Moduli.Jacobi

Methods

(==) :: JacobiSymbol -> JacobiSymbol -> Bool

(/=) :: JacobiSymbol -> JacobiSymbol -> Bool

Ord JacobiSymbol

Defined in Math.NumberTheory.Moduli.Jacobi

Methods

compare :: JacobiSymbol -> JacobiSymbol -> Ordering

(<) :: JacobiSymbol -> JacobiSymbol -> Bool

(<=) :: JacobiSymbol -> JacobiSymbol -> Bool

(>) :: JacobiSymbol -> JacobiSymbol -> Bool

(>=) :: JacobiSymbol -> JacobiSymbol -> Bool

max :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol

min :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol

Show JacobiSymbol

Defined in Math.NumberTheory.Moduli.Jacobi

Methods

showsPrec :: Int -> JacobiSymbol -> ShowS

show :: JacobiSymbol -> String

showList :: [JacobiSymbol] -> ShowS

Semigroup JacobiSymbol

Defined in Math.NumberTheory.Moduli.Jacobi

Methods

(<>) :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol

sconcat :: NonEmpty JacobiSymbol -> JacobiSymbol

stimes :: Integral b => b -> JacobiSymbol -> JacobiSymbol

Monoid JacobiSymbol

Defined in Math.NumberTheory.Moduli.Jacobi

Methods

mempty :: JacobiSymbol

mappend :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol

mconcat :: [JacobiSymbol] -> JacobiSymbol

jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol

Jacobi symbol of two arguments. The lower argument ("denominator") must be odd and positive, this condition is checked.

If arguments have a common factor, the result is Zero, otherwise it is MinusOne or One.

>>> jacobi 1001 9911
Zero -- arguments have a common factor 11
>>> jacobi 1001 9907
MinusOne