úÎBœ@%      !"#$Good experimental#Vincent Hanquez <vincent@snarc.org>None%&' ()*   %&' ()*None 5os2ip converts a byte string into a positive integer 5i2osp converts a positive integer into a byte string 7just like i2osp, but take an extra parameter for size. $ if the number is too big to fit in len bytes, nothing is returned 2 otherwise the number is padded with 0 to fit the len required. /FIXME: use unsafeCreate to fill the bytestring &just like i2ospOf except that it doesn't expect a failure. D for example if you just took a modulo of the number that represent & the size (example the RSA modulo n). ;returns the number of bytes to store an integer with i2osp =FIXME: really slow implementation. use log or bigger shifts. +   + Good experimental#Vincent Hanquez <vincent@snarc.org>None&generate a positive integer x, s.t. 0 <= x < m 8Note that depending on m value, the number distribution 8 generated by this function is not necessarily uniform. 7generate a number between the inclusive bound [low,high]. 8generate a positive integer of a specific size in bits. E the number of bits need to be multiple of 8. It will always returns & an integer that is close to 2^(1+bits/'8) by setting the 2 highest bits to 1. Good experimental#Vincent Hanquez <vincent@snarc.org> Safe-Inferred*sqrti returns two integer (l,b) so that l < = sqrt i <= b N the implementation is quite naive, use an approximation for the first number L and use a dichotomy algorithm to compute the bound relatively efficiently. 9get the extended GCD of two integer using integer divMod Tget the extended GCD of two integer using the extended binary algorithm (HAC 14.61) ? get (x,y,d) where d = gcd(a,b) and x,y satisfying ax + by = d (check if a list of integer are all even Good experimental#Vincent Hanquez <vincent@snarc.org> Safe-Inferred,ARaised when two numbers are supposed to be coprimes but are not. Gexponantiation_rtl_binary computes modular exponantiation as b^e mod m E using the right-to-left binary exponentiation algorithm (HAC 14.79) <exponantiation computes modular exponantiation as b^e mod m  using repetitive squaring. 8inverse computes the modular inverse as in g^(-1) mod m 2Compute the modular inverse of 2 coprime numbers. 6 This is equivalent to inverse except that the result  is known to exists. 9if the numbers are not defined as coprime, this function & will raise a CoprimesAssertionError. ,-.,-.Good experimental#Vincent Hanquez <vincent@snarc.org>None )returns if the number is probably prime. G first a list of small primes are implicitely tested for divisibility, A then a fermat primality test is used with arbitrary numbers and K then the Miller Rabin algorithm is used with an accuracy of 30 recursions 0generate a prime number of the required bitsize @generate a prime number of the form 2p+1 where p is also prime. = it is also knowed as a Sophie Germaine prime or safe prime. JThe number of safe prime is significantly smaller to the number of prime,  as such it shouldn'6t be used if this number is supposed to be kept safe. <find a prime from a starting point where the property hold. >find a prime from a starting point with no specific property. !LMiller Rabin algorithm return if the number is probably prime or composite. [ the tries parameter is the number of recursion, that determines the accuracy of the test. "/Probabilitic Test using Fermat primility test. D Beware of Carmichael numbers that are Fermat liars, i.e. this test < is useless for them. always combines with some other test. #"Test naively is integer is prime. D while naive, we skip even number and stop iteration at i > sqrt(n) $.Test is two integer are coprime to each other /%list of the first primes till 2903..  !"&number of iterations of the algorithm  starting a number to test for primality #$/0  !"#$  #!"$  !"#$/01      !"#$%&'()*+,-./0112345crypto-numbers-0.2.1Crypto.Number.PolynomialCrypto.Number.SerializeCrypto.Number.GenerateCrypto.Number.BasicCrypto.Number.ModArithmeticCrypto.Number.Prime PolynomialMonomialtoListfromListaddPolysubPolynegPolymulPoly squarePolyexpPolydivPolyos2ipi2ospi2ospOfi2ospOf_ lengthBytes generateMaxgenerateBetweengenerateOfSizesqrtigcde gcde_binaryareEvenexponantiation_rtl_binaryexponantiationinverseinverseCoprimesisProbablyPrime generatePrimegenerateSafePrimefindPrimeFromWith findPrimeFromprimalityTestMillerRabinprimalityTestFermatprimalityTestNaive isCoprime getWeight mergePoly$fShowPolynomial$fShowMonomial $fOrdMonomial divMod256CoprimesAssertionError!$fExceptionCoprimesAssertionError firstPrimesdivides