Copyright	(c) 2015-2019 Frederick Schneider
License	MIT
Maintainer	Frederick Schneider <fws.nyc@gmail.com>
Stability	Provisional
Safe Haskell	None
Language	Haskell2010

Math.NumberTheory.Canon.AurifCyclo

Description

Aurifeullian and Cyclotomic factorization method functions.

Synopsis

aurCandDec :: Integer -> Integer -> Bool -> Maybe (Integer, Integer)
aurDec :: Integer -> Maybe (Array Integer Integer, Array Integer Integer)
applyCycloPair :: Integer -> Integer -> Integer -> [Integer]
applyCycloPairWithMap :: Integer -> Integer -> Integer -> CycloMap -> ([Integer], CycloMap)
cyclo :: Integer -> (CycloPair, CycloMap)
cycloWithMap :: Integer -> CycloMap -> (CycloPair, CycloMap)
cycloDivSet :: Integer -> CycloMap
cycloDivSetWithMap :: Integer -> CycloMap -> (CycloMap, CycloMap)
chineseAurif :: Integer -> Integer -> Bool -> Maybe (Integer, Integer)
chineseAurifWithMap :: Integer -> Integer -> Bool -> CycloMap -> (Maybe (Integer, Integer), CycloMap)
crCycloAurifApply :: Bool -> CR_ -> CR_ -> CR_ -> Integer -> CycloMap -> (CR_, CycloMap)
applyCrCycloPair :: Integer -> Integer -> CR_ -> CycloMap -> ([Integer], CycloMap)
divvy :: [Integer] -> Integer -> Integer -> [Integer]
data CycloMap
getIntegerBasedCycloMap :: CycloMap -> Map Integer CycloPair
showCyclo :: CR_ -> CycloMap -> [Char]
crCycloInitMap :: CycloMap
multPoly :: Num a => [a] -> [a] -> [a]
divPoly :: Integral a => [a] -> [a] -> [a]
addPoly :: Num a => [a] -> [a] -> [a]

Documentation

aurCandDec :: Integer -> Integer -> Bool -> Maybe (Integer, Integer) Source #

This function checks if the input is a candidate for Aurifeuillian decomposition. If so, split it into two and evaluate it. Otherwise, return nothing. The code will "prep" the input params for the internal function so they will be relatively prime. Possible solutions: Non-zero multiples of xi and yi (where xi and yi are relatively prime and of the form xi = a^(a*b), yi = 1 where a and b are positive integers and b is odd. (xi and y1 may be interchanged) If a is even, we will find factors of a^(a*b) + 1. The bool flag must be True If a is odd, we will find factors of a^(a*b) - 1. The bool flag must be False

aurDec :: Integer -> Maybe (Array Integer Integer, Array Integer Integer) Source #

This function returns a pair of polynomials (in array form) or Nothing (if it's squareful). An illogical n (n <= 1) will generate an error.

applyCycloPair :: Integer -> Integer -> Integer -> [Integer] Source #

Wraps applyCycloPairWithMap with default CycloMap argument.

applyCycloPairWithMap :: Integer -> Integer -> Integer -> CycloMap -> ([Integer], CycloMap) Source #

This will use cyclotomic polynomial methods to factor x^e - b^e.

cyclo :: Integer -> (CycloPair, CycloMap) Source #

Integer wrapper for crCyclo with default CycloMap parameter

cycloWithMap :: Integer -> CycloMap -> (CycloPair, CycloMap) Source #

Integer wrapper for crCyclo

cycloDivSet :: Integer -> CycloMap Source #

Integer wrapper for crCycloDivSet with default CycloMap parameter

cycloDivSetWithMap :: Integer -> CycloMap -> (CycloMap, CycloMap) Source #

Integer wrapper for crCycloDivSet

chineseAurif :: Integer -> Integer -> Bool -> Maybe (Integer, Integer) Source #

Wrapper for chineseAurifWithMap with default CycloMap parameter

chineseAurifWithMap :: Integer -> Integer -> Bool -> CycloMap -> (Maybe (Integer, Integer), CycloMap) Source #

Integer wrapper for chineseAurifCr

crCycloAurifApply :: Bool -> CR_ -> CR_ -> CR_ -> Integer -> CycloMap -> (CR_, CycloMap) Source #

This function checks if the inputs along with operator flag have a cyclotomic or Aurifeuillian form to greatly simplify factoring. If they do not, potentially much more expesive simple factorization is used via crSimpleApply. Note: The cyclotomic map is threaded into the functions

applyCrCycloPair :: Integer -> Integer -> CR_ -> CycloMap -> ([Integer], CycloMap) Source #

These "apply cyclo" functions will use cyclotomic polynomial methods to factor x^e - b^e.

divvy :: [Integer] -> Integer -> Integer -> [Integer] Source #

Internal function requires two integers (computed via Aurif. methods) along with a list of Integers. The product of the Integers must be a divisor of the list's product otherwise an error will be generated. It's called divvy because it splits the 2 integers across the array using the gcd. This will help factoring because the larger term(s) will be broken up into smaller pieces.

data CycloMap Source #

CycloMap is a newtype hiding the details of a map of CR_ to pairs of integers and corresponding cyclotomic polynomials.

Instances

Eq CycloMap Source #
Instance details Defined in Math.NumberTheory.Canon.AurifCyclo Methods (==) :: CycloMap -> CycloMap -> Bool # (/=) :: CycloMap -> CycloMap -> Bool #
Show CycloMap Source #
Instance details Defined in Math.NumberTheory.Canon.AurifCyclo Methods showsPrec :: Int -> CycloMap -> ShowS # show :: CycloMap -> String # showList :: [CycloMap] -> ShowS #

getIntegerBasedCycloMap :: CycloMap -> Map Integer CycloPair Source #

Unwrap the CycloMap and convert the internal canon rep keys to Integers, returning a "raw" map

showCyclo :: CR_ -> CycloMap -> [Char] Source #

This will display the cyclotomic polynomials for a CR.

crCycloInitMap :: CycloMap Source #

This is an initial map with the cyclotomic polynomials for 1.

multPoly :: Num a => [a] -> [a] -> [a] Source #

Multiply two polynomials

divPoly :: Integral a => [a] -> [a] -> [a] Source #

Div function for polynomials. The assumption is that p1 is a multiple of p2

addPoly :: Num a => [a] -> [a] -> [a] Source #

Add two polynomials