Z_ |
The ring of integers: Z_ = ZZ(). Since the integers
are Python integers, no type is reported:
73 >> Z_ ⇒ 73 |
Q_ |
The field of rational numbers.
Examples:
|
domain(f) |
This function returns the domain of the object f.
Examples: |
K_(f) |
If f is a polynomial, a vector, or a matrix, this function yields the domain over which
f is defined.
Examples: |
is_sub_domain(A,B) |
Tests whether a domain A is
a sub-domain of a domain B.
Examples: |
belongs(x, X) |
If x is an object and
X a domain, it returns
True if x
belongs to X, and False
otherwise.
Examples: |
is_zero(a) |
True if a is 0, False otherwise. |
base(B) |
If B is a domain which is a simple extension of a domain A, it returns the domain A. See Finite rings and fields. |
max_domain(A1,..., An) union_domain(A1,A2) |
If A1, ..., An are domains, this function returns the smallest domain A such that Aj ⊆ A for all j = 1, ..., n. For n = 2, it is equivalent to union_domain. |
lift(a) |
If a = push(x,A), where A is a domain and x an object, lift(a) returns an object x' in the same domain as x such that a = push(x',A) and which is simplest with this condition. For example, lift(push(19,Zn(11))) returns 8. |
push(a,B) |
If a is an object belonging to a domain A and there is a natural map A → B to a domain B, this function returns the image of a in B. Example. push(19, Zn(11)) yields 8 :: Z11. |
pull(a) |
If a is an object belonging to a domain A, a :: A, it returns the same element a with type a :: A' where A' is the minimum subdomain of A containing a. For example, if F9 = extension(Zn(3),[1,0,1]) and a = (2 >> F9), so that a :: F9, pull(a) returns 2 :: Zn(3). |
cardinal(A) |
Returns the cardinal of the object A. For example, cardinal(ZZ()) ⇒ 'Infinity', while cardinal(Zn(25)) ⇒ 25. |
a2b(a,b) a2b(a,b,d) |
To get a list of all the integers not less than a
and not higher than b,
a, b integers,
use a2b(a,b).
Its definition is list(range(a,b+1)).
If we supply the third parameter d, also an integer,
we get list(range(a,b+1,d)) if
b+1 > a and list(range(a,b-1,d))
otherwise.
Examples: |
rd_selection(X,k=1) combination(n,k=1) permutation(n) |
Assuming that X is a list,
rd_selection(X,k)
selects k distinct elements of X
and creates a list with them. The expression combination(n,k)
is defined as the sorted list delivered by rd_selection(list(range(n)), k).
If k is not supplied, it is set to k = 1.
Finally, permutation(n) is defined as
rd_selection(list(range(n)), n).
rd_selection = rd_choice = rd_sample (Cf. Random resources).
Examples: |
binom(n,k) binomial = binom |
The value of the expression is
\(\binom{n}{k}\).
Example: |
In the remaining function calls in this section, those with two parameters
(n and d)
are defined as the function calls of the same name with parameters
n, d and
q = 2.
In other words, if
q is not supplied, its value is set to
2.
For example,
volume (n, r) = volume (n, r, 2).
volume (n, r, q) volume (n, r) |
The cardinal of the Hamming ball of radius r in the q-ary Hamming space of length n ( Fn, with |F| = q). |
ub_singleton (n, d, q) ub_singleton (n, d) |
The Singleton upper bound on M for codes (n,M,d)q. |
ub_sphere (n, d, q) ub_sphere (n, d) |
The sphere (or Hamming) upper bound on M for codes (n,M,d)q. |
lb_gilbert (n, d, q) lb_gilbert (n, d) |
The Gilbert lower bound on M for codes (n,M,d)q. |
lb_gilbert_varshamov (n, d, q) lb_gilbert_varshamov (n, d) |
The Gilbert-Varshamov lower bound on M for codes (n,M,d)q. |
even(n) odd(n) remainder(n,m) |
For any integer n, those expressions do what is expected of them: the value of even(n) is True if n is even and False if n is odd. The expression odd(n) works the other way around. Since these functions can be (and are) defined in terms of the remainder expression n % 2, the justification for including them is that they make code more readable. The same is true of remainder(n,m), which is defined as n % m. |
dlen(n) blen(n) |
These expresions deliver the number of decimal and binary digits of the positive integer n. |
convert(n,b) hohner(D,b) |
If n is an integer ≥ 2,
convert(n,b)
returns the list of digits of the positive integer
n relative to the base b.
To get the integer
n
whose list of digits in the base b
is D, we have
hohner(D,b) (the name points to the
well known generating rule used to find n).
Examples: |
factorial(n) |
Computes n!
Examples: |
fib(N) fibonacci = fib |
Delivers the Nth Fibonacci number.
Examples: |
igcd(m,n) ilcm(m,n) |
The expression igcd(m,n)
yields the greatest common divisor
of the positive integers m
and n. Similarly, their
least common multiple is supplied by the expression
ilcm(m,n).
Both functions can be applied to a sequence of any number of integers.
The names gcd and lcm
can also be used, but they are resolved, when the parameters are integers,
by calling igcd and ilcm.
Examples: |
extended_euclidean_algorithm(m, n) |
Given integera m and n,
this function returns a triple (x,y,d) of integers such that
d = igcd(m,n)
and d = x m +y n.
Example: |
rabin_miller(n, k=25) strong_probable_prime(n,a) strong_pseudo_prime(n,a) |
This function implements the Rabin-Miller primality test on the integer
n. If it returns False,
then n is composite. Otherwise it is
prime with very high probability (not less than
p=1-1/4k, which for the default
iteration number k = 25 is
p = 0.9999999999999991).
The Rabin-Miller test uses the function
strong_probable_prime(n,a)
that tells wheter an odd integer n
is a strong probable prime to the base a
(cf. Crandall-Pomerance-2005, Algorithm 3.5.2), and
strong_pseudo_prime(n,a)
tests whether n is a strong probable prime base
a but not prime.
Examples: |
is_prime(n) is_prime_power(n) is_perfect_power(n) is_square(n) |
For a positive integer n,
is_prime(n) is true if n
is prime and false otherwise. By default, the test is based on the rabin_miller
method. We can call is_prime(n,method='BPSW') or
is_prime(n,method='miller'), which are equivalent to
BPSW(n) and miller(n),
respectively (these functions are described later in this section).
Similarly,
is_prime_power(n)
is true if and only if n is a power
of a prime number. Finally, for an odd integer n > 1,
the expression is_perfect_power(n)
produces a pair of integers (x,p) with the following
properties: If n is not a perfect power,
this pair is equal to (n,1), and otherwise
p is prime and n = xp.
Although this function is very fast, its complete analysis is a bit involved and we refer to the note
X180630 for details and references. An interesting exercise
is to use it to produce a faster version of is_prime_power(n).
Finally, the function is_square(n) decides whether
the positive integer n is a perfect square.
Example: The following expression computes the list of all odd prime powers less than 1000 but excluding those that are prime numbers:
[x for x in range(3,1000,2) if is_prime_power(x) and not is_prime(x)] Other examples: is_perfect_power(2347**421) ⇒ (2347,421) is_perfect_power(2347**421 * 421**2347) ⇒ (n,1) Note. dlen(2347**421 * 421**2347) ⇒ 7579, so n has 7579 decimal digits. |
primes_less_than(n) |
Delivers the list of prime numbers that are less than the integer n.
Example: |
next_q (n) next_prime(n) next_p = next_prime |
For any positive integer n,
the first expression gives the first prime power
≥ n. Similarly,
the second expression gives the first prime
≥ n. Since there are more prime powers than primes,
we have next_q(x) ≤ next_p(x)
Examples: Note that 3**7 = 2187 |
pollard(n) |
If n is composite, this function attemps to find
a non-trivial factor of n. It is the basis for the factoring
function ifactor(n).
Examples: |
ifactor(n) prime_factors(n) |
The function ifactor(n) computes the prime factorization
\(p_{1}^{e_{1}}p_{1}^{e_{1}}\cdots \) of
a positive integer n
in the form of a table: \(\{p_1:e_1, p_2:e_2,\dotsc\}\).
Examples: |
divisors(n) tau(n) sigma(n) |
For a positive integer n, the first expression supplies
the list of positive divisors of n in increasing order.
The number of such divisors is given by tau(n) and
their sum by sigma(n).
Example: |
phi_euler(n) lambda_carmichael(n) |
Computes Euler's totient function of a positive integer n,
which is the number of integers in 1,2, ..., n-1
that are coprime to n, or, in other words,
the order of the multiplicative group
\(Z_n^*\)
of invertible elements of \(Z_n\).
In terms of a factorization
\(n=\prod p_{\alpha}^{e_{\alpha}},\)
its value is \(\prod p_{\alpha}^{e_{\alpha}-1}(p_{\alpha}-1)\).
The Carmichael \(\lambda\)-function of n
(see Yan-2002, Definition 1.4.7).
Example:
The last two examples reproduce Example 1.4.7 and Example 1.4.8 in Yan-2002.
|
mu_moebius(n) |
If \(n=\prod p_{\alpha}^{e_{\alpha}}\) is the prime factorization of
\(n\),
mu_moebius(n) is 0 if there is at least one exponent
\(e_{\alpha}\) greter than 1. Otherwise it is
\(\pm1\),
,
where the sign is \(+\) (\(-\))
if the number of prime divisors of \(n\)
is even (odd).
Examples: |
is_square_free_n(x) |
For a positive integer x, it returns True
if it is not divisible by any perfect square greater than 1. Equivalenty, x
is not divisible by the square of any prime, or also
mu_moebius(x) ≠ 0.
There is a similar function is_square_free(f) that is specific for univariate polynomials
f. The separation of the two makes the computation of either much more
efficient.
Examples: |
lucas_number(P,Q,x0,x1,N) lucas_chain_V(P,Q,m,n) lucas_U(P,Q,N) lucas_V(P,Q,N) lucas(N) pell(N) pell_lucas(N) jacobsthal(N) jacobsthal_lucas(N) mersenne(N) |
The main function of this group is
lucas_number(P,Q,x0,x1,N),
where the parameters are integers, N non-negative.
It returns the N-th Lucas number of the Lucas
sequence associated to P, Q, x0, x1. In
PyECC it is defined as follows:
def lucas_number(P,Q,x0,x1,N): if N==0: return x0 if N==1: return x1 for _ in range(2,N+1): x0, x1 = x1, P*x1-Q*x0 return x1The function lucas_chain_V(P,Q,m,n) is a variation of the function just described which is used in the BPSW test of primatlity and is implemented as follows (cf. Crandall-Pomerance-2005, Algorithm 3.6.7): def lucas_chain_V(P,Q,m,n): mb = bin(m)[2:] # the binary string representing m v0 = 2; v1 = P j = 0 for b in mb: Qj = power(Q,j,n) if b == '1': v0,v1 = (v0*v1)%n-(Qj*P)%n, (v1**2-2*Qj*Q)%n else: v0,v1 = (v0**2-2*Qj)%n,(v0*v1)%n-(Qj*P)%n j = 2*j+int(b) return (v0,v1)The other numbers are defined as follows:
Examples: |
baillie-pomerance-selfridge-wagstaff(n) BPSW = baillie-pomerance-selfridge-wagstaff |
This implements the primality test of Baillie, Pomerance, Selfridge, and Wagstaff, as
explained in Crandal-Pomerance-2005, Algorithm 3.6.9.
Examples:
n = 1000000000000000000000000000000000000000000000000000000000007 |
miller(n) |
For an odd number n > 1, this function implements
Miller's primality test (Crandall-Pomerance-2005, Algoritm 3.5.13). If it returns
False, then n
is composite. Otherwise, n is prime or the
GRH is false.
Examples: |
lucas_lehmer(n) LL = lucas_lehmer |
An implementation of the Lucas-Lehmer test
(Crandall-Pomerance-2005, Algorithm 4.2.98697)
to decide whether the n-th
Mersenne number 2n-1 is prime or not.
Example: The first two lines of this example show that 29869-1 is not a Mersenne prime, contrary to its presence on Table 1.2 of Crandall-Pomerance-2005 (p. 23). With a little more work we find that the exponent has been misprinted: it should be 9689. |
continuous_fraction(x,n) |
If x is a positive real number,
this funtion returns the n-term continuous fraction of x
in the form of a list [f0, f1, ..., fn-1], so that
setting x0 = x we have
f0 = floor(x0) and then,
for j = 1, ..., n-1,
fj = floor(xj) with
xj = 1/(xj-1 - fj-1).
Si xj-1 - fj-1 = 0, la iteració s'atura i la funció retorna
[f0, f1, ..., fj-1].
Example: |
continuous_fraction_value(F) |
If F is a
list of positive integers, this function computes the rational number corresponding to F
regarded as a continuous fraction.
Exampe: |
dec2bin(x, nb = 58) bin2dec(xb) |
Let x be a real number,
x ϵ [0,1].
The function dec2bin(x, nb)
returns the binary expansion of
x up to nb bits.
The default value of nb is 58,
which encompasses the machine precesion of Python floats.
Conversely, bin2dec(xb) converts a string of
bits into a real number in the interval [0,1] by interpreting
that the kth bit b contributes with
b/2k.
Examples: |
floor(x) frac(x) |
If x is a real number, floor(x) is the greatest
integer ≤ x. In mathematics, it is often denoted
⌊x⌋.
Examples: The function frac(x) yields the fractional or decimal part of the real number x, that is, x − floor(x). |
ceiling(x) qceiling(n,m) |
If x is a real number, ceiling(x) is the least
integer ≥ x.
Since it relies on the Pyhton double precesion floats, it is not indicated when higher precesion is needed.
An alternative is qceiling(n,m), n and
m integers, m ≠ 0,
which returns the (exact) ceiling of the rational number n/m.
Examples: |
order(k, n) |
If
gcd(k,n) = 1, the order of
k in Zn*.
Examples:
order(2,9) ⇒ 6 |
inverse(k,n) |
If gcd(k,n) = 1,
inverse(k,n) computes
a positive integer k'
such that k' < n
and k'k ≡ 1 mod n.
Example: |
mult(n,k,b) bpow(n,k,b) quot(n.k,b) power(n,k,m) |
The value of these expressions
is n · k mod 2b,
nk mod 2b
and (m / k) mod 2b, respectively.
In the latter case, k has to be odd.
The function bpow(n,k,b) coincides with
bpow(n,k,2b), as
power(n,k,m) computes
nk mod m.
These functions are used, for example, in the definition of the next two.
Examples: |
jacobi(a,n) legendre(a,n) |
Computes the Jacobi symbol (a/n) of two integers a and n, which must be odd and positive. The PyECC implementation is based on Algorithm 2.3.5 of Crandall-Pomerance-2005. If n is prime, it coincides with the Legendre symbol (a/n), which is 0 if a is divisible by n and otherwise it is +1 or -1 according to whether a is or is not a quadratic residue mod n. It coincides with legendre(a,Zn) defined in Finite rings and fields. |
nroot(n,k,b) sqroot(n,b) |
If n is an odd integer and k
is either odd or 2,
nroot(n,k,b) computes an integer
r < 2b such that
rkn ≡ 1 mod 2b,
which is a kth root of
n-1 mod 2b.
The function sqroot(n,b) is equivalent to
nroot(n,2,b).
These funtions are used in the definition of is_perfect_power(n).
Examples: |
cyclotomic_class (k, n, q) cyclotomic_class (k, n) |
Assuming that
q and n
are positive integers and that
gcd(q,n)=1,
the call
cyclotomic_class(k,n,q) supplies the
q-cyclotomic class of
k mod n, which by definition is the list
[k, q·k,q2·k,...,qr−1·k],
where the operations are done mod
n and
r is the least positive integer such that
qr·k=1.
The call cyclotomic_class(k,n) is defined as cyclotomic_class(k,n,2).
Examples: |
cycloctomic_classes (n, q) cycloctomic_classes (n) |
Assuming that
q and n
are positive integers and that
gcd(q,n)=1,
the function
cycloctomic_classes(n,q)
furnishes the list of all the q-cyclotomic
classes mod n. Finally,
cycloctomic_classes(n) is defined as
cycloctomic_classes(n,2).
Examples: |
vector = row_vector = create_vector vector(X), vector(K,X) col_vector(X) = vector(X,'c'), col_vector(K, X) = vector(K,X,'c') |
The function vector(X) transforms a list X to a Vector. If a field or ring K is supplied as a the first parameter, the elements of X are pushed to elements of it. The parameter 'c' is to indicate that the constructed vector be a column vector. |
eps(n,j) eps(m,n,j,k) |
If n is a positive integer and
0≤j<n,
eps(n,j) is the length n
list whose j-th entry is 1 and all other
entries are 0. If j
is out of the indicated range, eps(n,j) is the length
n list whose entries are all 0.
Similarly, given positive integers m
and n, and integers j
and k such that
0≤j<m and
0≤k<n,
eps(m,n,j,k) creates
an m × n matrix with all entries 0
except 1 in the (i,j) entry.
If either j or k
is not in the stated range, the call returns the m × n null matrix.
Examples: |
vector_append(x,a) |
If x is a vector, this function is equivalent to vector(list(X)+[a]) |
reverse(x) |
If x is a list and its length is n, this expression yields [ x[j] for j in range(n-1,0,-1) ]. If x is a vector, it returns vector[reverse(list(x))]. |
support(x) pattern(x) |
If x is a list or vector, support(x) yields the list of the indices i in the range of x such that xi≠0. The function pattern(x) returns a pair (s,v), with s = support(x) and v = vector([x[j] for j in s]) |
error_vector(n,E) |
wt(x) hd (x,y) |
If x is a list or vector, wt(x) is equivalent to len(support(x)). If y is another list or vector of the same length as x, hd(x,y) supplies the Hamming distance between x and y, which by definition is the cardinal of the set of indices j in the range of the lists/vectors such that xj ≠ yj. If both x and y are vectors, it is equivalent to wt(x-y). |
convolution(a,b,k) convolution(a,b) |
If a and b are vectors or lists and k is an integer, this function returns the k-th coefficient of the convolution of a and b, namely the sum of the terms aj·bk-j for j = 0,...,k, with the conention that aj=0 if j≥len(x) and bk-j=0 if k-j≥len(b). Thus convolution(a,b,k) = 0 if k<0 or k≥len(a)+len(b). If a and b are lists, convolution(a,b) is the list [convolution(a,b,k) for k in range(n)], where n=len(a)+len(b)−1. For vectors, convolution(a,b) is equivalent to vector(convolution(list(a),list(b))). |
coeffs (p) |
If p is a polynomial, coeffs(p) gives the list of its coefficients, from highest to lowest degree. The multivariate polynomials are considered as univariate polynomials in the last variable with coefficients in the polynomial ring of the previous variables. |
geometric_series (x, n, s0) geometric_series (x, n) |
The first call produces the vector [s0,s0·x,...,s0·xn−1]. The second is defined as geometric_series(x,n,1), which therefore supplies the vector [1, x,...,xn−1]. |
flip(x) flip(x,k) |
The first form transforms a list or a vector x
into the list or vector whose components are 1-x[j],
j in the range of x.
For a binary list or vector, it concides with the result of swaping 0
and 1 (this explains the name
given to the function). In the second form, k may
be an index in the range ofx, or a list/tuple/set of such
indices and only the kth component, or the components
with index in k, undergo the trasformation
1-x[j].
Examples: |
invert_entries (a) |
If a is a vector with no zero entries, the vector [1/a1,...,1/an]. |
prod (x, y) dot (x, y) |
If x and y are lists or vectors of the same length n, prod(x, y) constructs the vector [ x1·y1,...,xn·yn] and dot(x, y) yields the sum x1·y1+···+xn·yn |
[B,X] = polynomial_ring(A, 'T') [B,X] = polynomial_ring(A, 'T', 'R') [B,X] = polynomial_ring(A) |
If A is a ring, and B, X are identifiers, this assignement binds B to the polynomial ring A[T] and binds X to the variable T (a particular element of A[T]). For example, in the assignement [B,X] = polynomial_ring( ZZ(), 'T'), B and X are bound to Z[T] and T, respectively. If we supply the third paramente 'R', then all works in the same way except that the (diplayed) name of A[T] is R. If only the first argument is provided, then the second and third paramenters are set to 'X' and 'A[X]'. For example, the statement [P,U] = polynomial_ring( ZZ() ), P is bound to Z[X] and U to X. |
generator(A) |
hohner(A,x) |
If [a0,a0,...,an] is a list of elements of a ring, this function returns the evaluation of a0xn+a1xn-1 + ··· + an-1x + an. |
cyclotomic_polynomial(n, A = ZZ()) |
polynomial(A,x) |
If [a0,a0,...,an] is a list of elements of a ring, this function returns the evaluation of a0 + a1x + ··· + an xn . |
[R,X,Y] = bivariate_polynomial_ring(A,'S', 'T', 'P') [R,X,Y] = bivariate_polynomial_ring(A,'S', 'T') [R,X,Y] = bivariate_polynomial_ring(A) [R,X,Y] = bivariate_polynomial_ring(A,name='P') |
Creates the bivariate polynomial ring P = A[S,T], with P assigned to the variable R and S, T assigned to the variables X, Y. If 'P' is omitted, the default name is A[S,T]. If 'S' and 'T' are also omitted, the default name of the ring is A[x,y] and the names of the variables are x,y. In the last call, the name of the polynomial ring is set to P. |
[R,X1,...,Xr] = multivariate_polynomial_ring(A,'T1',...,'Tr',name='P') [R,X1,...,Xr] = multivariate_polynomial_ring(A,'T1',...,'Tr') PR = multivariate_polynomial_ring |
For r > 1, this function creates the r-variable polynomial ring P = A[T1,...,Tr], with P assigned to the variable R and T1,..., Tr assigned to the variables X1,...,Xr. If we omit the last parameter (if present, the syntax "name = 'P'" is compulsory), the default name of the polynomial ring is A[T1,...,Tr]. In all cases, the number of variables Xi has to agree with the number of symbols 'Ti'. Instead of the sequence 'T1',...,'Tr' of symbols for the indeterminates, we can supply its list ['T1',...,'Tr'], say as in multivariate_polynomial_ring(A,V,name='P') with V = ['T1',...,'Tr'], in which case the structure of the output is [R,X], where X stands for the list [X1,...,Xr]. |
variable(f) variables(f) |
If f is a univariate polynomial, variable(f) returns its variable symbol. In the case of a multivariate polynomial f, variables(f) yields the list of the variable symbols, even when f is univariate, and variable(f) the last variable symbol 'Tr'. This behaviour is explained by the fact a multivariable polynomial is seen as an univariate polynomial in the the last variable with coefficients in the multivariate polynomials in the preceding variables. |
trailing_degree(f) |
derivative(f) |
partial_derivative(f,x) pder = partial_derivative |
coeffs(f) |
Given an univariate polynomial f = a0xn+a1xn-1 + ··· + an-1x + an, coeffs(f) returns the list [a0, a1,..., an]. Cf. the function hohner(A,x). |
quo_rem(r0,r1) |
sugiyama(r0,r1,t) |
get_subpolynomial_degree(f,d) |
degree(f) mdegree(f) |
skeleton(f) |
evaluate(f,a1,...,ar) evaluate(f,p) |
find_roots(f,K) find_roots(f) roots = find_roots |
If K is a finite field that contains the coefficients of the univariate polynomial f, the first call finds the roots of f in K. If K is not supplied, it defaults to the minimum field that contains the coefficients of f. |
zero_positions(f,a) |
get_irreducible-polynomial(K,r,symbol='X') |
distinct_degree_factoring(f,K) DDF = distinct_degree_factoring |
equal_degree_splitting(f,r) EDS = equal_degree_factoring |
equal_degree_factoring(f,r) EDF = equal_degree_factoring |
merge(A,B) |
power_series(s,symbol='T',point=0,n=3) |
Zn(n) |
If n is an integer >1, this function constructs the ring Zn. If A=Zn(n), and k is any integer, the expression k>>A yields the value k mod n. |
[B,b]= extension (A, f(T), 'a') [B,b]=extension (A, [1,c1,...,cr], 'a') base(B) prime_field(F) |
If
A is a ring,
f(T) a monic polynomial with coefficients in A,
and a is an identifier, then the first statement binds B and
b to the quotient A[T] / ( f(T) ) and to the class of
T modulo f(T), which is named a
(or x if 'a' is not supplied).
The second statement is equivalent to the first when
f(T) = Tr + c1Tr-1 +···+ cr.
The ring A can be recovered from B with the command base(B). The elements 1, a, a2, ..., ar-1 form a linear free basis of B over A which is called the natural or standard basis. If A is a field and f(T) is irreducible over A, then B is a field of degree r over A. The minimum subfield of a finite field F can be obtained with prime_field(F) (it is Zn(p), where p is the characteristic of F). |
K_(a) |
If the domain of an object a is a ring (which may be a field), this function returns A :: Ring (or A :: Field). Examples: K_(5) returns ZZ :: Ring, K_(1/5) returns QQ :: Field. |
generator(A) |
md_power(f,n,g) |
md_double_power(f,m,n,g) |
md_mult(f,g,h) |
period(a) order(a) period(f) exponent = period |
For a a non-zero element of a finite field, the call period(a) delivers the minimum positive integer r such that ar = 1, which coincides with order(a). If f is an univariate polynomial with variable x with coefficints in a finite field, period(f) yields the minimum positive integer r such that xr = 1 mod f. |
legendre (x, F) QR(F) QNR(F) |
If
x
is a non-zero element of the finite field
F
of characteristic
≠ 2,
legendre(x,F)
retuns 1
if x
is quadratic residue in
F and
−1 otherwise.
By convention, legendre(0) is 0.
For x ≠ 0,
legendre(x,F) coincides with
(−1)(q−1)/2, where
q is the cardinal of
F.
QR(F) yields the list of the non-zero quadratic residues of F. Similary, QNR(F) yields the list of the quadratic non-residues of F.
|
is_irreducible(f) is_irreducible(f,K) |
get_irreducible-polynomial(K,r,symbol='X') |
matrix(A,m,n) |
This creates the m × n null matrix
with entries in the ring A.
If M = matrix(A,m,n), M
can be populated by expressions of the form M[j,k] = a,
where a is an element of A.
Examples: |
ncols(M) nrows(M) shape(M) |
If M is an m × n matrix, we get m with nrows(M), nvwith ncols(M), and the pair (m,n) with shape(M). |
I_(n,A) I_(n) |
The identity matrix of order n with entries in the ring
A is obtained with the expression
I_(n,A). If A
is not given, by default it is taken to be the binary field
Z2.
Examples:
I_(3, Zn(8)) ⇒
|
submatrix (A,J) |
If A is a matrix and
J is any sequence in range(ncols(A)),
submatrix(A,J) constructs the matrix whose colums are
the columns A_j for j\(\in\)J.
Examples: [[1 2 3 4 5 6] [1 4 9 16 25 36] [1 8 27 64 125 216]] :: Matrix[Z]submatrix(A,[0,2,4]) ⇒ [[1 3 5] [1 9 25] [1 27 125]] :: Matrix[Z] |
permutation_matrix(p) |
If p is a permutation of
0, 1, ..., n-1, this function creates the
n × n matrix that has 0 everywhere, except
at the entries (j,p[j]) that are set to 1. There is a version
rd_permutation_matrix(n) that selects p
at random and returns permutation_matrix(p) (see
Random resouces).
Example:
permutation_matrix([2,1,0]) ⇒
|
splice(A,B) stack(A,B) |
If A and B
are matrices and nrows(A) = nrows(B), then
splice(A,B) is the matrix A|B
obtained by appending each row of B to the corresponding
row of A. The expression stack(A,B)
is defined when ncols(A) = ncols(B) and it appends the rows of
B to the rows of A.
Examples:
A = I_(2,Z_); B = permutation_matrix([1,0])
splice(A,B) ⇒
|
transpose(M) |
If M is a matrix, with this expresion we get the transpose of M. |
row_index(h,H) col_index(h',H) |
Let H be an m × n matrix. If h is one of the rows of H, row_index(h,H) gives de index of h in H (seen as a list of vectors). If h is not a row of H, the returned value is [ ]. The expression col_index(h',H) works similarly for a column h' of H. |
rank(M) |
This expression yields the rank of a matrix M with entries in a field. It agrees with the dimension of the space spanned by the rows of M. |
det(M) trace(M) |
If M is a square matrix, these expressions deliver the determinant and the trace of M, respectively. |
kernel(H) left_kernel(H) right_kernel(H) |
Let H be an m × n matrix with entries in a field F. The expression kernel(H) returns an n × k matrix whose columns form a basis of the space of column vectors x of length n such that Hx = 0. This is also called the right_kernel(H). The space of row vectors x of length m such that xH = 0 is obtained by the function left_kernel(H), which produces an r × m matrix whose rows form a basis of left_kernel |
hankel_matrix(s) |
Given a list or vector S, this function
constructs the square Hankel matrix H associated to
S, which is defined by
H[j,k] = S[i+j] for
0 ≤ i, j < (l+1)//2, l = len(S).
Examples:
S = a2b(1,4); hankel_matrix(S) ⇒
S = a2b(1,5); hankel_matrix(S) ⇒
|
parity_completion (G) left_parity_completion (G) |
If
G is a
k × n
matrix, it adds to the right of
G the colum formed by the negatives of the sums
of the rows of
G. Thus the sum of every row of the matrix so
obtained is 0.
left_parity_completion(G) works as parity_completion(G), but with the extra column placed on the left of G.
|
paley_matrix (F) |
If
F
is a finite field of
q
elements, q odd,
paley_matrix(F)
yields the
q × q
matrix
(legendre(xi−xj)),
where
x0,...,xq−1
are the elements of
F in some order.
|
vandermonde (a, r) |
If
a
is a vector,
vandermonde(a,r)
produces the vandermonde matrix of
r rows associated to
a.
|
cyclic_matrix (g, n) cyclic_normalized_matrix (g, n) |
If g
is a monic univariate polynomial of degree
n−k > 0 dividing
Xn−1,
or its vector of coefficents,
cyclic_matrix(g,n)
yields the standard generating matrix of the cyclic code
Cg.
cyclic_normalized_matrix(g,n) works like cyclic_matrix(g,n), but the returned matrix is the normalized generating matrix of the cyclic code Cg.
|
cyclic_control_matrix (g,n) cyclic_normalized_control_matrix (g, n) |
If
h
is a monic univariate polynomial of degree
k > 0
dividing
Xn−1,
or its vector of coefficents,
cyclic_control_matrix(g,n)
yields the standard control
matrix of the cyclic code Cg,
g = (Xn−1) / h.
cyclic_normalized_control_matrix(g,n) is the standard control matrix associated to cyclic_normalized_matrix(g,n).
|
components (x, F) blow (h, F) |
If
F
is a finite field and
x
an element of
F,
components(x,F) is
the vector of components of
x
with respect to the standard basis of
F over base(F)
(see extension in
Finite rings and fields).
If F is a finite field and h ∈ Fn, blow(h,F) delivers the vector obtained by replacing each element of h by the sequence of its components with respect to the standard basis of F over base(F).
|
blow (H, F) prune (H, F) |
If F
is a finite field and
H
is an
r×n
matrix with entries in
F,
blow(H,F)
copnstructs the matrix obtained by replacing each entry of
H
by the column of its components with respect to the standard basis of
F
over base(F).
If H is any matrix, prune(H) eliminates each row of H that is a linear combination of the preceding ones.
|
alternant_matrix (h, a, r) alternant_matrix (P ,A) |
The call alternant_matrix (h, a, r) privides
the alternant control matrix of order
r associated to the vectors
h and
a.
The call
alternant_matrix(P,A), where
P=[p1, ..., pr]
is assumed to be a vector of univariate polynomials
and A=[a1, ..., an]
a vector, constructs the matrix
(pi(aj)), or
|
A (block error-correcting) code is represented by a table-like structure
C that contains
the relevant data of the code. For example, for an alternant code
the table entries have the labels
h_,
a_,
r_,
b_ and
H_,
and optionally
K_ or
G_ or both.
The values of these fields are, respectively, the vector
h, the
vector
a, the order
r, the vector
b of the reciprocals
of the elements of
a, the alternant control matrix
H associated to
h,
a and
r,
and, when present, the base field
K and a generating matrix
G. The trick of
appending the underscore character to the table field labels produces names
that are unlikely to be used as identifiers elsewhere and yet that are
mnemonic of the meaning of their values. To extrat the value of a field,
say a_,
we form the expression
a_(C) or
C.a_.
alternant_code (h, a, r) alternant_code (h, a, r, K) |
If h and a are vectors of the same length, say n, with entries in a finite field F and r is a positive integer such that r ≤ n, alternant_code(h,a,r) constructs the alternant code AK(h,a,r) associated to h, a and r over a ground field K that is assumed to be known from the context (usually K = base(F), the field out of which F has been constructed). The call alternant_code(h,a,r,K), where K is a subfield of F, is defined to be C = alternant_code(h,a,r) together with the setting C.K_ = K |
BCH (a, d, l) BCH (a, d, l, K) BCH (a, d) BCH (a, d, K) |
If a is a non-zero element of a finite field F, d > 0 an integer such that d < n = period(a), BCH(a,d,l) is defined as alternant(h,a,d-1), where h = geometric_series(al,n) and a = geometric_series(a,n). This code is the BCH code of length n = period(a), design distance d and offset l. On the other hand, BCH(a,d) = BCH(a,d,1), which is called the strict BCH code of length n = period(a) and design distance d. Finally BCH(a,d,l,K) is equivalent to BCH(a,d,l).K_= K. |
RS (a, k) PRS (F, r) |
Given a finite field
K, a vector
a ∈ Kn,
RS(a,k) is
C = alternant_code(h,a,n-k)
extended with the assignements C.G_ = vandermonde(a,k)
and C.K_ = field(a), where
h is the vector in
Kn such that
hi = 1 / Πj≠i
(ai - aj).
Note that its generating matrix is included in the data of the code,
and also the base field
K (since it can be inferred from the vector
a, it is not
necessary to include it as parameter of the function
RS).
If F is a finite field, q its cardinal, ω a primitive element of F, n = q−1 = period(ω), andr a non-negative integer ≤ n, then PRS(F,r) = BCH(ω, r+1, F), which is the RS code of dimention n − r on the vector of non-zero elements of F. |
GRS(h,a,k) |
Let h and a are vectors of the same length n over a field a finite field F and assume that the components of a are pairwise distinct and those of h are all non-zero. Then the code constructed with GRS(h,a,k) is equivalent to alternant_code(h,a,n-k,F). Note that if all components of h are one, then RS(a,k). |
goppa(g,a) Goppa = Goppa_Classic_Code = goppa |
The parameters of this funtion are a list or vector a of elements of a finite field F = K[x] that is a simple extension of K and a polynomial g ε F[T] such that g(t) ≠ 0 for any component t of a. Then the definition of goppa(g,a) is equivalent to alternant_code(h,a,r,K), where h is the vector [1/g(t) for t in a] and r is the degree of g. |
alternant_decoder (y, C) BMS(y,C) sugiyama (r0, r1, t) |
If C is an alternant code and y is the received vector, alternant_decoder (y,C) delivers the C-decoding of y according to the Berlekamp-Massey-Sugiyama algorithm. The name BMS is a synonym of alternant_decoder. The function sugiyama (r0, r1, t) is a key subroutine of the BMS decoder and works as follows. Given non-zero univariate polynomials r0 and r1 in the variable z such that 0 < deg(r1) ≤ deg(r0), and an integer t such that t ≤ deg(r1), sugiyama returns a pair [v,r] of univariate polynomials in z such that r ≡ v·r1 mod r0 and deg(r) < t. |
PGZ(y,C) PGZm(y,C) |
If C is an alternant code (see Code constructors) and y is the received vector, then both PGZ(y,C) and PGZm(y,C) deliver the C-decoding of y according to the Peterson-Gorenstein-Zierler algorithm. They share the same error-location scheme, but differ in the error evaluation: PGZ uses a variation of Forney's formula and PGZm uses linear algebra. For the foundation of the improvements provided by the PyECC implementations, see 2017-Farre-Sayols-Xambo. |
RSID (a, k, y) |
For RS codes, there is an interesting decoder based on polynomial interpolation.
Since it only needs the vector α
and the dimension k, it can be implemented as a function
RSID(a,k,y), where a stands for
the vector α and y
for the received vector. The PyECC
implementation is based on the following scheme. Let n = len(a)
and t = (n − k) // 2. Then there are polynomials
P = p0 + p1 T
+ ··· + pn-t-1 Tn-t-1
and
Q = q0 + q1 T
+ ··· + qn-t-k Tn-t-k,
not both zero, such that
P(aj) + yjQ(aj) = 0
for j = 0, ..., n-1 (these
conditions amount to a system of n linear homogeneous
equations in the n-t + n-k-t+1 = n - k -2t +n+1 > n
unknowns p0, ...,
pn-t-1, q0, ..., qn-t-k).
Let x and e be the sent
and error vectors, respectively, so that y = x + e.
By definition of the RS codes, there is a well-defined polynomial
f(T) ∈ F[T]k, where F
is the finite field in which the aj have been chosen
and F[T]k is the space of polynomials
with coefficients in F of degre < k, such that
xj = f(aj). Therefore we have the
relations P(aj) +
(f(aj) + ej) Q(aj) = 0
for j = 0, ..., n-1. This implies that the
polynomial g(T) = P(T) + f(T) Q(T)
vanishes for all aj such that
ej = 0. Since g(T)
has degree < n − t, we conclude that
g(T) = 0 if the number n − |e| ≥ n − t ,
that is, if |e| ≤ t. Under this assumption we conclude that we
can recover f(T), and hence x,
as f(T) = - P(T) / Q(T).
|
hadamard_decoder (y, H) |
If H is a Hadamard matrix of order n and y is a binary vector of length n, the function decodes y with respect to the Hadamard code associated with H. |
meggitt (y, g, E) |
Given the Meggitt table
E for the cyclic code of length
n over a finite field
K generated by the monic polynomial
g, and a vector
y ∈ Kn, this function decodes
y according to Meggitt algorithm.
|
rd_linear_combination (G, K) |
If G is matrix and K is a field (or a ring), rd_linear_combination(G, K) returns a linear combination of the rows of G with coefficients randomly chosen in K. |
rd_error_vector (K, n, s) rd_error_vector (K, s) |
If n and s are positive intgers, s≤n, and K is a field (or a ring), rd_error_vector(K, n, s) produces a vector in Kn of weight s whose non-zero positions and the corresponding values have been chosen randomly. The function rd_error_vector(K, s) is defined as rd_error_vector(K, q-1,s), where q is the cardinal of K. |
decoder_trial (C, s, K) |
If C is an alternant code (let n be its length) defined over the finite field K and s ≤ n a positive integer, decoder_trial(C,s,K) first generates a random vector x of C and a random error pattern e in Kn of weight s, then finds the value x* = alternant_decoder(x + e, C) and presents [x, e, x+e] if x* = x (correct decoding), [x, e, x+e, x*] if x* is a vector ≠ x (undetectable error), and [x, e] if x* is not a vector (decoder error). If the field K is included in the data of C, then we can use decoder_trial(C, s) instead, as this call is defined to be decoder_trial( C, s, K_(C)). |
rd_gauss(\(\mu=0,\sigma=1\)) |
Delivers a real number drawn according to the
Gauss normal distribution
\[
f(x|\mu,\sigma)=
\frac{1}{\sqrt{2\pi}\sigma}
e^{-\frac12\left(\frac{x-\mu}{\sigma}\right)^2}
\]
of mean \(\mu\) and standard deviation \(\sigma\), with default values 0 and 1, respectively.
Examples: |
rd_int(a,b) ri(d) rd_prime(d=5) |
Assuming that a and b
are integers, the expression rd_int(a,b)
chooses an integer uniformly at random in the interval
[a,b]. A special version is the function
ri(d) that chooses uniformly at random
a d-digit integer.
To get a random prime number of d
digits, with default d=5, call rd_prime(d).
Actually it yields the first prime number that is \(\ge\) of the random integer x = ri(d), so it will have
d+1 digits if there is no primer number in the interval \([x,10^d]\).
The function can be easily modified to avoid this possibility: if dlen(next_prime(x))>d, start
all over again.
Examples: |
rd_choice (X, m=1) rd_choice (n, m=1) rd_permutation(n) rd_choice = rd_sample = rd_selection rd_permutation = permutation |
If X is a list or a vector and
m is a positive integer, not greater than the length of
X,
rd_choice (X, m)
returns a list or a vector of m distinct
elements of X selected at random. It defaults to m = 1
if m is not supplied:
rd_choice (X) = rd_choice (X, 1) .
If n and m are positive integers with m ≤ n, rd_choice (n, m) is defined as rd_choice (range(n), m). Thus it returns a list of m distinct integers chosen at random in 0..(n-1). The function rd_permutation(n) is defined as rd_choice(n,n) and hence it yields a random permutation of [0,1,...,n-1]. Examples: rd_choice(9,5) ⇒ [0, 5, 2, 7, 8]; permutation(9) ⇒ [2, 4, 8, 3, 7, 1, 5, 6, 0] |
rd (A) rd (A,m) |
If A is a ring, the first call yields an element of A chosen at random. The second form yields, if m is a positive integer, a list of m elements of A, not necessarily distinct, chosen at random. |
rd_nonzero (A) rd _nonzero (A, m) |
If A is a ring, the first expression supplies a non-zero an element of A chosen at random. The second form provides, if m is a positive integer, a list of m non-zero elements of A, not necessarily distinct, chosen at random. |
rd_vector(A,n) rd_nonzero_vector(A,n) |
The first expression yields a vector of length n
whose components are selected uniformly and independently at random from the finite ring
A. The second expression does the same, but
garanteeing that the result is a non-zero vector.
Examples: |
rd_permutation_matrix(n) |
The function
rd_permutation_matrix(n) selects
a random permutation p
of 0,1,...,n-1
and returns permutation_matrix(p) (see
Matrices).
Examples:
rd_permutation_matrix(4) ⇒
|
rd_GL(n,F = Zn(2)) |
If n is a positive integer and
F a finite field (Z2
by default), this function delivers an invertible matrix of oder n
with entries in F chosen uniformly at random in
GL(n,F). For more details about the construction and
its uniform character, see X180702
Examples: rd_GL(6) ⇒ [[0 1 0 1 1 1] [0 0 0 0 1 0] [1 1 1 1 0 1] [1 1 0 0 0 0] [1 1 1 0 0 1] [1 0 0 0 0 0]] :: Matrix[Z2]rd_GL(4,Zn(19)) ⇒ [[13 3 5 0] [13 18 15 16] [14 10 12 16] [ 3 18 15 1]] :: Matrix[Z19] |
rd_extend(A) rd_insert(A,r) |
If A
is a square matrix of order n over a finite field K,
this function creates a square matrix B with the following properties:
(1) The first row of B is a non-zero vector v
with entries in K
drawn uniformly at random; (2) if the index of the first non-zero entry of v
is r, the elements of the r-th column of B
below vr are drawn independently and uniformly at radom in
K.
The main property of B is that it distributed uniformly at random among the regular matrices of order n+1 if A has the same property among the regular matrices of order n. rd_extend uses rd_insert(A,r), where 0 ≤ r ≤ n+1, which inserts a column of random elements of K before the r-th column (meaning after the n-th column when r=n+1) and stacks the row er (1 in the r-th position and 0's elsewhere). on top
Examples: [[1 1] [1 0]] :: Matrix[Z2]C = rd_extend(B) ⇒ [[0 1 1] [1 0 1] [1 1 1]] :: Matrix[Z2]rd_insert(C,1) ⇒ [[0 1 0 0] [0 1 0 1] [1 1 1 0] [1 0 0 0]] :: Matrix[Z2]The functions are explained in detail in X180702 (cf. rd_GL(n,F)). |
rd_message (A,m=1) |
If
A is a string,
rd_message (A,m=1)
returns a string formed with m
characters of A, with possible repetitions,
drawn at random, and uniformly with respect to A.
A may also be a list or a range.
The parameter m = 1 can be omitted if m = 1.
Examples: |
show = print |
ruler(A, B, lw=1, dashing=-, color=k, left_inc=10, right_inc=10) |
Draws a segment of the lineAB that amounts to a prolongation of the segment [A,B] at both ends. By default, the prolongations are both a tenth of the length of the segment [A,B], but they can be set independently to any desired percent. The default linewidth is 1 point, the line is continuous, and the color is black. To draw a dashed ruler, include dashing=-- in the call. |
seg(A, B, lw=1, dashing=-, color=k) |
Draws a segment [A,B]. The default linewidth is 1 point, the line is continuous, and the color is black. To draw a dashed segment, include dashing=-- in the call. |
lable(A, Text, fs=18, dx=0, dy=0, color=k) |
Affixes Text, given as a string, at the point A. The default font size is 18 and the default color is black. The text can be offset by giving values to dx and dy. |
Yan-2002
Song Y. Yan:
Number theory for computeing (2nd edition).
Springer, 2002.