We first introduce a family of binary pq2-periodic sequences based on the Euler quotients modulo pq, where p and q are two distinct odd primes and p divides q - 1. The minimal polynomials and linear complexities are determined for the proposed sequences provided that 2q-1≠ 1 mod q2. The results show that the proposed sequences have high linear complexities.

In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected to a lower-dimensional space while preserving the pairwise Euclidean distances between points up to a bounded relative error. If the desired dimension of the image is too small, however, Kane, Meka, and Nelson (2011) and Jayram and Woodruff (2013) proved that such a projection does not exist. In this paper, we provide a precise asymptotic threshold for the dimension of the image, above which, there exists a projection preserving the Euclidean distance, but, below which, there does not exist such a projection.

Expander codes are Tanner codes defined on sparse graphs that have good expansion properties. Sipser and Spielman (1996) showed that there is a linear-time decoding algorithm for expander codes when the vertex expansion is at least 3/4 and the number of errors corrected is a constant fraction of the code length. Later, Feldman et al. (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where $c$ is the left degree of the underlying bipartite graph, at the expense of polynomial-time decoding complexity. Recently, Viderman (2013) further improved the expansion parameter to $2/3 - 1/(6c)$ , and the decoding algorithm runs in linear time. These results are for expander codes whose inner codes are parity-check codes. By using stronger inner codes, Chilappagari et al. (2010) showed that there is a linear-time decoding algorithm for every vertex expansion greater than 1/2. In this paper, it is shown that for every vertex expansion, there is a linear-time decoding algorithm for expander codes (using inner codes with minimum distance depending on the vertex expansion), and that the number of errors corrected is a constant fraction of the code length.

We present the first complexity analysis of the algorithm by Plantinga and Vegter for approximating real implicit curves and surfaces. This approximation algorithm certifies the topological correctness of the output using both subdivision and interval arithmetic. In practice, it has been seen to be quite efficient; our goal is to quantify this efficiency. We focus on the subdivision step (and not the approximation step) of the Plantinga and Vegter algorithm. We begin by extending the subdivision step to arbitrary dimensions. We provide a priori worst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and the bit complexity for the construction. Then, we use continuous amortization to derive adaptive bounds on the complexity of the subdivided region. We also provide examples showing our bounds are tight.

Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve C q : v 2 = u p − au − b over the field $\Fopf_{q}$ with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ $\Fopf_{p}$. In this paper, by introducing the concept of simple divisors, we prove that a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of $\Fopf_{p}$. Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less.

Every finite field has many multiplicative generators. However, finding one in polynomial time is an important open problem. In fact, even finding elements of high order has not been solved satisfactorily. In this paper, we present an algorithm that for any positive integer c and prime power q, finding an element of order in the finite field in deterministic time (qc)O(1). We also show that there are many weak keys for the discrete logarithm problems in those fields with respect to certain bases.

In this paper, we present a new algorithm for computing Gröbner bases. Our algorithm is incremental in the same fashion as F5 and F5C. At a typical step, one is given a Gröbner basis G for an ideal I and any polynomial g, and it is desired to compute a Gröbner basis for the new ideal , obtained from I by joining g. Let (I: g) denote the colon ideal of I divided by g. Our algorithm computes Gröbner bases for and (I: g) simultaneously. In previous algorithms, S-polynomials that reduce to zero are useless, in fact, F5 tries to avoid such reductions as much as possible. In our algorithm, however, these "useless" S-polynomials give elements in (I: g) and are useful in speeding up the subsequent computations. Computer experiments on some benchmark examples indicate that our algorithm is much more efficient (two to ten times faster) than F5 and F5C.

We present new additive Fast Fourier Transform (FFT) algorithms based on Taylor expansions over finite fields of characteristic two. The new algorithms improve previous approaches by Wang and Zhu (1988), Cantor (1989), and von zur Gathen and Gerhard (1996).

The input to our algorithm is a multivariate polynomial, whose complex rational coefficients are considered imprecise with an unknown error that causes f to be irreducible over the complex numbers C. We seek to perturb the coefficients by a small quantitity such that the resulting polynomial factors over C. Ideally, one would like to minimize the perturbation in some selected distance measure, but no efficient algorithm for that is known. We give a numerical multivariate greatest common divisor algorithm and use it on a numerical variant of algorithms by W. M. Ruppert and S. Gao. Our numerical factorizer makes repeated use of singular value decompositions. We demonstrate on a significant body of experimental data that our algorithm is practical and can find factorizable polynomials within a distance that is about the same in relative magnitude as the input error, even when the relative error in the input is substantial (10-3).

We introduce a new approach to multivariate polynomial factorisation which incorporates ideas from polyhedral geometry, and generalises Hensel lifting. Our main contribution is to present an algorithm for factoring bivariate polynomials which is able to exploit to some extent the sparsity of polynomials. We give details of an implementation which we used to factor randomly chosen sparse and composite polynomials of high degree over the binary field.

Motivated by a connection with block iterative methods for solving linear systems over finite fields, we consider the probability that the Krylov space generated by a fixed linear mapping and a random set of elements in a vector space over a finite field equals the space itself. We obtain an exact formula for this probability and from it we derive good lower bounds that approach 1 exponentially fast as the size of the set increases.

This article presents simple and highly regular architectures for finite field multipliers using a redundant representation. The basic idea is to embed a finite field into a cyclotomic ring which is based on the elegant multiplicative structure of a cyclic group. One important feature of our architectures is that they provide area-time trade-offs which enable us to implement the multipliers in a partial-parallel/hybrid fashion. This hybrid architecture has great significance in its VLSI implementation in very large fields. The squaring operation using the redundant representation is simply a permutation of the coordinates. It is shown that, when there is an optimal normal basis, the proposed bit-serial and hybrid multiplier architectures have very low space complexity. Constant multiplication is also considered and is shown to have an advantage in using the redundant representation.

The present paper is interested in a family of normal bases, considered by Sidel’nikov [Math. USSR-Sb., 61 (1988), pp. 485–494], with the property that all the elements in a basis can be obtained from one element by repeatedly applying to it a linear fractional function of the form $\varphi ( x ) = ( ax + b )/( cx + d ),a,b,c,d \in F_q $. Sidel’nikov proved that the products for such a basis $\{ \alpha _i \}$ are of the form $\alpha _i \alpha _j = e_{i - j} \alpha _i + e_{j - i} \alpha _j + \gamma ,i = j$, where $e_k ,\gamma \in F_q $. It is shown that every such basis can be formed by the roots of an irreducible factor of $F( x ) = cx^{q + 1} + dx^q - ax - b$. The following are constructed: (a) a normal basis of $F_{q^n } $ over $F_q $ with complexity at most $3n - 2$ for each divisor n of $q - 1$ and for $n = p$, where p is the characteristic of $F_q$; (b) a self-dual normal basis of $F_{q^n } $ over $F_q $ for $n = p$ and for each odd divisor n of $q - 1$ or $q + 1$. When $n = p$, the self-dual normal basis constructed of $F_{q^p } $ over $F_q$ also has complexity at most $3p - 2$. In all cases, the irreducible polynomials and the multiplication tables are given explicitly.