h$38,      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                    Safe-Inferred /2?  finite-fieldswitness for the existence of the field (this is an injective type family!)  finite-fieldsthe prime characteristic finite-fields-dimension over the prime field (the exponent m in q=p^m) finite-fields the size (or order) of the field finite-fields"The additive identity of the field finite-fields(The multiplicative identity of the field  finite-fields-check for equality with the additive identity  finite-fields3check for equality with the multiplicative identity  finite-fieldsan element of the prime field  finite-fields a uniformly random field element finite-fieldsa random invertible element finite-fieldsa primitive generator finite-fields*extract t he witness from a field element finite-fieldsexponentiation  finite-fieldslist of field elements (of course it's only useful for very small fields) finite-fields&The multiplicate inverse (synonym for ) finite-fields/Enumerate the elements of the prime field only  finite-fieldsThe nonzero elements in cyclic order, starting from the primitive generator (of course this is only useful for very small fields) finite-fieldsComputes a table of discrete logarithms with respect to the primitive generator. Note: zero is not present in the resulting map. finite-fieldsGeneric exponentiation   None'(/  finite-fields (prime,exponent) finite-fields$We have some Conway polynomials for m=1 too; the roots of these linear polynomials are primitive roots in F_p  Safe-Inferred/  finite-fields"Tuples" fitting into a give shape. The order is lexicographic, that is, &sort ts == ts where ts = tuples' shape Example: tuples' [2,3] = [[0,0],[0,1],[0,2],[0,3],[1,0],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[2,3]] finite-fields,positive "tuples" fitting into a give shape. finite-fieldsProduct of list of integers, but in interleaved order (for a list of big numbers, it should be faster than the linear order) finite-fieldslength (width) finite-fieldsmaximum (height) finite-fieldslength (width) finite-fieldsmaximum (height)  Safe-Inferred/  finite-fields$Inversion (using Euclid's algorithm) finite-fieldsDivision via Euclid's algorithm finite-fields'Division via multiplying by the inverse finite-fields#Extended binary Euclidean algorithm  Safe-Inferred//  finite-fields+1 or -1! finite-fields+Negate the second argument if the first is " finite-fields if even,  if odd# finite-fields (-1)^k$ finite-fields.Negate the second argument if the first is odd  !"#$%&'  !"#$%&' Safe-Inferred/- finite-fieldsLargest integer k such that 2^k is smaller or equal to n. finite-fieldsSmallest integer k such that 2^k is larger or equal to n0 finite-fieldsInteger square root (largest integer whose square is smaller or equal to the input) using Newton's method, with a faster (for large numbers) inital guess based on bit shifts.1 finite-fields=Smallest integer whose square is larger or equal to the input2 finite-fields*We also return the excess residue; that is (a,r) = integerSquareRoot' n means that "a*a + r = n a*a <= n < (a+1)*(a+1)3 finite-fieldsNewton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version.4 finite-fields d 4 n5 finite-fields.The Moebius mu function (naive implementation)6 finite-fields4The Liouville lambda function (naive implementation)7 finite-fieldsSum ofthe of the divisors8 finite-fieldsSum of k-th powers of the divisors9 finite-fieldsEuler's totient function: finite-fields Divisors of n (note: the result is not ordered!); finite-fieldsList of square-free divisors together with their Mobius mu value (note: the result is not ordered!)< finite-fields4List of square-free divisors (note: the result is not ordered!)= finite-fields2Infinite list of primes, using the TMWE algorithm.> finite-fieldsA relatively simple but still quite fast implementation of list of primes. By Will Ness http://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html? finite-fields?List of primes, using tree merge with wheel. Code by Will Ness.C finite-fieldsGroups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)] D finite-fields#The naive trial division algorithm.E finite-fieldsEfficient powers modulo m. powerMod a k m == (a^k) `mod` mF finite-fields#Prime testing using trial division G finite-fieldsMiller-Rabin Primality Test (taken from Haskell wiki). We test the primality of the first argument n by using the second argument a' as a candidate witness. If it returs False, then n is composite. If it returns True, then n is either prime or composite.A random choice between 2 and (n-2) is a good choice for a.H finite-fieldsFor very small numbers, we use trial division, for larger numbers, we apply the Miller-Rabin primality test log4(n) times, with candidate witnesses derived deterministically from n) using a pseudo-random sequence (which  should be: based on a cryptographic hash function, but isn't, yet). Thus the candidate witnesses should behave essentially like random, but the resulting function is still a deterministic, pure function.8TODO: implement the hash sequence, at the moment we use   instead...I finite-fieldsA more exhaustive version of H, this one tests candidate witnesses both the first log4(n) prime numbers and then log4(n) pseudo-random numbers-./0123456789:;<=>?@ABCDEFGHI-./01234:;<78596=>?@ABDCEFGHI Safe-Inferred '(/2yN finite-fieldsWord-sized nat-singletonsO finite-fieldsNat-singletonsS finite-fieldsYou are responsible here! (this is exported primarily because the testsuite is much simpler using this...)W finite-fieldsYou are responsible here! (this is exported primarily because the testsuite is much simpler using this...)JKLMNOPQRSTUVWXYZ[\ Safe-Inferred '(./2_ finite-fields Prime witnessb finite-fieldsPrime testing.Note: this uses trial division at the moment, so it's only good for small numbers for nowc finite-fields Escape hatchg finite-fields7Creating a witness for a number being small (less than 2^31)l finite-fieldsPrime testing.Note: this uses trial division at the moment, so it's only good for small numbers for nowo finite-fieldsCreating small primesp finite-fields Escape hatch)JKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqr)OQPRSNUTVWLMXJKYZ^efdg_a`bc]ikjhlpmnoqr[\None /2"Sv finite-fieldsAn element of the prime field F_py finite-fields/A witness for the existence of the prime field F_p| finite-fieldsNote: currently this checks the primality of the input using trial division, so it's only practical for (very) small primes...But you can use } to cheat.} finite-fields?You are responsible for guaranteeing that the input is a prime. finite-fields Note: the Ord. instance is present only so that you can use GF as key in Maps& - the ordering is kind of arbitrary! vwxyz{|}~ yz{wx|}v~ Safe-Inferred/#q finite-fields$Inversion (using Euclid's algorithm) finite-fieldsDivision via Euclid's algorithm finite-fields'Division via multiplying by the inverse finite-fields#Extended binary Euclidean algorithm  Safe-Inferred /2% finite-fieldsAn element of the prime field F_p  finite-fields/A witness for the existence of the prime field F_p finite-fieldsNote: currently this checks the primality of the input using trial division, so it's not really practical...But you can use  to cheat. finite-fields?You are responsible for guaranteeing that the input is a prime. finite-fields Note: the Ord. instance is present only so that you can use GF as key in Maps& - the ordering is kind of arbitrary! None '(/2' finite-fieldsThe prime characteristic p finite-fieldsThe dimension m of F_q over F_p finite-fields The pair (p,m) finite-fieldsUsage: lookupConwayPoly sp sm for q = p^m finite-fieldsUsage: lookupSomeConwayPoly p m for q = p^m finite-fields$We have some Conway polynomials for m=1 too; the roots of these linear polynomials are primitive roots in F_p  None '(/)) finite-fields&The vectors can have different lengths finite-fields&The vectors can have different lengths finite-fields Based on https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integersNone '(/2, finite-fields(An element of the Galois field of order q = p^m finite-fields.We need either a Conway polynomial, or in the m=1 case, a proof that p is prime finite-fieldsUsage: mkGaloisField p mto construct the field with q = p^m elementsImplementation note: For m=1 we may do a primality test, which is very slow at the moment. You can use  below to avoid this. finite-fieldsIn the case of m=1+ you are responsible for guaranteeing that p is a prime (for m>10 we have to look up a Conway polynomial anyway). finite-fields Note: the Ord. instance is present only so that you can use  as key in Maps& - the ordering is kind of arbitrary!  None /2,   !"#$%&'()* +,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                ]^(finite-fields-0.1-J7uyIkT16Ul6wwzpUUESQdMath.FiniteField.ClassMath.FiniteField.ConwayMath.FiniteField.SignMath.FiniteField.PrimesMath.FiniteField.TypeLevel!Math.FiniteField.PrimeField.Small#Math.FiniteField.PrimeField.Generic"Math.FiniteField.GaloisField.Small!Math.FiniteField.GaloisField.Zech Math.FiniteField.Conway.InternalMath.FiniteField.Misc%Math.FiniteField.PrimeField.Small.RawSystemRandom$Math.FiniteField.TypeLevel.Singleton'Math.FiniteField.PrimeField.Generic.Raw+Math.FiniteField.GaloisField.Small.Internal SomeFieldFieldWitnesscharacteristic dimension fieldSizezerooneisZeroisOneembed embedSmallrandomFieldElemrandomInvertibleprimGen witnessOfpower powerSmall enumerateinverseenumPrimeField multGroupdiscreteLogTable powerDefault$fShowSomeField HasConwayPolySignPlusMinusisPlusisMinus signValuesigned paritySignparitySignValue negateIfOdd oppositeSignmulSignproductOfSigns $fMonoidSign$fSemigroupSign$fEqSign $fShowSign $fReadSign integerLog2 ceilingLog2isSquareintegerSquareRootceilingSquareRootintegerSquareRoot'integerSquareRootNewton'divides moebiusMuliouvilleLambda divisorSum divisorSum' eulerTotientdivisorssquareFreeDivisorssquareFreeDivisors_primes primesSimple primesTMWE factorizefactorizeNaiveproductOfFactorsgroupIntegerFactorsintegerFactorsTrialDivisionpowerModisPrimeTrialDivisionmillerRabinPrimalityTestisProbablyPrimeisVeryProbablyPrime SomeSNat64SomeSNatSNat64SNat proxyOfSNatfromSNat proxyToSNat unsafeSNat proxyOfSNat64 fromSNat64 proxyToSNat64 unsafeSNat64someSNat someSNat64 someSNat64_ checkSomeSNatcheckSomeSNat64 IsSmallPrime Fits31BitsIsPrime fromPrime' fromPrimeisPrimebelieveMeItsPrime from31Bit' from31Bitfrom31BitSigned fits31BitsfromSmallPrime'fromSmallPrimefromSmallPrimeIntegerfromSmallPrimeSigned isSmallPrimesmallPrimeIsPrimesmallPrimeIsSmall mkSmallPrimebelieveMeItsASmallPrimeproxyOfproxyOf1$fShowIsSmallPrime$fShowFits31Bits $fShowIsPrimeFp SomeWitnessFp WitnessFp fromWitnessFpmkSmallPrimeFieldunsafeSmallPrimeFieldprimRoot $fFieldFp$fFractionalFp$fNumFp$fShowFp$fOrdFp$fEqFp$fShowWitnessFp$fShowSomeWitnessFp mkPrimeFieldunsafePrimeFieldSomeConwayPoly conwayPrime conwayDim conwayParams conwayParams'conwayCoefficientslookupConwayPolyunsafeLookupConwayPolylookupSomeConwayPolylookupConwayPrimRoot$fShowHasConwayPoly$fShowSomeConwayPolyGF SomeWitnessGF WitnessGF WitnessFq mkGaloisFieldunsafeGaloisField $fFieldGF$fFractionalGF$fNumGF$fShowGF$fOrdGF$fEqGF$fShowSomeWitnessGF$fShowWitnessGFZechSomeWitnessZech WitnessZechfromWitnessZech ZechTable mkZechFieldunsafeZechField makeZechTable $fFieldZech$fFractionalZech $fNumZech $fShowZech $fOrdZech$fEqZech$fShowWitnessZech$fShowZechTable$fShowSomeWitnessZechbaseGHC.Realrecip conwayParams_lookupConwayPrimRoot_ ConwayTablefromConwayTable ConwayWitnessc_conway_table_ptrc_conway_table_sizefromConwayPoly conwayPrime_getConwayEntryParamsmarshalConwayEntryencodePrimeExpodecodePrimeExpotheConwayTablelookupConwayEntryreadConwayTableIOtuples'tuples1'productInterleavedtuplestuples1swappairs pairsWith longZipWithsum' interleaveevensodds word32Tuples'w32toW64w64toW32invdivdiv2euclid64FPnegaddsubmulpowpow'euclidaddPolysubPoly invEuclidCMmulIO resizePoly scalePolymulPolyzeroPolyonePoly isZeroPoly polyDegreepolyLongDivision downIndices polyQuotientgetCPoly getCPolyIO