pyntlib
is an open sourse library for number theory written in Python, with compatibility in both 2.7 and 3.6 versions. The following is a manual for this library. Usage instructions and samples attached.
# some preparations :)
>>> from ntlib import *
-
prime(stop)
-
prime(start, end[, step])
Returns an
iterator
type generating prime numbers in an array range withstart
,end
andstep
.>>> prime(17, 89) <generator object primerange at 0x10fef7fc0>
-
primelist(upper[, lower])
Returns
list
type containing prime numbers within integerupper
andlower
bound, iflower
is given. Whenlower
is omitted, all prime numbers less than (bound excluded) theupper
bound.>>> primelist(17, 89) [17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83]
-
isdivisible(a, b)
Returns
bool
type if integersa
andb
are divisible, i.o.w. whether$b \mid a$ or$b \nmid a$ , whenb
is greater thana
, and in other cases, vice versa.>>> isdivisible(983, 234) False
-
isprime(N)
Returns
bool
type if integerN
is a prime number.>>> isprime(8563) True
-
gcd(a, b)
Returns
int
type of the greatest common divisor between integersa
andb
.>>> gcd(657, 292) 73
-
lcm(a, b)
Returns
int
type of the least common multiplier between integersa
andb
.>>> lcm(146, 28) 2044
-
coprime(a, b)
Returns
bool
type if integersa
andb
are coprime, i.e. which greatest common divisor is$one$ .>>> coprime(352, 76) False
-
eealist(a, b)
Returns
list
type containing quotients for integers$a \div b$ with extended Euclidean Algorithm.>>> eealist(23, 984) [0, 42, 1, 3, 1, 1]
-
bezout(a, b)
Returns
tuple
type containing parameters for Bézout equition of integersa
andb
.# -20*-367 + -41*179 = (-367, 179) >>> bezout(-367, 179) (-20, -41)
-
factor(N[, wrap=False])
Returns
list
type containing prime factors of integersN
, if keywordwrap
isFalse
or omitted. Once setTrue
,tuple
type of two lists will be offered, which implies the factors and their exponents.# 72 = 2 * 2 * 2 * 3 * 3 >>> factor(72) [2, 2, 2, 3, 3] # -72 = -1 * 2^3 * 3^2 >>> factor(-72, wrap=True) ([-1, 2, 3], [1, 3, 2])
-
decomposit(N)
Returns
tuple
type containing two(2) integers, which are the decoposition results of coposit numberN
, i.e.(a, b)
where$N \mid a^2-b^2$ but$N \nmid a+b$ nor$N \nmid a-b$ .# 1508^2 - 608^2 = 345 * 5520 // 345 | 1508^2 - 608^2 # 1508 + 608 = 345 * 6 + 46 // 345 ∤ 1508 + 608 # 1508 - 608 = 345 * 2 + 210 // 345 ∤ 1508 - 608 >>> decomposit(345) (1508, 608)
-
binary(a, b, c)
Returns
tuple
type containing special solutions for an indefinite binary equation, i.e.$ax + by = c$ .# 7*x + b*24 = -3 # x = 6 + 24*t (t∈Z) # y = -21 - 7*t (t∈Z) >>> binary(7,24,-3) (6, -21)
-
modulo(b, e, m)
Returns
int
type for the result of$b^e \mod m$ .# -765^264 = -291 (mod 597) >>> modulo(-765, 264, 597) -291
-
polydiv(dvdExp, dvdCoe, dvsExp, dvsCoe)
Returns
tuple
type containing the lists of exponents and coefficients of quotient and remainder polynomials, which are the division results of dividend and divisor polynomials.# (x^34 + 4x^3 + 3x^2 - 2x) = (x^27 + x^21 + x^15 + x^9 +x^3)(x^7 - x) + (x^4 + 4x^3 + 3x^2 - 2x) >>> polydiv([1, 3, 2, 34], [-2, 4, 3, 1], [7, 1], [1, -1]) ([27, 21, 15, 9, 3], [1, 1, 1, 1, 1], [4, 3, 2, 1], [1, 4, 3, -2])
-
simplify(cgcExp, cgcCoe, modulo)
Returns
tuple
type containing the lists of exponents and coefficients of result congruence after congruence simplification.# 3x^14 + 4x^13 + 2x^11 + x^9 + x^6 + x^3 + 12x^2 + x ≡ 3x^3 + 16x^2 + 6x (mod 5) >>> simplify([14, 13, 11, 9, 6, 3, 2, 1], [ 3, 4, 2, 1, 1, 1, 12, 1], 5) ([3, 2, 1], [3, 16, 6])
-
crt((mod, [x1, x2, …]), …)
Returns
list
type containing all solutions of a naïve congruence set.# x = ±1 (mod 3) # x = ±1 (mod 5) # x = ±2 (mod 7) # x = 16, 19, 26, 44, 61, 79, 86, 89 >>> crt(3, [1,-1]), (5, [1,-1]), (7, [2,-2]) [16, 19, 26, 44, 61, 79, 86, 89]
-
congsolve(cgcExp, cgcCoe, modulo)
Returns
list
type containing all solutions of an polynomial congruence.# x^2 - 46 ≡ 0 (mod 105) # x = 16, 19, 26, 44, 61, 79, 86, 89 >>> congsolve([2, 0], [1, -46], 105) [16, 19, 26, 44, 61, 79, 86, 89]
-
quadratic(p)
Returns
tuple
type containing the solutions of a quadratic polynomial, i.e.$x^2 + y^2 = p$ .# x^2 + y^2 = 2017 # x = ±9 # y = ±44 >>> quadratic(2017) (9, 44)
-
ord(m, a)
Returns
int
type for the order of an integera
modulom
, i.e.$ord_m(a)$ .# ord_9(a) = 6 >>> ord(9, 2) 6
-
euler(m)
Returns
int
type for the Euler function result of an integerm
, i.e.$\varphi (m)$ .# φ(40) = 16 >>> euler(40) 16
-
prc(m)
Returns
list
type for the primitive residue class of an integerm
.>>> prc(40) [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39]
-
root(m)
Returns
list
type for primitive roots of modulom
.>>> root(25) [2, 3, 8, 12, 13, 17, 22, 23]
-
legendre(a, p)
Returns
int
type for the result of Legendre symbol$\left(\dfrac{a}{p}\right)$ .# (3|17) = -1 >>> legendre(3, 17) -1
-
jacobi(a, m)
Returns
int
type for the result of Jacobi symbol$\left(\dfrac{a}{m}\right)$ .# (286|563) = -1 >>> jacobi(286, 563) -1
-
carmicheal(N)
Returns
bool
type if an integerN
is a Carmicheal number.>>> carmicheal(3499) False
-
pseudo([mode='Fermat'][, byte=16][, para=10000][, flag=False])
Returns
int
type for a pseudo prime number, which isbyte
long, usingmode
test withpara
times and (forFermat
test) Carmicheal number check set inflag
.-
mode
can be set to the followings (Fermat
in default)-
Fermat
—— using Fermat test for Fermat pseudo primes -
Euler
orSolovay-Stassen
—— using Solovay-Stassen test for Euler pseudo primes -
Strong
orMiller-Rabin
—— using Miller-Rabin test for strong pseudo primes
-
-
byte
is the binary length of expected pseudo primes (16
in default) -
para
is the security parameter for repetition in tests (10000
in default) -
flag
is to decide if Carmicheal numbers will be checked in Fermat test (False
in default)
>>> pseudo(mode='Fermat') 56629 >>> pseudo(mode='Euler') 38231 >>> pseudo(mode='Strong') 42451
-
-
fraction(n[, d])
Returns
list
type representing the continued fraction form of$\frac a d$ .# 7700/2145 = [3, 1, 1, 2, 3, 1, 1] >>> fraction(7700, 2145) [3, 1, 1, 2, 3, 1, 1]
-
Fraction
An extended
Fraction
class with compability to continued fraction derived from system built-in classfractions.Fraction
.-
Fraction(numerator=0, denominator=1)
-
Fraction(other_fraction)
-
Fraction(float)
-
Fraction(decimal)
-
Fraction(string)
Above are same with the constructors in
fractions.Fraction
. -
Fraction(continued_fraction)
Construction from
list
type representing a continued fraction.>>> Fraction(16, -10) Fraction(-8, 5) >>> Fraction(123) Fraction(123, 1) >>> Fraction() Fraction(0, 1) >>> Fraction('3/7') Fraction(3, 7) >>> Fraction(' -3/7 ') Fraction(-3, 7) >>> Fraction('1.414213 \t\n') Fraction(1414213, 1000000) >>> Fraction('-.125') Fraction(-1, 8) >>> Fraction('7e-6') Fraction(7, 1000000) >>> Fraction(2.25) Fraction(9, 4) >>> Fraction(1.1) Fraction(2476979795053773, 2251799813685248) >>> from decimal import Decimal >>> Fraction(Decimal('1.1')) Fraction(11, 10) >>> Fraction([-1, 1, 1, 3]) Fraction(-3, 7)
-
Properties
-
numerator
Numerator of the Fraction in lowest term.
-
denominator
Denominator of the Fraction in lowest term.
-
fraction
Continued fraction of the Fraction in
list
type. -
convergent
Convergents of the Fraction in
list
type, with elements (i.e. convergents) infractions.Fraction
type. -
number
Original fraction number of the Fraction in
fractions.Fraction
.
-
-
Data models
-
__getitem__(level)
Returns the
level
of the Fraction inconvergent
. Whenlevel
is overflowed, returnnumber
of the Fraction instead.# -3/7 --> [-1, 0, -1/2, -3/7] >>> Fraction(-3, 7)[2] Fraction(-1, 2)
-
__floor__()
Returns the greatest integer
<= self
. This method can also be accessed through themath.floor()
function:>>> from math import floor >>> floor(Fraction(355, 113)) 3
-
__ceil__()
Returns the least integer
<= self
. This method can also be accessed through themath.ceil()
function. -
__round__()
-
__round__(ndigits)
The first version returns the nearest integer to
self
, rounding half to even. The second version roundsself
to the nearest multiple ofFraction(1, 10**ndigits)
(logically, ifndigits
is negative), again rounding half toward even. This method can also be accessed through theround()
function.
-
-
-
Index
The
Index
class provides support for integer modulo index.-
Index(int)
>>> Index(41) Index(41)
-
Properties
-
modulo
Modulo of the Index.
-
root
Primitive root of the Index.
-
phi
Euler function of modulo in the Index.
-
index
Indexes to modulo of the Index in
list
type. -
table
Formatted table of indexes to modulo in the Index in
list
type.
-
-
Data models
-
__call__([a, b, …])
Returns the product of multiplication with integers
a, b, ...
after modulo of the Index. When omitted, returnsNone
.# 105 * 276 ≡ 34 (mod 41) >>> Index(41)(105, 276) 34
-
-
-
Legendre
The
Legendre
class implements Legendre symbol.-
Legendre(int, int)
-
Legendre(other_legendre)
-
Legendre(string)
>>> Legendre(2, 3) Legendre(2, 3) >>> Legendre('4|7') Legendre(4, 7) >>> Legendre(' -4|7 ') Legendre(-4, 7) >>> Legendre('47|11 \t\n') Legendre(47, 11) >>> Legendre(' 8/23 ') Legendre(8, 23) >>> Legendre('-8/23') Legendre(-8, 23)
-
Properties
-
numerator
Numerator of the Legendre symbol in lowest term.
-
denominator
Denominator of the Legendre symbol.
-
nickname
Returns
'Legendre'
.
-
-
Data models
-
__call__()
Returns final result of the Legendre symbol, which equals to
$1$ ,$-1$ or$0$ .
-
-
Methods
-
eval()
Returns final result of the Legendre symbol, which equals to
$1$ ,$-1$ or$0$ . -
simplify()
Returns simplication of the Legendre symbol in lowest term, in which numerator equals to
$0$ ,$\pm 1$ , or$\pm 2$ and denominator is prime. -
reciprocate()
Returns reciprocation of the Legendre symbol.
>>> l = Legendre(47, 5) >>> l() -1 >>> l.eval() -1 >>> l.simplify() Legendre(2, 5) >>> l.reciprocate() Legendre(42, 47)
-
convert([kind])
Converts the Legendre symbol to another kind. When given
'Jacobi'
, returns Jacobi symbol with same numerator and denominator. When omitted or given'Legendre'
, returns itself.
>>> l.convert() Legendre(47, 5) >>> l.convert('Legendre') Legendre(47, 5) >>> l.convert('Jacobi') Jacobi(47, 5)
-
-
-
Jacobi
The
Jacobi
class implements Jacobi symbol.-
Jacobi(int, int)
-
Jacobi(other_jacobi)
-
Jacobi(string)
>>> Jacobi(2, 3) Jacobi(2, 3) >>> Jacobi('4|9') Jacobi(4, 9) >>> Jacobi(' -4|9 ') Jacobi(-4, 9) >>> Jacobi('47|18 \t\n') Jacobi(47, 18) >>> Jacobi(' 8/26 ') Jacobi(8, 26) >>> Jacobi('-8/26') Jacobi(-8, 26)
-
Properties
-
numerator
Numerator of the Jacobie symbol in lowest term.
-
denominator
Denominator of the Jacobi symbol.
-
nickname
Returns
'Jacobi'
.
-
-
Data models
-
__call__()
Returns final result of the Jacobi symbol, which equals to
$1$ or$-1$ .
-
-
Methods
-
eval()
Returns final result of the Jacobi symbol, which equals to
$1$ or$-1$ . -
simplify()
Returns simplication of the Jacobi symbol in lowest term, in which numerator equals to
$0$ ,$\pm 1$ , or$\pm 2$ and denominator is prime. -
reciprocate()
Returns reciprocation of the Jacobi symbol.
>>> j = Jacobi(47, 6) >>> j() 1 >>> j.eval() 1 >>> j.simplify() Jacobi(1, 5) >>> j.reciprocate() Jacobi(41, 47)
-
convert([kind])
Converts the Jacobi symbol to another kind. When given
'Legendre'
, returns Legendre symbol with same numerator and denominator (if the latter is prime). When omitted or given'Jacobi'
, returns itself.>>> j.convert() Jacobi(47, 6) >>> j.convert('Jacobi') Jacobi(47, 6) >>> j.convert('Legendre') Legendre(47, 5)
-
-
-
Polynomial
A fully-functioned Polynomial class with support for complex coefficients.
-
Polynomial(dfvar='x')
-
default([var])
Default variable (used for common-number items) can be set when an instance is created. Also, it can be modified through
default([var])
later.
-
-
Polynomial(number)
As long as
number
is an instance of a class derivednumbers.Number
. -
Polynomial(string)
Default format of polynomial items:
$\pm \ coeficient \ (\ast) \ variable \ (\hat{} \mid \ast \ast ) \ exponent$ -
Polynomial(tuple_0, [tuple_1, …])
Default format of polynomial item tuples:
$( 'variable',\ (exponent,\ coefficient),\ \dots )$ -
Polynomial(dict)
Default format of polynomial "vec" dictionary:
${ 'variable':\ {exponent:\ coefficient,\ \dots },\ \dots }$ -
Polynomial(other_polynomial)
>>> Polynomial(4.67, dfvar='var') Polynomial(var) >>> Polynomial(4+5j) Polynomial(x) >>> Polynomial(' a^34 + 4a^3+x + y^2 /t/n') Polynomial(a, x, y) >>> Polynomial(((1,0), (4,-4), (2,3), (0,1))) Polynomial(x) >>> Polynomial(('x', (1,1)), ('y', (1, 0), (2, 1))) Polynomial(x, y) >>> Polynomial({'y': {2: 1}, 'x': {1: 1}}) Polynomial(x, y)
-
Properties
-
iscomplex
If coefficients of the Polynomial are in complex field.
-
isinteger
If coefficients of the Polynomial are in integer field.
-
ismultivar
If there are multiple variables in the Polynomial.
-
var
Name of variables in the Polynomial within
list
type. -
vector
Corespondence of variables, exponents and coefficeints in the Polynomial within
dict
type. -
dfvar
Default name of variables in the Polynomial.
-
nickname
Returns
poly
.
-
-
Methods
-
eval(dict)
Default format for
dict
definition:${ 'variable':\ value,\ \dots }$ -
eval(number)
-
eval(tuple_0[, tuple_1, …])
Default format for
tuple
definition:$( 'variable',\ value ),\ \dots$ Evaluate the Polynomial with the given values.
>>> p1 = Polynomial({'y': {2: 1}, 'x': {1: 1}}) >>> p1.eval({'y': 2, 'x': 3}) 7 >>> p2 = Polynomial(((1,0), (4,-4), (2,3), (0,1))) >>> p2.eval(5) -2424 >>> p3 = Polynomial(('x', (1,1)), ('y', (1, 0), (2, 1))) >>> p3.eval(('x', 2), ('y', 3)) 11
-
mod(dict, mod=None)
-
mod(number, mod=None)
-
mod(tuple_0[, tuple_1, …], mod=None)
Evaluate the Polynomial with the given values after modulo. If
mod
omits or sets to None, returnseval()
.>>> p4 = Polynomial({'y': {2: 1}, 'x': {1: 1}}) >>> p4.mod({'y': 2, 'x': 3}, mod=3) 1 >>> p5 = Polynomial(((1,0), (4,-4), (2,3), (0,1))) >>> p5.mod(5, mod=75) 51 >>> p6 = Polynomial(('x', (1,1)), ('y', (1, 0), (2, 1))) >>> p6.mod(('x', 2), ('y', 3), mod=5) 1
-
-
Data models
-
__reduce__()
-
__copy__()
-
__deepcopy__()
Support for pickling, copy, and deepcopy.
-
-
Notes
-
Rich comparison is implemented.
-
Algebra calculation is implemented.
-
Slice and get, set, delete are also implemented.
>>> p7 = Polynomial(((7,1), (1,-1))) >>> p8 = Polynomial(((6,1), (3,4), (2,2))) >>> p7 < p8 False >>> p9 = Polynomial(((1,0), (4,-4), (2,3), (0,1))) >>> p10 = Polynomial(((2,-1), (0,1))) >>> p9 / p10 4x^2 + 1 >>> p11 = Polynomial(('a', (1,3), (3,4), (2,2), (34,complex(1,3)))) >>> p11[1:3] 2a^2 + 3a
-
-
-
Congruence
The
Congruence
class, derived fromPolynomial
class, implements solution for mono-variable congruence in integer field.-
Congruence(dfvar='x')
-
default([var])
Default variable (used for common-number items) can be set when an instance is created. Also, it can be modified through
default([var])
later.
-
-
Congruence(number)
As long as
number
is an instance of a class derivednumbers.Number
. -
Congruence(string)
-
Congruence(tuple_0, [tuple_1, …])
-
Congruence(dict)
-
Congruence(other_congruence)
>>> Congruence(4.67, mod=7, dfvar='var') Congruence(var, mod=7) >>> Congruence(4+5j, mod=9) Congruence(x, mod=9) >>> Congruence(' a^34 + 4a^3+x + y^2 /t/n', mod=87) Congruence(a, x, y, mod=87) >>> Congruence(((1,0), (4,-4), (2,3), (0,1)), mod=3) Congruence(x, mod=3) >>> Congruence(('x', (1,1)), ('y', (1, 0), (2, 1)), mod=67) Congruence(x, y, mod=67) >>> Congruence({'y': {2: 1}, 'x': {1: 1}}, mod=90) Congruence(x, y, mod=90)
-
Properties
-
iscomplex
If coefficients of the Congruence are in complex field.
-
isinteger
If coefficients of the Congruence are in integer field.
-
ismultivar
If there are multiple variables in the Congruence.
-
isprime
If
modulo
is prime. -
var
Name of variables in the Congruence within
list
type. -
vector
Corespondence of variables, exponents and coefficeints in the Congruence within
dict
type. -
dfvar
Default name of variables in the Congruence.
-
modulo
Modulo of the Congruence.
-
solution
Solution of the Congruence.
-
nickname
Returns
cong
.
-
-
Methods
-
simplify()
Returns the Congruence after simplification.
-
solve()
Returns the
Solution
of the Congruence.The
Solution
class implements solutions for theCongruence
class.variables
—— Name of variables in the Solution withinlist
type.modulo
—— Modulo of the Solution.solutions
—— Ascending solutions of the Solution inlist
type.
The Solution is callable which returns
solutions
within. Length (len()
method) of the Solutions returns number ofsolutions
. Slice and item can also be accessed with subscripts.>>> c1 = Congruence(('z', (2014,2014), (8,8)), mod=7) >>> c1.simplify() 2014z^4 + 8z^2 ≡ 0 (mod 7) >>> c2 = Congruence(('z', (2,1), (0,-46)), mod=105) >>> c2.solve() z ≡ 16, 19, 26, 44, 61, 79, 86, 89 (mod 105)
-
eval(dict)
-
eval(number)
-
eval(tuple_0[, tuple_1, …])
Evaluate the Congruence with the given values.
>>> c3 = Congruence({'y': {2: 1}, 'x': {1: 1}}, mod=3) >>> c3.eval({'y': 2, 'x': 3}) 1 >>> c4 = Congruence(((1,0), (4,-4), (2,3), (0,1)), mod=75) >>> c4.eval(5) 51 >>> c5 = Congruence(('x', (1,1)), ('y', (1, 0), (2, 1)), mod=5) >>> c5.eval(('x', 2), ('y', 3)) 1
-
calc(dict)
-
calc(number)
-
calc(tuple_0[, tuple_1, …])
Evaluate the Congruence with the given values but without modulo.
>>> c6 = Congruence({'y': {2: 1}, 'x': {1: 1}}, mod=3) >>> c6.calc({'y': 2, 'x': 3}) 7 >>> c7 = Congruence(((1,0), (4,-4), (2,3), (0,1)), mod=75) >>> c7.calc(5) -2424 >>> c8 = Congruence(('x', (1,1)), ('y', (1, 0), (2, 1)), mod=5) >>> c8.calc(('x', 2), ('y', 3)) 11
-
-
Data models
-
__reduce__()
-
__copy__()
-
__deepcopy__()
Support for pickling, copy, and deepcopy.
-
-
-
Quadratic
The
Quadratic
class, derived fromPolynomial
class, implements solution for quadratic polynomials.-
Quadratic(number)
-
Quadratic(string)
-
Quadratic(tuple_0, [tuple_1, …])
-
Quadraticl(dict)
-
Quadratic(other_quadratic)
>>> Quadratic(4) Quadratic(x, y) >>> Quadratic(4, vars=('a', 'b')) Quadratic(a, b) >>> Quadratic(' p^2 +q^2- 9 /t/n') Quadratic(p, q) >>> Quadratic(('m', (2, 1)), ('n', (2, 1))) Quadratic(m, n) >>> Quadratic({'j': {2: 1}, 'k': {2: 1}}) Quadratic(j, k)
-
Properties
-
var
Name of variables in the Polynomial within
list
type. -
constant
Constant item in the Quadratic.
-
isprime
If the
constant
is prime. -
solution
Solution of the Quadratic.
-
nickname
Returns
quad
.
-
-
Methods
-
solve()
Returns the
Solution
of the Quadratic.The
Solution
class implements solutions for theQuadratic
class.variables
—— Name of variables in the Solution withinlist
type.modulo
—— Modulo of the Solution.solutions
—— Ascending solutions of the Solution inlist
type.
The Solution is callable which returns
solutions
within. Slice and item can also be accessed with subscripts.>>> Quadratic(8068, vars=('p', 'q')).solve() p = ±9 q = ±44
-
eval(dict)
-
eval(tuple_0, tuple_1)
Evaluate the Quadratic with the given values.
>>> q = Quadratic(4 >>> q.eval({'y': 2, 'x': 3}) 13 >>> q.eval(('x', 3), ('y', 2)) 13
-
mod(dict, mod=None)
-
mod(tuple_0[, tuple_1, …], mod=None)
Evaluate the Quadratic with the given values after modulo. If
mod
omits or sets to None, returnseval()
.>>> q.mod({'y': 2, 'x': 3}, mod=3) 1 >>> q.mod(('x', 2), ('y', 3), mod=3) 1
-
-
Data models
-
__reduce__()
-
__copy__()
-
__deepcopy__()
Support for pickling, copy, and deepcopy.
-
-