Applicable Algebra in Engineering, Communication and Computing

article

On the location of roots of non-reciprocal integer polynomials

Artūras Dubickas

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 1 > 1-19

Let P be a polynomial of degree d with integer coefficients such that P(0) ≠ 0. Assuming that P has no reciprocal factors we obtain a lower bound on the modulus of the smallest root of P in terms of its degree d, its Mahler measure M(P) and the number of roots of P lying outside the unit circle, say, k. We derive from this that all d roots of P must lie in the annulus R ₀ < |z| < R ₁, where...

article

The generalized road coloring problem and periodic digraphs

G. Budzban, Ph. Feinsilver

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 1 > 21-35

A proof of the Generalized Road Coloring Problem, independent of the recent work by Beal and Perrin, is presented, using both semigroup methods and Trakhtman’s algorithm. Algebraic properties of periodic, strongly connected digraphs are studied in the semigroup context. An algebraic condition which characterizes periodic, strongly connected digraphs is determined in the context of periodic Markov...

article

On necessary and sufficient conditions for differential flatness

Jean Lévine

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 1 > 47-90

This paper is devoted to the characterization of differentially flat nonlinear systems in implicit representation, after elimination of the input variables, in the differential geometric framework of manifolds of jets of infinite order. We extend the notion of Lie-Bäcklund equivalence, introduced in Fliess et al. (IEEE Trans Automat Contr 44(5):922–937, 1999), to this implicit context and focus attention...

article

The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity

Guanghong Sun, Chuankun Wu

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 1 > 37-45

The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. By investigating the lower bound of the nonlinearity of the derivative of the function f, this paper tightens the lower bound of the second-order nonlinearity...

article

Higher weights for codes over rings

Steven T. Dougherty, Sunghyu Han, Hongwei Liu

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 2 > 113-135

A generalized definition of higher weights for codes over finite chain rings and principal ideal rings and bounds on the minimum higher weights in this setting are given. Using this we generalize the definition for higher MDS and MDR codes. Computationally, the higher weight enumerator of lifted Hamming and Simplex codes over $${\mathbb{Z}_4}$$ , the minimum higher weights for the lifted code...

article

On the arithmetic of the endomorphisms ring $${{\rm End}(\mathbb{Z}_{p} \times \mathbb{Z}_{p^{2}})}$$

Joan-Josep Climent, Pedro R. Navarro, Leandro Tortosa

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 2 > 91-108

For a prime number p, Bergman (Israel J Math 18:257–277, 1974) established that $${{\rm End}(\mathbb{Z}_{p}\times \mathbb{Z}_{p^{2}})}$$ is a semilocal ring with p ⁵ elements that cannot be embedded in matrices over any commutative ring. We identify the elements of $${{\rm End}(\mathbb{Z}_{p} \times \mathbb{Z}_{p^{2}})}$$ with elements in a new set, denoted by E _p, of matrices of size...

article

A check digit system for hexadecimal numbers

Markku Niemenmaa

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 2 > 109-112

We present a new check digit system for hexadecimal numbers which is based on the use of a suitable automorphism of the elementary abelian group of order sixteen. Our system is able to detect all single errors, adjacent transpositions, twin errors, jump transpositions and jump twin errors.

article

Elliptic curves and Fibonacci numbers arising from Lindenmayer system with symbolic computation

Hiroshi Yoshida, Yoshihiro Miwa, Masanobu Kaneko

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 2 > 147-164

Starting from an egg, the multicell becomes a set of cells comprising a variety of types to serve functions. This phenomenon brings us a bio-motivated Lindenmayer system. To investigate conditions for a variety of cell types, we have constructed a stochastic model over Lindenmayer systems. This model considers interactive behaviors among cells, yielding complicated polynomials. Using symbolic computation,...

article

On the equivalence of linear codes

Zihui Liu, Zhimin Sun

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 2 > 137-145

Certain equivalent conditions are given for the equivalence of linear codes using the properties of the relative subcodes derived from the relative generalized Hamming weight.

article

Counting decomposable multivariate polynomials

Joachim zur Gathen

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 3 > 165-185

A polynomial f (multivariate over a field) is decomposable if $${f=g \circ h}$$ with g univariate of degree at least 2. We determine the dimension (over an algebraically closed field) of the set of decomposables, and an approximation to their number over a finite field. The relative error in our approximations is exponentially decaying in the input size.

article

Generalized quasi-cyclic codes over Galois rings: structural properties and enumeration

Yonglin Cao

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 3 > 219-233

For R a Galois ring and m ₁, . . . , m _l positive integers, a generalized quasi-cyclic (GQC) code over R of block lengths (m ₁, m ₂, . . . , m _l) and length $${\sum_{i=1}^lm_i}$$ is an R[x]-submodule of $${R[x]/(x^{m_1}-1)\times\cdots \times R[x]/(x^{m_l}-1)}$$ . Suppose m ₁, . . . , m _l are all coprime to the characteristic of R and let {g ₁, . . . , g _t} be the set of all monic...

article

Complexity bounds for the rational Newton-Puiseux algorithm over finite fields

Adrien Poteaux, Marc Rybowicz

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 3 > 187-217

