arithmoi-0.13.2.0: Efficient basic number-theoretic functions.

Copyright | (c) 2011 Daniel Fischer
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell2010

Math.NumberTheory.Moduli.Sqrt

Contents

- Modular square roots
- Jacobi symbol

Description

Modular square roots and Jacobi symbol.

Synopsis

- sqrtsMod :: forall (m :: Nat). SFactors Integer m -> Mod m -> [Mod m]
- sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer]
- sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer]
- sqrtsModPrime :: Integer -> Prime Integer -> [Integer]
- data JacobiSymbol
  - = MinusOne
  - | Zero
  - | One
- jacobi :: (Integral a, Bits a) => a -> a -> JacobiSymbol
- symbolToNum :: Num a => JacobiSymbol -> a

# Modular square roots

sqrtsMod :: forall (m :: Nat). SFactors Integer m -> Mod m -> [Mod m] Source #

List all modular square roots.

    >>> :set -XDataKinds
    >>> sqrtsMod sfactors (1 :: Mod 60)
    [(1 `modulo` 60),(49 `modulo` 60),(41 `modulo` 60),(29 `modulo` 60),(31 `modulo` 60),(19 `modulo` 60),(11 `modulo` 60),(59 `modulo` 60)]

sqrtsModFactorisation :: Integer -> [(Prime Integer, Word)] -> [Integer] Source #

List all square roots modulo a number, the factorisation of which is passed as a second argument.

    >>> sqrtsModFactorisation 1 (factorise 60)
    [1,49,41,29,31,19,11,59]

sqrtsModPrimePower :: Integer -> Prime Integer -> Word -> [Integer] Source #

List all square roots modulo the power of a prime.

    >>> import Data.Maybe
    >>> import Math.NumberTheory.Primes
    >>> sqrtsModPrimePower 7 (fromJust (isPrime 3)) 2
    [4,5]
    >>> sqrtsModPrimePower 9 (fromJust (isPrime 3)) 3
    [3,12,21,24,6,15]

sqrtsModPrime :: Integer -> Prime Integer -> [Integer] Source #

List all square roots by prime modulo.

    >>> import Data.Maybe
    >>> import Math.NumberTheory.Primes
    >>> sqrtsModPrime 1 (fromJust (isPrime 5))
    [1,4]
    >>> sqrtsModPrime 0 (fromJust (isPrime 5))
    [0]
    >>> sqrtsModPrime 2 (fromJust (isPrime 5))
    []

# Jacobi symbol

data JacobiSymbol Source #

Represents three possible values of Jacobi symbol.

Constructors

MinusOne |
Zero |
One |

#### Instances

Instances details

Semigroup JacobiSymbol Source # |
Instance details Defined in Math.NumberTheory.Moduli.JacobiSymbol Methods (<>) :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol Source # sconcat :: NonEmpty JacobiSymbol -> JacobiSymbol Source # stimes :: Integral b => b -> JacobiSymbol -> JacobiSymbol Source #
Show JacobiSymbol Source # |
Instance details Defined in Math.NumberTheory.Moduli.JacobiSymbol Methods showsPrec :: Int -> JacobiSymbol -> ShowS Source # show :: JacobiSymbol -> String Source # showList :: [JacobiSymbol] -> ShowS Source #
Eq JacobiSymbol Source # |
Instance details Defined in Math.NumberTheory.Moduli.JacobiSymbol Methods (==) :: JacobiSymbol -> JacobiSymbol -> Bool Source # (/=) :: JacobiSymbol -> JacobiSymbol -> Bool Source #
Ord JacobiSymbol Source # |

Instance details

Defined in Math.NumberTheory.Moduli.JacobiSymbol

Methods

compare :: JacobiSymbol -> JacobiSymbol -> Ordering Source #

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

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

(>) :: JacobiSymbol -> JacobiSymbol -> Bool Source #

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

max :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol Source #

min :: JacobiSymbol -> JacobiSymbol -> JacobiSymbol Source #

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

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 -- arguments have a common factor 11
    Zero
    >>> jacobi 1001 9907
    MinusOne

symbolToNum :: Num a => JacobiSymbol -> a Source #

Convenience function to convert out of a Jacobi symbol