Computational Coding / Function summary
S. Xambó


By design, CC is a package that provides a computational environment for coding theory and practice. This page (work in progress) aims at providing descriptions of its functions. The current Python implementations are documented in PyECC.

Conventions. Zn denotes the ring of integers mod n and Zn* the multiplicative group of the invertible elements mod n.

      INDEX




Domains and general predicates

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:
22/7 >> Q_ ⇒ 22/7 :: Q, but 22/7 ⇒ 3.142857142857143.

domain(f)
This function returns the domain of the object f.

Examples:
If a = (5 >> Zn(12)), domain(a) ⇒ Z12 :: Ring.
If [ZX,X] = polynomial_ring(ZZ()), domain(X) ⇒ ZX :: Ring.
If v = vector(Zn(12),[1,2,3]), domain(v) ⇒ Mat(Z12) :: Array.

K_(f)
If f is a polynomial, a vector, or a matrix, this function yields the domain over which f is defined.

Examples:
If a = (5 >> Zn(12)), K_(a) ⇒ Z12 :: Ring.
If [ZX,X] = polynomial_ring(ZZ()), K_(X) ⇒ ZZ :: Ring.
If v = vector(Zn(12),[1,2,3]), K_(v) ⇒ Z12 :: Ring.

is_sub_domain(A,B)
Tests whether a domain A is a sub-domain of a domain B.

Examples:
is_sub_domain(Z_,Z_) ⇒ True
is_sub_domain(Z_,Q_) ⇒ True
is_sub_domain(Q_,Z_) ⇒ False
is_sub_domain(Z_,Zn(41)) ⇒ False

belongs(x, X)
If x is an object and X a domain, it returns True if x belongs to X, and False otherwise.

Examples:
belongs(2/3,Q_) ⇒ False
belongs(2/3>>Q_,Q_) ⇒ True

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.

» index | PyECC


