h$@#7j      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                                        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/ 3 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/ j 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 n 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. finite-fields=Smallest integer whose square is larger or equal to the input 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) finite-fieldsNewton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version. finite-fields d  n finite-fields.The Moebius mu function (naive implementation) finite-fields4The Liouville lambda function (naive implementation) finite-fieldsSum ofthe of the divisors finite-fieldsSum of k-th powers of the divisors 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.) finite-fieldsGroups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)] * finite-fields#The naive trial division algorithm.+ finite-fieldsEfficient powers modulo m. powerMod a k m == (a^k) `mod` m, finite-fields#Prime testing using trial division - 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.. 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.../ finite-fieldsA more exhaustive version of ., this one tests candidate witnesses both the first log4(n) prime numbers and then log4(n) pseudo-random numbers !"#$%&'()*+,-./ !"#$%&'(*)+,-./None '(/24 finite-fieldsWord-sized nat-singletons5 finite-fieldsNat-singletons9 finite-fieldsYou are responsible here! (this is exported primarily because the testsuite is much simpler using this...)= finite-fieldsYou are responsible here! (this is exported primarily because the testsuite is much simpler using this...)0123456789:;<=>?@ABNone '(./2A E finite-fields A proof that k|nF finite-fields nG finite-fields kH finite-fields q=n/kK finite-fields Prime witnessN finite-fieldsPrime testing.Note: this uses trial division at the moment, so it's only good for small numbers for nowO finite-fields Escape hatchS finite-fields7Creating a witness for a number being small (less than 2^31)X finite-fieldsPrime testing.Note: this uses trial division at the moment, so it's only good for small numbers for now[ finite-fieldsCreating small primes\ finite-fields Escape hatch40123456789:;<=>?@ABCDEHFGIJKLMNOPQRSTUVWXYZ[\]^_`abc4576894;:<=23>01?@JQRPSKMLNOIUWVTX\YZ[EFGH]^_CD`abcABNone/ 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 None '(/2k finite-fieldsThe prime characteristic pl finite-fieldsThe dimension m of F_q over F_pm finite-fields The pair (p,m)p finite-fieldsUsage: lookupConwayPoly sp sm for q = p^mr finite-fieldsUsage: lookupSomeConwayPoly p m for q = p^ms finite-fields$We have some Conway polynomials for m=1 too; the roots of these linear polynomials are primitive roots in F_p ijklmnopqrs ijklmnorpqsNone '(/  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?'x finite-fields A class for field element types y finite-fieldswitness for the existence of the field (this is an injective type family!) z finite-fields the characteristic at type level{ finite-fieldsthe dimension at type level| 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-fieldsFrobenius automorphism x -> x^p finite-fieldslist of field elements (of course it's only useful for very small fields) finite-fieldsReturns "GF(p)" or @"GF(p^m)" 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 (that is, the additive identitiy of the field) is not present in the resulting map. finite-fieldsGeneric exponentiation!vwx~}|{zy!x~}|{zyvwNone /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 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!  None /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 '(/20t 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 /256 finite-fieldsAn element of the field GF(p^m)Implementation note: Field elements are represented by integers from the interval  [-1...q-2]:-1 corresponds to 00 corresponds to 11 corresponds to gk corresponds to g^k finite-fieldsSome subfield of GF(p,m) finite-fieldsA witness for the subfield GF(p,k) of GF(p,m) finite-fieldswitness for the ambient field finite-fields)witness for the existence of the subfield finite-fields proof that k divides m finite-fields the quotient (p^m-1)/(p^k-1) finite-fieldsA table of Zech logarithms (and some more data required for the operations) finite-fieldsthe parameters (p,m) finite-fields"order of the multiplicative group  q-1 = p^m - 1  finite-fields an integer e such that g^e = -1 finite-fields embedding of F_p into F_q (including 0) finite-fields2Zech's logarithms (except for 0; so the length is q-1) finite-fieldsReturns something like "GF(p^3) E GF(p^6)" None /26 finite-fieldsAn element of the field finite-fields4Save the data necessary to do computations to a file finite-fields6Load the data necessary to do computations from a file33  !"#$%&'()*+,-./0123456789:;<=>?@ABCCDDEFGHIJKLMNOPQRSTTUVWXYZ[\]^_`abcdefghijklmn-o3pqrstuvwwxyz{|}~                                                                                                                                                    EF(finite-fields-0.2-BMildsyEGpFKDlOnLA9h8UMath.FiniteField.ConwayMath.FiniteField.SignMath.FiniteField.PrimesMath.FiniteField.TypeLevelMath.FiniteField.Class!Math.FiniteField.PrimeField.Small#Math.FiniteField.PrimeField.Generic"Math.FiniteField.GaloisField.Small!Math.FiniteField.GaloisField.Zech#Math.FiniteField.GaloisField.Zech.C 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 ConwayPolySignPlusMinusisPlusisMinus 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_ checkSomeSNatcheckSomeSNat64DivisorDivides _dividend_divisor _quotient IsSmallPrime Fits31BitsIsPrime fromPrime' fromPrimeisPrimebelieveMeItsPrime from31Bit' from31Bitfrom31BitSigned fits31BitsfromSmallPrime'fromSmallPrimefromSmallPrimeIntegerfromSmallPrimeSigned isSmallPrimesmallPrimeIsPrimesmallPrimeIsSmall mkSmallPrimebelieveMeItsASmallPrime dividendSNat divisorSNatconstructDivisorproxyOfproxyOf1 $fShowDivides $fShowDivisor$fShowIsSmallPrime$fShowFits31Bits $fShowIsPrimeSomeConwayPoly conwayPrime conwayDim conwayParams conwayParams'conwayCoefficientslookupConwayPolyunsafeLookupConwayPolylookupSomeConwayPolylookupConwayPrimRoot$fShowConwayPoly$fShowSomeConwayPoly SomeFieldFieldWitnessPrimeDimcharacteristic dimension fieldSizezerooneisZeroisOneembed embedSmallrandomFieldElemrandomInvertibleprimGen witnessOfpower powerSmall frobenius enumeratefieldPrimeSNatfieldPrimeSNat64 fieldDimSNatfieldDimSNat64 fieldNameinverseenumPrimeField multGroupdiscreteLogTable powerDefault$fShowSomeFieldFp SomeWitnessFp WitnessFp fromWitnessFpmkSmallPrimeFieldunsafeSmallPrimeFieldprimRoot $fFieldFp$fFractionalFp$fNumFp$fShowFp$fOrdFp$fEqFp$fShowWitnessFp$fShowSomeWitnessFp mkPrimeFieldunsafePrimeFieldGF SomeWitnessGF WitnessGF WitnessFq mkGaloisFieldunsafeGaloisFieldconstructGaloisField $fFieldGF$fFractionalGF$fNumGF$fShowGF$fOrdGF$fEqGF$fShowSomeWitnessGF$fShowWitnessGFZech SomeSubFieldSubFieldambientWitnesssubFieldWitness subFieldProof fiberSizeSomeWitnessZech WitnessZechfromWitnessZech ZechTable _zechParams_qMinus1 _logMinus1 _embedding _zechLogs mkZechFieldunsafeZechFieldconstructZechField subFieldNameconstructSubFieldenumerateSubFields embedSubFieldprojectSubField isInSubField makeZechTable $fFieldZech$fFractionalZech $fNumZech $fShowZech $fOrdZech$fEqZech$fShowSubField$fShowWitnessZech$fShowZechTable$fShowSomeSubField$fShowSomeWitnessZechRawCFq SomeWitnessCWitnessCzech_enumerate zech_embed zech_is_one zech_is_zero zech_primzech_one zech_zerozech_powzech_divzech_mulzech_invzech_subzech_addzech_neg fromWitnessCmkCField unsafeCFieldmakeCZechTablemarshalZechTablesaveCZechTableloadCZechTableconstructWitnessC randomCFq randomInvCFqfromRawrawNegrawAddrawSubrawInvrawMulrawDivrawPow rawIsZerorawIsOnerawZerorawOnerawPrimrawEmbed rawEnumeraterawPrimerawDim rawFieldSize cboolToBool $fShowCFq$fOrdCFq$fEqCFq $fShowRaw $fFieldCFq$fFractionalCFq$fNumCFq$fEqRaw$fOrdRaw$fShowWitnessC$fShowSomeWitnessC conwayParams_lookupConwayPrimRoot_ ConwayTablefromConwayTable ConwayWitnessc_conway_table_ptrc_conway_table_sizefromConwayPoly conwayPrime_getConwayEntryParamsmarshalConwayEntryencodePrimeExpodecodePrimeExpotheConwayTablelookupConwayEntryreadConwayTableIOtuples'tuples1'productInterleavedtuplestuples1swappairs pairsWith longZipWithsum' interleaveevensodds word32Tuples'w32toW64w64toW32invdivdiv2euclid64FPnegaddsubmulpowpow'snat64IfOneThenElseeuclidaddPolysubPoly invEuclidCMmulIO resizePoly scalePolymulPolyzeroPolyonePoly isZeroPoly polyDegreepolyLongDivision downIndices polyQuotientgetCPoly getCPolyIObaseGHC.Realrecip