We carefully study the number of arithmetic operations required to compute rational Puiseux expansions of a bivariate polynomial F over a finite field. Our approach is based on the rational Newton-Puiseux algorithm introduced by D. Duval. In particular, we prove that coefficients of F may be significantly truncated and that certain complexity upper bounds may be expressed in terms of the output size...

article

New p-ary sequence family with low correlation and large linear span

Zhengchun Zhou, Xiaohu Tang, Udaya Parampalli, Daiyuan Peng

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 301-309

In this paper, for an odd prime p and positive integers n, m, and e such that n = me, a new family $${\mathcal{S}}$$ of p-ary sequences of period p ⁿ − 1 with low correlation and large linear span is constructed. It is shown that $${\mathcal{S}}$$ has maximum correlation $${1+p^{n+2e\over 2}}$$ , family size p ⁿ, and maximal linear span $${{(m+3)n\over 2}}$$ . When m is even,...

article

Optimal pairing computation over families of pairing-friendly elliptic curves

Soo-Kyung Eom, Hyang-Sook Lee, Cheol-Min Park

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 235-248

Vercauteren introduced the concept of optimal pairing, which by definition can be computed by using at most (log₂ r)/φ(k) + log₂ k basic Miller iterations, where r is the order of the groups involved and k is the embedding degree Vercauteren (IEEE Trans Inf Theory 56(1):455–461, 2010). Freeman et al. summarized and proposed all of the new constructions of pairing-friendly elliptic...

article

Aperiodic correlation of Kasami sequences in the small set

Zhimin Sun, Xiangyong Zeng, Wei Su, Lei Hu

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 311-320

In this paper, an upper bound for a hybrid exponential sum over a finite field GF(p ^m) is derived. This bound is then used to obtain an upper bound on the aperiodic correlation of nonbinary Kasami sequences in the small set. Similar method is also applied to get a new upper bound on the aperiodic correlation of binary Kasami sequences in the small set.

article

Envelope computation in the plane by approximate implicitization

Tino Schulz, Bert Jüttler

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 265-288

Given a rational family of planar rational curves in a certain region of interest, we are interested in computing an implicit representation of the envelope. The points of the envelope correspond to the zero set of a function (which represents the envelope condition) in the parameter space combining the curve parameter and the motion parameter. We analyze the connection of this function to the implicit...

article

Testing degenerate polynomials

Mihai Cipu, Ismaïla Diouf, Maurice Mignotte

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 289-300

Two methods to test whether a given polynomial has two distinct roots whose quotient is a root of unity are discussed.

article

The minimum distance of parameterized codes on projective tori

Eliseo Sarmiento, Maria Vaz Pinto, Rafael H. Villarreal

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 4 > 249-264

Let X be a subset of a projective space, over a finite field K, which is parameterized by the monomials arising from the edges of a clutter. Let I(X) be the vanishing ideal of X. It is shown that I(X) is a complete intersection if and only if X is a projective torus. In this case we determine the minimum distance of any parameterized linear code arising from X.

article

Finite field trigonometric transforms

Juliano B. Lima, Ricardo M. Campello de Souza

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 5-6 > 393-411

In this paper, the finite field trigonometric transforms (FFTT) are introduced. The FFTT family includes eight types of cosine transforms and eight types of sine transforms, which are developed from concepts related to the finite field trigonometry. New lemmas are presented and some properties of the FFTT are discussed.

article

Affine braid groups: a better platform than braid groups for cryptology?

Ping Zhu, Qiaoyan Wen

Applicable Algebra in Engineering, Communication and Computing > 2011 > 22 > 5-6 > 375-391

In recent years, various cryptographic protocols using infinite non-commutative groups, notably braid groups, have been proposed. Both experimental and theoretical evidence collected so far, however, makes it appear likely that braid groups are not a good choice for the platform. In this paper, we thus consider to use affine braid groups, a natural generalization of braid groups, as a platform. Like...

INFONA - science communication portal

Applicable Algebra in Engineering, Communication and Computing

On the location of roots of non-reciprocal integer polynomials

The generalized road coloring problem and periodic digraphs

On necessary and sufficient conditions for differential flatness

The lower bound on the second-order nonlinearity of a class of Boolean functions with high nonlinearity

Higher weights for codes over rings

On the arithmetic of the endomorphisms ring $${{\rm End}(\mathbb{Z}_{p} \times \mathbb{Z}_{p^{2}})}$$

A check digit system for hexadecimal numbers

Elliptic curves and Fibonacci numbers arising from Lindenmayer system with symbolic computation

On the equivalence of linear codes

Counting decomposable multivariate polynomials

Generalized quasi-cyclic codes over Galois rings: structural properties and enumeration

Complexity bounds for the rational Newton-Puiseux algorithm over finite fields

New p-ary sequence family with low correlation and large linear span

Optimal pairing computation over families of pairing-friendly elliptic curves

Aperiodic correlation of Kasami sequences in the small set

Envelope computation in the plane by approximate implicitization

Testing degenerate polynomials

The minimum distance of parameterized codes on projective tori

Finite field trigonometric transforms

Affine braid groups: a better platform than braid groups for cryptology?

Filter options

Publication date

Volume

Keywords

INFONA - science communication portal

Applicable Algebra in Engineering, Communication and Computing

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Volume

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options