Combinatorics

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:
a2b(20,29) ⇒ [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
a2b(29,20) ⇒ [ ]
len(a2b(100,500,5)) ⇒ 81
a2b(29,20,-1) ⇒ [29, 28, 27, 26, 25, 24, 23, 22, 21, 20]

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:
rd_selection( "abcdefghijklmnopqrstuvwxyz", 6) ⇒ ['j', 'r', 'f', 'm', 'e', 'c']
combination(10,5) ⇒ [2, 3, 4, 7, 8]
permutation(10) ⇒ [5, 3, 7, 2, 8, 0, 1, 6, 9, 4]

binom(n,k)
binomial = binom
The value of the expression is \(\binom{n}{k}\).

Example:
[binom(10,k) for k in a2b(0,10)] ⇒ [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]

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.

» index | PyECC


Arithmetic

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:
convert(314,10) ⇒ [3, 1, 4]
convert(314,2) ⇒ [1, 0, 0, 1, 1, 1, 0, 1, 0]
convert(314,16) ⇒ [1, 3, 10]
convert(314,60) ⇒ [5, 14]
hohner([1, 3, 10],16) ⇒ 314

factorial(n)
Computes n!

Examples:
factorial(23) ⇒ 25852016738884976640000
dlen(factorial(100000)) ⇒ 456574

fib(N)
fibonacci = fib
Delivers the Nth Fibonacci number.

Examples:
[fib(N) for N in a2b(1,10)] ⇒ [1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
fib(100) ⇒ 573147844013817084101
dlen(fib(1000000)) ⇒ 208988

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:
igcd(2**7 * 3**5 * 5**2 *7, 3**2 * 5**8) ⇒ 225
ilcm(2**7 * 3**5 * 5**2 *7, 3**2 * 5**8) ⇒ 85050000000
igcd(fib(100),fib(200)) ⇒ 1
igcd(fib(10), fib(20), fib(30)) ⇒ 1

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:
extended_euclidean_algorithm(fib(10), fib(11)) ⇒ (-55, 34, 1)
-55*fib(10)+34*fib(11) ⇒ 1

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:
n=12345678912345676537137911311771987
is_prime(n) ⇒ False
p = next_prime(n) ⇒ 12345678912345676537137911311772021
rabin_miller(p) ⇒ True
ifactor(n) ⇒ {155208191: 1, 3491: 1, 320916570893766397337: 1, 71: 1}

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)]
⇒ [9, 25, 27, 49, 81, 121, 125, 169, 243, 289, 343, 361, 529, 625, 729, 841, 961]
is_square(fib(1000)**2) ⇒ True
is_square(fib(1000)**2 + 1) ⇒ False

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:
primes_less_than(50) ⇒ [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
P = primes_less_than(106); len(P) ⇒ 78498

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:
next_q(97) ⇒ 97
next_p(97) ⇒ 97
next_q(98) ⇒ 101
next_p(98) ⇒ 101
next_q(3**7+1) ⇒ 2197 = 13**3
next_p(3**7+1) ⇒ 2203
.

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:
f5 = 2**(2**5)+1
is_prime(f5) ⇒ False
pollard(f5) ⇒ 641
f6 = 2**(2**6)+1
is_prime(f6) ⇒ False
pollard(f6) ⇒ 274177

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:
ifactor(23) ⇒ {23: 1}
ifactor(24) ⇒ {2: 3, 3: 1}
ifactor(12345678987654321) ⇒ {3: 4, 333667: 2, 37: 2}
prime_factors(12345678987654321) ⇒ [3, 3, 3, 3, 37, 37, 333667, 333667]

Note. Whereas in the table delivered by ifactor(n) the prime divisors of n do not appear in increasing order, they do so in the list produced by prime_factors(n)

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:
divisors(60) ⇒ [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
tau(60) ⇒ 12
sigma(60) ⇒ 168
divisors(2**8) ⇒ [1, 2, 4, 8, 16, 32, 64, 128, 256]
tau(2**8) ⇒ 9
sigma(2**8) ⇒ 511

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:
n = 7**11 * 101**13
phi_euler(n) ⇒ 190980108579576389822539918268429400
7**10 * 6 * 101**12 * 100 ⇒ 190980108579576389822539918268429400
[lambda_carmichael(n) for n in a2b(1,10)+a2b(100,103)] ⇒ [1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 20, 100, 16, 102]
n = 2**4 * 3**2 * 5 * 7 * 13
n, phi_euler(n), lambda_carmichael(n) ⇒ (65520, 13824, 12)

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:
mu_moebius(17) ⇒ -1
mu_moebius(51) ⇒ 1
mu_moebius(121) ⇒ 0

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:
is_square_free_n(123456789) ⇒ False
ifactor(123456789) ⇒ {3: 2, 3803: 1, 3607: 1}
is_square_free_n(123456789//3) ⇒ True

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 x1
The 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:
  • lucas_U(P,Q,N) = lucas_number(P,Q,0,1,N)
  • pell(N) = lucas_U(2,-1,N)
  • jacobsthal(N) = lucas_U(1,-2,N)
  • lucas_V(P,Q,N) = lucas_number(P,Q,2,P,N)
  • lucas(N) = lucas_V(1,-1,N)
  • pell_lucas(N) = lucas_V(2,-1,N)
  • jacobsthal_lucas(N) = lucas_V(1,-2,N)
The N-th Mersenne number is 2N-1 coincides with lucas_U(3,2,N) and can be obtained with mersenne(N).

Examples:
R = a2b(1,10)
[pell(N) for N in R] ⇒ [1, 2, 5, 12, 29, 70, 169, 408, 985, 2378]
[jacobsthal(N) for N in R] ⇒ [1, 1, 3, 5, 11, 21, 43, 85, 171, 341]
[lucas(N) for N in R] ⇒ [1, 3, 4, 7, 11, 18, 29, 47, 76, 123]
[pell_lucas(N) for N in R] ⇒ [2, 6, 14, 34, 82, 198, 478, 1154, 2786, 6726]
[jacobsthal_lucas(N) for N in R] ⇒ [1, 5, 7, 17, 31, 65, 127, 257, 511, 1025]
[mersenne(N) for N in R] ⇒ [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
[lucas_U(3,2,N) for N in R] ⇒ [1, 3, 7, 5, 31, 63, 127, 255, 511, 1023]

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
BPSW(n) ⇒ True
ifactor(n+2) ⇒ {4001286937: 1, 22578335198067455967303388696235369076794326853: 1, 11069: 1}

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:
n = next_prime(10**50) ⇒ 100000000000000000000000000000000000000000000000151
miller(n) ⇒ True
miller(22578335198067455967303388696235369076794326853) ⇒ True

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:
LL(9869) ⇒ False
ifactor(9869) ⇒ {139: 1, 71: 1}
LL(9689) ⇒ True

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(π,4) ⇒ [3,7,15,1].

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:
continuous_fraction_value([3,7,15,1]) ⇒ 355/113 :: Q.
Note that 355/113 ⇒ 3.1415929 ..., whereas π = 3.1415926 ....

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:
1/7 ⇒ 0.14285714285714285
dec2bin(1/7) ⇒ '0010010010010010010010010010010010010010010010010010010000'
bin2dec('0010010010010010010010010010010010010010010010010010010000') ⇒ 0.14285714285714285

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:
floor(−2.5) ⇒ −3
floor(−2) ⇒ −2
floor(0.99) ⇒ 0;
floor(3.14) ⇒ 3

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:
ceiling(−2.5) ⇒ −2
ceiling(−2) ⇒ −2
ceiling(0.99) ⇒ 1
ceiling(3.14) ⇒ 4
ceiling(3.000000000000001) ⇒ 4
qceiling(3000000000000001, 10**15) ⇒ 4
ceiling(3.0000000000000001) ⇒ 3
qceiling(30000000000000001, 10**16) ⇒ 4

» index | PyECC

Modular arithmetic

order(k, n)
If gcd(k,n) = 1, the order of k in Zn*.

Examples: order(2,9) ⇒ 6
a=2>>Zn(9); [a**j for j in range(7)] ⇒ [1 :: Z9, 2 :: Z9, 4 :: Z9, 8 :: Z9, 7 :: Z9, 5 :: Z9, 1 :: Z9]
order(37,666) ⇒ 'k is not invertible mod n'
order(73,666) ⇒ 2
order(79,666) ⇒ 36

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:
inverse(79,666) ⇒ 607
79*607 % 666 ⇒ 1.

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:
mult (23, 127, 5) ⇒ 9
pow (23, 127, 10) ⇒ 935
quot (23, 127, 8) ⇒ 105
power (1729, 9271,1000) ⇒ 329

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:
sqroot(25,4) ⇒ 13
nroot(25,2,4) ⇒ 13
nroot(125,3,5) ⇒ 13
Note. 13225 mod 16 ⇒ 1, 133125 mod 64 ⇒ 1.

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:
cyclotomic_class(2,17) ⇒ [2, 4, 8, 16, 15, 13, 9, 1]
cyclotomic_class(2,17,3) ⇒ [2, 6, 1, 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12]

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:
cycloctomic_classes(17) ⇒ [[0], [1, 2, 4, 8, 16, 15, 13, 9], [3, 6, 12, 7, 14, 11, 5, 10]]
cycloctomic_classes(16,3) ⇒ [[0], [1, 3, 9, 11], [2, 6], [4, 12], [5, 15, 13, 7], [8], [10, 14]]

» index | PyECC

Vectors

Vectors are the instances of the class Vector. They look like lists, but the sum is defined as the vector sum (not the list sum) and similarly with the product of an expression by a vector.

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:
eps(4,1) ⇒ [0, 1, 0, 0]
eps(3,4,2,2) ⇒

[[0  0  0  0]
 [0  0	0  0]
 [0  0	1  0]] :: Matrix[ZZ]

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:
x = rd_vector(Zn(2),7) ⇒ [1, 0, 0, 1, 0, 0, 1] :: Vector[Z2]
flip(x) ⇒ [1, 0, 1, 1, 0, 0, 1] :: Vector[Z2]
flip(x) ⇒ [1, 0, 0, 1, 0, 0, 1] :: Vector[Z2]
R = vector(Zn(5), list(range(9))) ⇒ [0,1,2,3,4,0,1,2,3] :: Vector(Z5)
flip(R,(1,6)) ⇒ [0, 0, 2, 3, 4, 0, 0, 2, 3] :: Vector[Z5]
flip(R) ⇒ [1, 1, 4, 3, 2, 1, 1, 4, 3] :: Vector[Z5]

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

» index | PyECC

Polynomials and power series

[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)

» index | PyECC



Finite rings and fields

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')

» index | PyECC

Matrices

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:
M = matrix(Zn(18),2,3) ⇒

[[0  0  0]
 [0  0  0]] :: Matrix[Z18]
M[0,1] = 11>>Zn(18)
M ⇒
[[0 11  0]
 [0  0  0]] :: Matrix[Z18]

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)) ⇒

[[1  0  0]
 [0  1  0]
 [0  0  1]] :: Matrix[Z8]
I_(3) ⇒
[[1  0  0]
 [0  1  0]
 [0  0  1]] :: Matrix[Z2]
I_(3,Z_) ⇒
[[1  0  0]
 [0  1  0]
 [0  0  1]] :: Matrix[ZZ]

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:
a=[1,2,3,4,5,6]; A = vandermonde(a,3,1) ⇒

[[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]) ⇒

[[0  0  1]
 [0  1  0]
 [1  0  0]] :: Matrix[ZZ]

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) ⇒

[[1 0 0 1]
 [0 1 1 0]] :: Matrix[ZZ]
stack(A,B) ⇒
[[1 0]
 [0 1]
 [0 1]
 [1 0]] :: Matrix[ZZ]

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) ⇒

