h&G=      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                                        None)*1[ 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-Inferred1  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-Inferred1 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-Inferred1 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-Inferred1 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-fields?@AB Safe-Inferred )*015 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`abcAB Safe-Inferred1 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 )*15!k 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 ijklmnorpqs Safe-Inferred )*1" 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_integers Safe-Inferred 15)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 the 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~}|{zyvw Safe-Inferred 15.  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-fieldsConstructing elements finite-fieldsThe order of the field finite-fieldsEnumarte all field elements finite-fieldsPowers finite-fields$Inversion (using Euclid's algorithm) finite-fieldsDivision via Euclid's algorithm finite-fields'Division via multiplying by the inverse 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!   Safe-Inferred 151  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-fieldsConstructing elements finite-fieldsThe order of the field finite-fieldsPowers finite-fields$Inversion (using Euclid's algorithm) finite-fieldsDivision via Euclid's algorithm finite-fields'Division via multiplying by the inverse 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!  Safe-Inferred )*156  finite-fields An alias for GF p m5, that is, the elements of the Galois field of order q = p^m 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-fieldsAn element of the prime field finite-fields2The field element corresponding to the polynomial X! (which is a primitive generator) finite-fields2The field element corresponding to the polynomial c*X finite-fields7Enumerate all field elements (in a lexicographic order) finite-fields Note: the Ord. instance is present only so that you can use  as key in Maps& - the ordering is kind of arbitrary!    Safe-Inferred 15; 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)" finite-fieldsGF(p^m) as a vector space over GF(p^k) None 15= 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.0.1-87FevXN4Pzomm8qtca4GHMath.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'sublistsintegerRndSequencesnat64IfOneThenElseeuclidaddPolysubPoly invEuclidCMmulIO resizePoly scalePolymulPolyzeroPolyonePoly isZeroPoly polyDegreepolyLongDivision downIndices polyQuotientgetCPoly getCPolyIObaseGHC.RealrecipfpfpOrder enumerateFpfpPow_fpInvfpDivfpDiv2fpPowFqgengen' enumerateFqsubFieldCoordinates