Module ImportFrom alias ImportFrom alias alias ImportFrom alias Import alias Import alias ClassDef bases NameLoad body Expr Str Pass decorator_list ClassDef bases NameLoad body Pass decorator_list ClassDef bases NameLoad body Pass decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str If CompareLt NameLoad Num body Raise Call NameLoad BinOpMod Str NameLoad Return Call NameLoad NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam defaults body Expr Str Assert CompareEq SubscriptLoad NameLoad Index Num Num Assert CompareGt Call NameLoad NameLoad Num While CompareGtE Call NameLoad NameLoad Call NameLoad NameLoad body If CompareNotEq SubscriptLoad NameLoad Index Num Num body For NameStore Call NameLoad Num BinOpAdd Call NameLoad NameLoad Num body Assign SubscriptStore NameLoad Index UnaryOpUSub NameLoad BinOpMod BinOpSub SubscriptLoad NameLoad Index UnaryOpUSub NameLoad BinOpMult SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index UnaryOpUSub NameLoad NameLoad Assign NameStore SubscriptLoad NameLoad Slice Num Num Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults body Expr Str Assign NameStore BinOpMult BinOpSub BinOpAdd Call NameLoad NameLoad Call NameLoad NameLoad Num ListLoad Num For NameStore Call NameLoad Call NameLoad NameLoad body For NameStore Call NameLoad Call NameLoad NameLoad body Assign SubscriptStore NameLoad Index BinOpAdd NameLoad NameLoad BinOpMod BinOpAdd SubscriptLoad NameLoad Index BinOpAdd NameLoad NameLoad BinOpMult SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad Return Call NameLoad NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam NameParam NameParam defaults body Expr Str Assert CompareLt NameLoad NameLoad If CompareEq NameLoad Num body Return ListLoad Num Assign NameStore NameLoad Assign NameStore NameLoad If CompareEq BinOpMod NameLoad Num Num body Assign NameStore NameLoad orelse Assign NameStore ListLoad Num While CompareGt NameLoad Num body Assign NameStore BinOpFloorDiv NameLoad Num Assign NameStore Call NameLoad NameLoad NameLoad NameLoad NameLoad If CompareEq BinOpMod NameLoad Num Num body Assign NameStore Call NameLoad NameLoad NameLoad NameLoad NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assert CompareGtE NameLoad Num Assert CompareEq BinOpMod NameLoad Num Num Assign NameStore BinOpMod NameLoad NameLoad If CompareEq NameLoad Num body Return Num If CompareEq NameLoad Num body Return Num Assign TupleStore NameStore NameStore TupleLoad NameLoad Num While CompareEq BinOpMod NameLoad Num Num body Assign TupleStore NameStore NameStore TupleLoad BinOpFloorDiv NameLoad Num BinOpAdd NameLoad Num If BoolOpOr CompareEq BinOpMod NameLoad Num Num CompareEq BinOpMod NameLoad Num Num CompareEq BinOpMod NameLoad Num Num body Assign NameStore Num orelse Assign NameStore Num If CompareEq NameLoad Num body Return NameLoad If BoolOpAnd CompareEq BinOpMod NameLoad Num Num CompareEq BinOpMod NameLoad Num Num body Assign NameStore UnaryOpUSub NameLoad Return BinOpMult NameLoad Call NameLoad BinOpMod NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Assert CompareLtELt Num NameLoad NameLoad Assert CompareLt Num NameLoad If CompareEq NameLoad Num body Return Num If CompareEq NameLoad Num body Return NameLoad Assign NameStore Call NameLoad NameLoad NameLoad If CompareEq NameLoad Num body Raise Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad If CompareEq BinOpMod NameLoad Num Num body Return Call NameLoad NameLoad BinOpFloorDiv BinOpAdd NameLoad Num Num NameLoad If CompareEq BinOpMod NameLoad Num Num body Assign NameStore Call NameLoad NameLoad BinOpFloorDiv BinOpSub NameLoad Num Num NameLoad If CompareEq NameLoad Num body Return Call NameLoad NameLoad BinOpFloorDiv BinOpAdd NameLoad Num Num NameLoad If CompareEq NameLoad BinOpSub NameLoad Num body Return BinOpMod BinOpMult BinOpMult Num NameLoad Call NameLoad BinOpMult Num NameLoad BinOpFloorDiv BinOpSub NameLoad Num Num NameLoad NameLoad Raise Call NameLoad Str For NameStore Call NameLoad Num NameLoad body If CompareEq Call NameLoad BinOpSub BinOpMult NameLoad NameLoad BinOpMult Num NameLoad NameLoad Num body Assign NameStore TupleLoad NameLoad UnaryOpUSub NameLoad Num Assign NameStore Call NameLoad TupleLoad Num Num BinOpFloorDiv BinOpAdd NameLoad Num Num NameLoad NameLoad Assert CompareEq SubscriptLoad NameLoad Index Num Num Return SubscriptLoad NameLoad Index Num Raise Call NameLoad Str decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str If BoolOpOr CompareLt NameLoad Num CompareLtE NameLoad NameLoad body Assign NameStore BinOpMod NameLoad NameLoad Assign TupleStore NameStore NameStore TupleLoad NameLoad NameLoad Assign TupleStore NameStore NameStore NameStore NameStore TupleLoad Num Num Num Num While CompareNotEq NameLoad Num body Assign TupleStore NameStore NameStore NameStore BinOpAdd Call NameLoad NameLoad NameLoad TupleLoad NameLoad Assign TupleStore NameStore NameStore NameStore NameStore TupleLoad BinOpSub NameLoad BinOpMult NameLoad NameLoad BinOpSub NameLoad BinOpMult NameLoad NameLoad NameLoad NameLoad Assert CompareEq NameLoad Num If CompareGt NameLoad Num body Return NameLoad orelse Return BinOpAdd NameLoad NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str While NameLoad body Assign TupleStore NameStore NameStore TupleLoad BinOpMod NameLoad NameLoad NameLoad Return NameLoad decorator_list FunctionDef arguments args defaults vararg body Expr Str If CompareGt Call NameLoad NameLoad Num body Return Call NameLoad NameLoad NameLoad If Call NameLoad SubscriptLoad NameLoad Index Num Str body Return Call NameLoad NameLoad SubscriptLoad NameLoad Index Num Return SubscriptLoad NameLoad Index Num decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Return BinOpFloorDiv BinOpMult NameLoad NameLoad Call NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args defaults vararg body Expr Str If CompareGt Call NameLoad NameLoad Num body Return Call NameLoad NameLoad NameLoad If Call NameLoad SubscriptLoad NameLoad Index Num Str body Return Call NameLoad NameLoad SubscriptLoad NameLoad Index Num Return SubscriptLoad NameLoad Index Num decorator_list FunctionDef arguments args NameParam defaults body Expr Str Assert Call NameLoad NameLoad NameLoad If CompareLt NameLoad Num body Return ListLoad Assign NameStore ListLoad Assign NameStore Num For NameStore NameLoad body If CompareGt NameLoad NameLoad body Break Assign TupleStore NameStore NameStore Call NameLoad NameLoad NameLoad If CompareEq NameLoad Num body Assign NameStore Num While CompareLtE NameLoad NameLoad body Assign NameStore NameLoad Assign TupleStore NameStore NameStore Call NameLoad NameLoad NameLoad If CompareNotEq NameLoad Num body Break Assign NameStore BinOpAdd NameLoad Num Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If CompareGt NameLoad SubscriptLoad NameLoad Index Num body If Call NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad Num orelse Assign NameStore SubscriptLoad NameLoad Index Num While Num body Assign NameStore BinOpAdd NameLoad Num Assign TupleStore NameStore NameStore Call NameLoad NameLoad NameLoad If CompareLt NameLoad NameLoad body Break If CompareEq NameLoad Num body Assign NameStore Num Assign NameStore NameLoad While CompareLtE NameLoad NameLoad body Assign TupleStore NameStore NameStore Call NameLoad NameLoad NameLoad If CompareNotEq NameLoad Num body Break Assign NameStore NameLoad Assign NameStore BinOpAdd NameLoad Num Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad NameLoad If CompareGt NameLoad Num body Expr Call AttributeLoad NameLoad attr TupleLoad NameLoad Num Return NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str Assert Call NameLoad NameLoad NameLoad If CompareLt NameLoad Num body Return Num Assign NameStore Num Assign NameStore Call NameLoad NameLoad For NameStore NameLoad body Assign NameStore SubscriptLoad NameLoad Index Num If CompareGt NameLoad Num body Assign NameStore BinOpMult BinOpMult NameLoad BinOpPow SubscriptLoad NameLoad Index Num BinOpSub NameLoad Num BinOpSub SubscriptLoad NameLoad Index Num Num orelse Assign NameStore BinOpMult NameLoad BinOpSub SubscriptLoad NameLoad Index Num Num Return NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str Return Call NameLoad Call NameLoad NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str If CompareLt Call NameLoad NameLoad Num body Return Num Assign NameStore Call NameLoad SubscriptLoad NameLoad Index Num For NameStore Call NameLoad Num Call NameLoad NameLoad body Assign NameStore Call NameLoad NameLoad Call NameLoad SubscriptLoad NameLoad Index NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str Assign TupleStore NameStore NameStore NameLoad If BoolOpAnd CompareEq NameLoad Num CompareGt NameLoad Num body Return BinOpPow Num BinOpSub NameLoad Num orelse Return BinOpMult BinOpSub NameLoad Num BinOpPow NameLoad BinOpSub NameLoad Num decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str If CompareLtE NameLoad Num body Return Num Assert CompareEq Call NameLoad NameLoad NameLoad Num Assign NameStore NameLoad Assign NameStore Num While CompareNotEq NameLoad Num body Assign NameStore BinOpMod BinOpMult NameLoad NameLoad NameLoad Assign NameStore BinOpAdd NameLoad Num Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str While Num body Assign NameStore Call NameLoad NameLoad NameLoad If CompareLtE NameLoad Num body Break Assign NameStore NameLoad While Num body Assign TupleStore NameStore NameStore Call NameLoad NameLoad NameLoad If CompareGt NameLoad Num body Break Assign NameStore NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str Return Call NameLoad NameLoad Call NameLoad NameLoad NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str Global identifier Assign NameStore Num If CompareLtE NameLoad SubscriptLoad NameLoad Index Num body If CompareIn NameLoad NameLoad body Return NameLoad orelse Return NameLoad If CompareNotEq Call NameLoad NameLoad BinOpMult BinOpMult BinOpMult BinOpMult Num Num Num Num Num Num body Return NameLoad Assign NameStore Num Assign NameStore BinOpAdd Num Call NameLoad Call AttributeLoad NameLoad attr NameLoad Num For TupleStore NameStore NameStore TupleLoad TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num TupleLoad Num Num body If CompareLt NameLoad NameLoad body Break Assign NameStore NameLoad Assign NameStore Num Assign NameStore BinOpSub NameLoad Num While CompareEq BinOpMod NameLoad Num Num body Assign NameStore BinOpAdd NameLoad Num Assign NameStore BinOpFloorDiv NameLoad Num For NameStore Call NameLoad NameLoad body Assign NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore Call NameLoad NameLoad NameLoad NameLoad If BoolOpAnd CompareNotEq NameLoad Num CompareNotEq NameLoad BinOpSub NameLoad Num body Assign NameStore Num While BoolOpAnd CompareLtE NameLoad BinOpSub NameLoad Num CompareNotEq NameLoad BinOpSub NameLoad Num body Assign NameStore Call NameLoad NameLoad Num NameLoad If CompareEq NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Return NameLoad Assign NameStore BinOpAdd NameLoad Num If CompareNotEq NameLoad BinOpSub NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Return NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam defaults body Expr Str If CompareLt NameLoad Num body Return Num Assign NameStore BinOpBitOr BinOpAdd NameLoad Num Num While UnaryOpNot Call NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad Num Return NameLoad decorator_list Assign NameStore ListLoad Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Assign NameStore Num FunctionDef arguments args defaults body Expr Call NameLoad Str Assert CompareEq Call NameLoad BinOpMult BinOpMult Num Num Num BinOpMult BinOpMult Num Num Num BinOpMult BinOpMult Num Num Num BinOpMult Num Num Assert CompareEq Call NameLoad ListLoad BinOpMult BinOpMult Num Num Num BinOpMult BinOpMult Num Num Num BinOpMult BinOpMult Num Num Num BinOpMult Num Num Assert CompareEq Call NameLoad Num Num Expr Call NameLoad Str Assert CompareEq Call NameLoad Num BinOpMult Num Num BinOpMult Num Num BinOpMult BinOpMult Num Num Num Assert CompareEq Call NameLoad ListLoad Num BinOpMult Num Num BinOpMult Num Num BinOpMult BinOpMult Num Num Num Assert CompareEq Call NameLoad Num Num Expr Call NameLoad Str Assign NameStore TupleLoad Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num Num For NameStore Call NameLoad BinOpSub Call NameLoad NameLoad Num body Assert CompareEq Call NameLoad SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index BinOpAdd NameLoad Num Assign NameStore Num For NameStore NameLoad body Expr Call NameLoad BinOpMod Str NameLoad Assign NameStore ListLoad For NameStore Call NameLoad Num BinOpAdd Num BinOpFloorDiv NameLoad Num body Assign NameStore BinOpMod BinOpMult NameLoad NameLoad NameLoad Expr Call AttributeLoad NameLoad attr NameLoad Assign NameStore Call NameLoad NameLoad NameLoad If CompareNotEq BinOpMod BinOpMult NameLoad NameLoad NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad NameLoad NameLoad For NameStore Call NameLoad Num NameLoad body If CompareNotIn NameLoad NameLoad body TryExcept body Assign NameStore Call NameLoad NameLoad NameLoad handlers ExceptHandler type NameLoad body Pass orelse Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad For NameStore Call NameLoad Num Num Num body Expr Call NameLoad BinOpMod Str NameLoad If Call NameLoad NameLoad body Assign NameStore ListLoad For NameStore Call NameLoad Num NameLoad body If CompareNotEq Call NameLoad BinOpMult NameLoad NameLoad NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad NameLoad Expr Call AttributeLoad NameLoad attr BinOpMod BinOpMult NameLoad NameLoad NameLoad For NameStore Call NameLoad Num NameLoad body If UnaryOpNot CompareIn NameLoad NameLoad body If CompareNotEq Call NameLoad NameLoad NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad orelse Assign NameStore Call NameLoad NameLoad For NameStore Call NameLoad Num NameLoad body Assign NameStore Num For NameStore NameLoad body Assign NameStore BinOpMult NameLoad BinOpPow Call NameLoad NameLoad SubscriptLoad NameLoad Index Num SubscriptLoad NameLoad Index Num If CompareNotEq NameLoad Call NameLoad NameLoad NameLoad body Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad NameLoad Expr Call NameLoad Str Import alias Assign NameStore Num For NameStore Call NameLoad Num body Assign NameStore Call AttributeLoad NameLoad attr Num Num For NameStore Call NameLoad Num body Assign NameStore Call AttributeLoad NameLoad attr Num BinOpSub NameLoad Num If CompareEq Call NameLoad NameLoad NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Assign NameStore Call NameLoad NameLoad NameLoad If BoolOpOr CompareLtE NameLoad Num CompareGtE NameLoad NameLoad CompareNotEq BinOpMod BinOpMult NameLoad NameLoad NameLoad Num body Assign NameStore BinOpAdd NameLoad Num Expr Call NameLoad BinOpMod Str TupleLoad NameLoad NameLoad NameLoad Assert CompareGt NameLoad Num Expr Call NameLoad NameLoad Str ClassDef bases NameLoad body Pass decorator_list Expr Call NameLoad NameLoad Str If CompareNotEq NameLoad Num body Raise Call NameLoad BinOpMod Str NameLoad decorator_list If CompareEq NameLoad Str body Expr Call NameLoad
N/A __future__ division six print_ integer_types six.moves reduce N/A math N/A types Error N/A Exception N/A N/A Base class for exceptions in this module. N/A N/A SquareRootError N/A Error N/A N/A N/A NegativeExponentError N/A Error N/A N/A N/A modular_exp N/A N/A base exponent modulus N/A N/A N/A Raise base to exponent, reducing by modulus N/A N/A exponent 0 N/A N/A N/A NegativeExponentError N/A Negative exponents (%d) not allowed exponent N/A N/A pow base exponent modulus N/A polynomial_reduce_mod N/A N/A poly polymod p N/A N/A N/A Reduce poly by polymod, integer arithmetic modulo p.

  Polynomials are represented as lists of coefficients
  of increasing powers of x. N/A N/A N/A polymod N/A -1 1 N/A N/A N/A len polymod 1 N/A N/A N/A len poly N/A len polymod N/A N/A N/A N/A poly N/A -1 0 N/A N/A i N/A range 2 N/A N/A len polymod 1 N/A N/A N/A poly N/A N/A i N/A N/A N/A poly N/A N/A i N/A N/A poly N/A -1 N/A polymod N/A N/A i p N/A poly N/A poly N/A 0 -1 N/A poly N/A polynomial_multiply_mod N/A N/A m1 m2 polymod p N/A N/A N/A Polynomial multiplication modulo a polynomial over ints mod p.

  Polynomials are represented as lists of coefficients
  of increasing powers of x. N/A prod N/A N/A N/A N/A len m1 N/A len m2 1 N/A 0 N/A i N/A range N/A len m1 N/A N/A j N/A range N/A len m2 N/A N/A N/A prod N/A N/A i j N/A N/A N/A prod N/A N/A i j N/A N/A m1 N/A i N/A m2 N/A j p N/A N/A polynomial_reduce_mod prod polymod p N/A polynomial_exp_mod N/A N/A base exponent polymod p N/A N/A N/A Polynomial exponentiation modulo a polynomial over ints mod p.

  Polynomials are represented as lists of coefficients
  of increasing powers of x. N/A N/A exponent p N/A N/A exponent 0 N/A N/A N/A 1 N/A G base N/A k exponent N/A N/A N/A k 2 1 N/A N/A s G N/A N/A s N/A 1 N/A N/A k 1 N/A N/A k N/A k 2 N/A G N/A polynomial_multiply_mod G G polymod p N/A N/A N/A k 2 1 N/A N/A s N/A polynomial_multiply_mod G s polymod p N/A s N/A jacobi N/A N/A a n N/A N/A N/A Jacobi symbol N/A N/A n 3 N/A N/A N/A n 2 1 N/A a N/A a n N/A N/A a 0 N/A N/A 0 N/A N/A a 1 N/A N/A 1 N/A N/A a1 e N/A a 0 N/A N/A N/A a1 2 0 N/A N/A N/A a1 e N/A N/A a1 2 N/A e 1 N/A N/A N/A N/A e 2 0 N/A N/A n 8 1 N/A N/A n 8 7 N/A N/A s 1 N/A N/A s -1 N/A N/A a1 1 N/A N/A s N/A N/A N/A N/A n 4 3 N/A N/A a1 4 3 N/A N/A s N/A s N/A N/A s N/A jacobi N/A n a1 a1 N/A square_root_mod_prime N/A N/A a p N/A N/A N/A Modular square root of a, mod p, p prime. N/A N/A 0 a p N/A N/A 1 p N/A N/A a 0 N/A N/A 0 N/A N/A p 2 N/A N/A a N/A jac N/A jacobi a p N/A N/A jac -1 N/A N/A N/A SquareRootError N/A %d has no square root modulo %d N/A a p N/A N/A N/A p 4 3 N/A N/A N/A modular_exp a N/A N/A p 1 4 p N/A N/A N/A p 8 5 N/A N/A d N/A modular_exp a N/A N/A p 1 4 p N/A N/A d 1 N/A N/A N/A modular_exp a N/A N/A p 3 8 p N/A N/A d N/A p 1 N/A N/A N/A N/A N/A 2 a N/A modular_exp N/A 4 a N/A N/A p 5 8 p p N/A N/A RuntimeError Shouldn't get here. N/A b N/A range 2 p N/A N/A N/A N/A jacobi N/A N/A b b N/A 4 a p -1 N/A N/A f N/A a N/A b 1 N/A ff N/A polynomial_exp_mod N/A 0 1 N/A N/A p 1 2 f p N/A N/A N/A ff N/A 1 0 N/A N/A ff N/A 0 N/A N/A RuntimeError No b found. N/A inverse_mod N/A N/A a m N/A N/A N/A Inverse of a mod m. N/A N/A N/A a 0 N/A m a N/A N/A a N/A a m N/A N/A c d N/A a m N/A N/A uc vc ud vd N/A 1 0 0 1 N/A N/A c 0 N/A N/A N/A q c d N/A N/A divmod d c N/A c N/A N/A uc vc ud vd N/A N/A ud N/A q uc N/A vd N/A q vc uc vc N/A N/A d 1 N/A N/A ud 0 N/A N/A ud N/A N/A N/A ud m N/A gcd2 N/A N/A a b N/A N/A N/A Greatest common divisor using Euclid's algorithm. N/A a N/A N/A N/A a b N/A N/A b a a N/A b N/A gcd N/A N/A N/A a N/A N/A Greatest common divisor.

  Usage: gcd( [ 2, 4, 6 ] )
  or:    gcd( 2, 4, 6 )
   N/A N/A N/A len a 1 N/A N/A N/A reduce gcd2 a N/A N/A hasattr N/A a N/A 0 __iter__ N/A N/A N/A reduce gcd2 N/A a N/A 0 N/A N/A a N/A 0 N/A lcm2 N/A N/A a b N/A N/A N/A Least common multiple of two integers. N/A N/A N/A a b N/A gcd a b N/A lcm N/A N/A N/A a N/A N/A Least common multiple.

  Usage: lcm( [ 3, 4, 5 ] )
  or:    lcm( 3, 4, 5 )
   N/A N/A N/A len a 1 N/A N/A N/A reduce lcm2 a N/A N/A hasattr N/A a N/A 0 __iter__ N/A N/A N/A reduce lcm2 N/A a N/A 0 N/A N/A a N/A 0 N/A factorization N/A N/A n N/A N/A N/A Decompose n into a list of (prime,exponent) pairs. N/A N/A isinstance n integer_types N/A N/A n 2 N/A N/A N/A N/A result N/A N/A d 2 N/A d smallprimes N/A N/A N/A d n N/A N/A N/A N/A q r N/A divmod n d N/A N/A r 0 N/A N/A count 1 N/A N/A d n N/A N/A n q N/A N/A q r N/A divmod n d N/A N/A r 0 N/A N/A N/A count N/A count 1 N/A N/A N/A result append N/A d count N/A N/A n N/A smallprimes N/A -1 N/A N/A N/A is_prime n N/A N/A N/A N/A result append N/A n 1 N/A N/A d N/A smallprimes N/A -1 N/A 1 N/A N/A d N/A d 2 N/A N/A q r N/A divmod n d N/A N/A q d N/A N/A N/A N/A r 0 N/A N/A count 1 N/A n q N/A N/A d n N/A N/A N/A q r N/A divmod n d N/A N/A r 0 N/A N/A N/A n q N/A count N/A count 1 N/A N/A N/A result append N/A d count N/A N/A n 1 N/A N/A N/A N/A result append N/A n 1 N/A result N/A phi N/A N/A n N/A N/A N/A Return the Euler totient function of n. N/A N/A isinstance n integer_types N/A N/A n 3 N/A N/A 1 N/A result 1 N/A ff N/A factorization n N/A f ff N/A N/A e N/A f N/A 1 N/A N/A e 1 N/A N/A result N/A N/A result N/A N/A f N/A 0 N/A e 1 N/A N/A f N/A 0 1 N/A N/A result N/A result N/A N/A f N/A 0 1 N/A result N/A carmichael N/A N/A n N/A N/A N/A Return Carmichael function of n.

  Carmichael(n) is the smallest integer x such that
  m**x = 1 mod n for all m relatively prime to n.
   N/A N/A carmichael_of_factorized N/A factorization n N/A carmichael_of_factorized N/A N/A f_list N/A N/A N/A Return the Carmichael function of a number that is
  represented as a list of (prime,exponent) pairs.
   N/A N/A N/A len f_list 1 N/A N/A 1 N/A result N/A carmichael_of_ppower N/A f_list N/A 0 N/A i N/A range 1 N/A len f_list N/A N/A result N/A lcm result N/A carmichael_of_ppower N/A f_list N/A i N/A result N/A carmichael_of_ppower N/A N/A pp N/A N/A N/A Carmichael function of the given power of the given prime.
   N/A N/A p a pp N/A N/A N/A p 2 N/A a 2 N/A N/A N/A 2 N/A a 2 N/A N/A N/A N/A p 1 N/A p N/A a 1 N/A order_mod N/A N/A x m N/A N/A N/A Return the order of x in the multiplicative group mod m.
   N/A N/A m 1 N/A N/A 0 N/A N/A N/A gcd x m 1 N/A z x N/A result 1 N/A N/A z 1 N/A N/A z N/A N/A z x m N/A result N/A result 1 N/A result N/A largest_factor_relatively_prime N/A N/A a b N/A N/A N/A Return the largest factor of a relatively prime to b.
   N/A 1 N/A N/A d N/A gcd a b N/A N/A d 1 N/A N/A N/A b d N/A 1 N/A N/A N/A q r N/A divmod a d N/A N/A r 0 N/A N/A N/A a q N/A a N/A kinda_order_mod N/A N/A x m N/A N/A N/A Return the order of x in the multiplicative group mod m',
  where m' is the largest factor of m relatively prime to x.
   N/A N/A order_mod x N/A largest_factor_relatively_prime m x N/A is_prime N/A N/A n N/A N/A N/A Return True if x is prime, False otherwise.

  We use the Miller-Rabin test, as given in Menezes et al. p. 138.
  This test is not exact: there are composite values n for which
  it returns True.

  In testing the odd numbers from 10000001 to 19999999,
  about 66 composites got past the first test,
  5 got past the second test, and none got past the third.
  Since factors of 2, 3, 5, 7, and 11 were detected during
  preliminary screening, the number of numbers tested by
  Miller-Rabin was (19999999 - 10000001)*(2/3)*(4/5)*(6/7)
  = 4.57 million.
   N/A miller_rabin_test_count N/A miller_rabin_test_count 0 N/A N/A n N/A smallprimes N/A -1 N/A N/A N/A n smallprimes N/A N/A True N/A N/A False N/A N/A N/A gcd n N/A N/A N/A N/A 2 3 5 7 11 1 N/A N/A False N/A t 40 N/A n_bits N/A 1 N/A int N/A N/A math log n 2 N/A N/A k tt N/A N/A 100 27 N/A 150 18 N/A 200 15 N/A 250 12 N/A 300 9 N/A 350 8 N/A 400 7 N/A 450 6 N/A 550 5 N/A 650 4 N/A 850 3 N/A 1300 2 N/A N/A N/A n_bits k N/A N/A N/A t tt N/A s 0 N/A r N/A n 1 N/A N/A N/A r 2 0 N/A N/A s N/A s 1 N/A r N/A r 2 N/A i N/A range t N/A N/A a N/A smallprimes N/A i N/A y N/A modular_exp a r n N/A N/A N/A y 1 N/A y N/A n 1 N/A N/A j 1 N/A N/A N/A j N/A s 1 N/A y N/A n 1 N/A N/A y N/A modular_exp y 2 n N/A N/A y 1 N/A N/A miller_rabin_test_count N/A i 1 N/A False N/A j N/A j 1 N/A N/A y N/A n 1 N/A N/A miller_rabin_test_count N/A i 1 N/A False N/A True N/A next_prime N/A N/A starting_value N/A N/A N/A Return the smallest prime larger than the starting value. N/A N/A starting_value 2 N/A N/A 2 N/A result N/A N/A starting_value 1 1 N/A N/A N/A is_prime result N/A N/A result N/A result 2 N/A result N/A N/A smallprimes N/A 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 N/A miller_rabin_test_count 0 __main__ N/A N/A N/A N/A N/A N/A print_ Testing gcd... N/A N/A N/A gcd N/A N/A 3 5 7 N/A N/A 3 5 11 N/A N/A 3 5 13 N/A 3 5 N/A N/A N/A gcd N/A N/A N/A 3 5 7 N/A N/A 3 5 11 N/A N/A 3 5 13 N/A 3 5 N/A N/A N/A gcd 3 3 N/A N/A print_ Testing lcm... N/A N/A N/A lcm 3 N/A 5 3 N/A 7 3 N/A N/A 3 5 7 N/A N/A N/A lcm N/A 3 N/A 5 3 N/A 7 3 N/A N/A 3 5 7 N/A N/A N/A lcm 3 3 N/A N/A print_ Testing next_prime... N/A bigprimes N/A 999671 999683 999721 999727 999749 999763 999769 999773 999809 999853 999863 999883 999907 999917 999931 999953 999959 999961 999979 999983 N/A i N/A range N/A N/A len bigprimes 1 N/A N/A N/A N/A next_prime N/A bigprimes N/A i N/A bigprimes N/A N/A i 1 N/A error_tally 0 N/A p smallprimes N/A N/A N/A print_ N/A Testing square_root_mod_prime for modulus p = %d. p N/A squares N/A N/A root N/A range 0 N/A 1 N/A p 2 N/A N/A sq N/A N/A root root p N/A N/A N/A squares append sq N/A calculated N/A square_root_mod_prime sq p N/A N/A N/A N/A calculated calculated p sq N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A Failed to find %d as sqrt( %d ) mod %d. Said %d. N/A root sq p calculated N/A nonsquare N/A range 0 p N/A N/A N/A nonsquare squares N/A N/A N/A N/A calculated N/A square_root_mod_prime nonsquare p N/A N/A N/A SquareRootError N/A N/A N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A Failed to report no root for sqrt( %d ) mod %d. N/A nonsquare p N/A m N/A range 3 400 2 N/A N/A N/A print_ N/A Testing jacobi for modulus m = %d. m N/A N/A is_prime m N/A N/A squares N/A N/A root N/A range 1 m N/A N/A N/A N/A jacobi N/A root root m 1 N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A jacobi( %d * %d, %d ) != 1 N/A root root m N/A N/A N/A squares append N/A N/A root root m N/A i N/A range 1 m N/A N/A N/A N/A i squares N/A N/A N/A N/A jacobi i m -1 N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A jacobi( %d, %d ) != -1 N/A i m N/A N/A f N/A factorization m N/A a N/A range 1 m N/A N/A c 1 N/A i f N/A N/A c N/A c N/A N/A jacobi a N/A i N/A 0 N/A i N/A 1 N/A N/A c N/A jacobi a m N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A %d != jacobi( %d, %d ) N/A c a m N/A N/A print_ Testing inverse_mod . . . N/A random N/A n_tests 0 N/A i N/A range 100 N/A N/A m N/A N/A random randint 20 10000 N/A j N/A range 100 N/A N/A a N/A N/A random randint 1 N/A m 1 N/A N/A N/A gcd a m 1 N/A N/A n_tests N/A n_tests 1 N/A inv N/A inverse_mod a m N/A N/A N/A inv 0 N/A inv m N/A N/A N/A a inv m 1 N/A N/A error_tally N/A error_tally 1 N/A N/A print_ N/A %d = inverse_mod( %d, %d ) is wrong. N/A inv a m N/A N/A n_tests 1000 N/A N/A print_ n_tests  tests of inverse_mod completed. FailedTest N/A Exception N/A N/A N/A N/A N/A print_ error_tally errors detected. N/A N/A error_tally 0 N/A N/A N/A FailedTest N/A %d errors detected error_tally N/A N/A N/A __name__ __main__ N/A N/A N/A __main__