[[1 2]
 [2 3]] :: Matrix[ZZ]

S = a2b(1,5); hankel_matrix(S) ⇒

[[1 2 3]
 [2 3 4]
 [3 4 5]] :: Matrix[ZZ]

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

» index | PyECC

Source coding


Block coding

For the definitions and notations, we refer to Xambó-2003.

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.

» index | PyECC

Decoders and decoding tools

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.

» index | PyECC

Decoding tools

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)).

» index | PyECC

Probability tools

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_gauss() ⇒ 0.369
rd_gauss(50) ⇒ 50.602
rd_gauss(sigma=10) ⇒ 5.927
rd_gauss(50,10) ⇒ 53.975

Random resources

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_int(10,999) ⇒ 696
ri(15) ⇒ 182570876961559
rd_prime() ⇒ 91381
rd_prime(50) ⇒ 84640154098367084505945561799952113529399310885089

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_vector(Zn(12),8) ⇒ [4, 2, 11, 3, 11, 0, 7, 6] :: Vector[Z12]
rd_nonzero_vector(Zn(7),3) ⇒ [0, 5, 5] :: Vector[Z7]

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) ⇒

[[0  0  1  0]
 [1  0  0  0]
 [0  1  0  0]
 [0  0  0  1]] :: Matrix[ZZ] 

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:
K = Zn(2); u = 1>>K; A = matrix(u); B = rd_extend(A) ⇒

[[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:
rd_message('abc',10) ⇒ 'aacbcbcaab'
rd_message(range(10,20),10) ⇒ '19111213101115161419'
rd_message([0,1],25) ⇒ '1111011011000001011011000'
rd_message([2,3,5,7,11,13,17,19,23,29]) ⇒ '17'

» index | PyECC

Signals

Utilities

show = print

Graphics

The graphic functions in PyECC are based on the Python matplotlib pyplot package, which is loaded as plt.

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.

References

Crandall-Pomerance-2005
Richar Crandall, Carl Pomerance: Prime numbers, a computational perspective (2nd edition). Springer, 2005.

Yan-2002
Song Y. Yan: Number theory for computeing (2nd edition). Springer, 2002.


SXD

31.12.2018