Search

In the context of blind signature schemes, how to devise efficient and concurrent-secure blind signature scheme without random oracles has been a very active research topic. Recently, Gjøsteen et al. proposed a round-optimal blind signature scheme in the registered public key model. Unfortunately, this scheme has the drawback that the costs of computation and communication of its signing protocol are linear in the size of the message to be signed. The main contribution of this paper is a revised scheme which is built on the Zhou-Lin signature scheme, the compilation technique of Damgård et al., and Arita's straight-line extractable commitment scheme. The salient features of the new scheme are that the costs of computation and communication of its signing protocol do not depend on the size of the message to be signed. In addition, the resultant signature is very short and has an efficient verification process. Moreover, thanks to the technique of straight-line extraction, the security reduction algorithm is efficient and run in strictly polynomial-time. [ABSTRACT FROM AUTHOR]

An array antenna system with innovative signal processing can enhance the resolution of a signal direction of arrival (DOA) estimation. Super resolution algorithms take advantage of array antenna structures to better process the incoming signals. They also have the ability to identify multiple targets. This paper explores the Polynomial Roots Intersection for Multi-dimensional Estimation (PRIME) algorithms. The PRIME algorithm allows a polynomial rooting approach to estimate joint azimuth/elevation parameters of the signal detection for planer arrays. This method calculates a finite set of root intersections, which are the simultaneous solutions from multiple independent multivariate polynomials. The solutions for the source angle information are included in the simultaneous solutions. The PRIME algorithm does not require the use of a scan vector to scan all possible directions. The results demonstrate improvement in both resolution and computational efficiency with no loss of accuracy. Statistical analysis of the performance of the processing algorithm and processing resource requirements are discussed in this paper. Extensive computer simulations are used to show the performance of the algorithms. [ABSTRACT FROM AUTHOR]

The security of the RSA public key cryptosystem depends on the intractability of the integer factoring problem. This paper shall give some theoretical support to the assumption of hardness of this number theoretic problem. We obtain lower bounds on degree, weight, and additive complexity of polynomials interpolating functions related to the integer factoring problem, including Euler΄s totient function, the divisor sum functions, Carmichael΄s function, and the RSA-function. These investigations are motivated by earlier results of the same flavour on the interpolation of discrete logarithm and Diffie-Hellman mapping. [ABSTRACT FROM AUTHOR]

Puzzles and games have been used for centuries to nurture problem-solving skills. Although often presented as isolated brain-teasers, the desire to know how to win makes games ideal examples for teaching algorithmic problem solving. With this in mind, this paper explores one-person solitaire-like games. The key to understanding solutions to solitaire-like games is the identification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a collection of novel one-person games. The known classification of states of the game of (peg) solitaire into 16 equivalence classes is used to introduce the relevance of polynomial arithmetic. Then we give a novel algebraic formulation of the solution to a class of tiling problems. Finally, we introduce an infinite class of challenging one-person games inspired by earlier work by Chen and Backhouse on the relation between cyclotomic polynomials and generalisations of the seven-trees-in-one type isomorphism. We show how to derive algorithms to solve these games. [ABSTRACT FROM AUTHOR]

In this paper, we study a single-machine deteriorating job scheduling problem with job release times where the objective is to minimize the makespan. The problem is known to be strongly NP-complete. Therefore, we first develop a branch-and-bound algorithm incorporating with several dominance properties and a lower bound to derive the optimal solution. Then, we propose two heuristic algorithms for the near-optimal solutions. Finally, we conduct some computational experiments to evaluate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we propose a fuzzy rulebased boundary extraction method for a plaque in an intravascular ultrasound (IVUS) image. In the present method, a plaque boundary to be extracted is piecewise approximated by the polynomials inferred by fuzzy rules. The coefficients of the polynomials are determined by the weighted least square method using the separability measure obtained from the IVUS image. The proposed method achieves a precise and noise-robust extraction of the plaque with use of a small number of seed points and without any timeconsuming iterative processes. The validity and the effectiveness of the proposed method have been confirmed by applying it to the boundary extraction problem of the plaque in the IVUS image. [ABSTRACT FROM AUTHOR]

Normal basis in finite fields has proved to be very useful for fast arithmetic computations. The elements in a normal basis are exactly the roots of a normal polynomial. Hence a normal polynomial is just another way of describing a normal basis. In this paper, we give some computational results of normal polynomial up to degree n = 19 according to the fast algorithm from Chang et al. [1]. [ABSTRACT FROM AUTHOR]

Key distribution center (KDC) is an important component for generating symmetric key. Security and efficiency are critical in the implementation of KDC. In this paper we presented a secure distributed symmetric key generation scheme which uses bivariate polynomial to construct (k,n)-threshold pseudo-random number function, any k or more of the n KDC servers can compute the pseudo-random number for key, and any less than k-1 KDC servers can't get the symmetric key. So it can enhance the security of distributed KDC servers, and prevent bottlenecks or single points of failure in service. Our scheme uses Zero-knowledge proof technology to verify cheating from initiators or participants. [ABSTRACT FROM AUTHOR]

In this paper, we study a special class of nonbinary additive cyclic codes over GF(4) which we call reversible complement cyclic codes. Such codes are suitable for constructing codewords for DNA computing. We develop the theory behind constructing the set of generator polynomials for these codes. We study, as an example, all length—7 codes over GF(4) and list those that have the largest minimum Hamming distance and largest number of codewords. [ABSTRACT FROM AUTHOR]

The idea to find first integrals for polynomial vector fields via algebraic invariant curves can be traced back to Darboux in the 19th century. In 1983, this approach was further developed by Prelle and Singer to become a semi-decision algorithm for finding elementary first integrals. In this paper, we describe how to extend the Prelle-Singer method to deal with second order linear differential equations via Kovacic's results on algebraic solutions of Riccati equations. Some illustrative examples on using this approach are provided. [ABSTRACT FROM AUTHOR]

The discrete Fourier transform (DFT) of a boolean function yields a trace representation or equivalently, a polynomial representation, of the boolean function, which is identical to the DFT of the sequence associated with the boolean function. Using this tool, we investigate characterizations of boolean functions for which the fast algebraic attack is applicable. In order to apply the fast algebraic attack, the question that needs to be answered is that: for a given boolean function f in n variables and a pair of positive integers (d, e), when there exists a function g with degree at most d such that ]> where h΄s degree is at most e. We give a sufficient and necessary condition for the existence of those multipliers of f. An algorithm for finding those multipliers is given in terms of a polynomial basis of 2n dimensional space over ]> which is established by an arbitrary m-sequence of period 2n − 1 together with all its decimations and certain shifts. We then provide analysis for degenerated cases and introduce a new concept of resistance against the fast algebraic attack in terms of the DFT of sequences or boolean functions. Some functions which made the fast algebraic attack inefficient are identified. [ABSTRACT FROM AUTHOR]

The notions and results developed in Chapter 12 for matrix polynomials are used in this chapter to study systems of differential and difference equations of higher order with constant coefficients. [ABSTRACT FROM AUTHOR]

Let x1, x2, . . . , xm be a linearly independent set in a linear space with a definite inner product. In classical linear algebra and analysis a fundamental role is played by the construction of a mutually orthogonal set of vectors y1, y2, . . . , ym for which each subset y1, . . . , yk (k ≤ m) spans the same subspace as x1, . . . , xm. The well-known Gram—Schmidt process is of this kind. This is also the central idea in the analysis of systems of orthogonal polynomial functions. This chapter is devoted to the development of this line of thought in the context of the linear space Cn with an indefinite inner product. Motivated by applications, attention will be confined to sets of vectors y1, . . . , ym for which [yj, yj] ≠ 0 for each j; sometimes described as the case of “nonzero squares”. In this case the orthogonalization will be said to be regular. It turns out that the results look very like those obtained in the classical case based on a definite inner product. The chapter consists of four sections. The first contains general results concerning orthogonal (regular) systems. The second contains discussion of a fundamental theorem of Szegő for the case of a definite inner product, as well as a more general theorem of M. G. Krein for the indefinite case. The last two sections contain a proof of the Krein theorem using the “one-step case” developed by Ellis and Gohberg as well as their and Lay’s analysis of fundamental determinants arising in an extension of this process. [ABSTRACT FROM AUTHOR]

Chapter nine of the book "Green's Function Estimates for Lattice Schrödinger Operators and Applications," by J. Bourgain is presented. It explores the facts regarding semialgebraic sets, as well as its polynomial equalities and inequalities. It also discusses the assumed diophantine and standard equidistribution considerations of semialgebraic sets.

Polynomial factorization is one of the main chapters of Computer Algebra. Recently, significant progress was made on absolute factorization (i.e., over the complex field) of a multivariate polynomial with rational coefficients, with two families of algorithms proposing two different strategies of computation. One is represented by Gao’s algorithm and is explained in Lecture 2. The other is represented by the Galligo-Rupprecht-Chèze algorithm, presented in Lectures 4 and 5. The latter relies on an original use of the monodromy map attached to a generic projection of a plane curve on a line. It also involves zero-sums relations (introduced by Sasaki and his collaborators) with efficient semi-numerical computations to produce a certified exact result. [ABSTRACT FROM AUTHOR]

This chapter is intended as a brief survey of the different notions and results that arise when we try to compute the algebraic complexity of algorithms solving polynomial equation systems. Although it is essentially self-contained, many of the definitions, problems and results we deal with also appear in many other chapters of this book. We start by considering algorithms which use the dense representation of multivariate polynomials. Some results about the algebraic complexities of the effective Nullstellensatz, of quantifier elimination processes over algebraically closed fields and of the decomposition of algebraic varieties when considering this model are stated. Then, it is shown that these complexities are essentially optimal in the dense representation model. This is the reason why a change in the encoding of polynomials is needed to get better upper bounds for the complexities of new algorithms solving the already mentioned tasks. The straight-line program representation for multivariate polynomials is defined and briefly discussed. Some complexity results for algorithms in the straight-line program representation model are mentioned (an effective Nullstellensatz and quantifier elimination procedures, for instance). A description of the Newton-Hensel method to approximate roots of a system of parametric polynomial equations is made. Finally, we mention some new trends to avoid large complexities when trying to solve polynomial equation systems. [ABSTRACT FROM AUTHOR]

This tutorial gives an introductory presentation of algebraic and geometric methods to solve a polynomial system ƒ1 = ⋯ = ƒm = 0. The algebraic methods are based on the study of the quotient algebra A of the polynomial ring modulo the ideal I = (ƒ1,..., ƒm). We show how to deduce the geometry of solutions from the structure of A and in particular, how solving polynomial equations reduces to eigenvalue and eigenvector computations of multiplication operators in A. We give two approaches for computing the normal form of elements in A, used to obtain a representation of multiplication operators. We also present the duality theory and its application to solving systems of algebraic equations. The geometric methods are based on projection operations which are closely related to resultant theory. We present different constructions of resultants and different methods for solving systems of polynomial equations based on these formulations. Finally, we illustrate these tools on problems coming from applications in computer-aided geometric design, computer vision, robotics, computational biology and signal processing. [ABSTRACT FROM AUTHOR]

This chapter studies algebras obtained as the quotient of a polynomial ring by an ideal of finite codimension. These algebras have a rich supply of interesting linear maps whose eigenvalues, eigenvectors, and characteristic polynomials can be used to solve systems of polynomial equations. We will also discuss applications to resultants, factorization, primary decomposition, and Galois theory. [ABSTRACT FROM AUTHOR]

This article presents the minimum mean square error (MMSE) estimation of Gaussian random vectors and the linear MMSE estimator for arbitrarily distributed random vectors. The latter is the estimator constrained to have a linear form. The estimation of unknown constant vectors according to the least squares criterion, where both the batch and recursive versions are derived. Polynomials in time can be fitted to a set of arbitrarily spaced data points via the least squares method. Explicit expressions have been presented for the coefficients of polynomials up to third order fitted to a set of uniformly spaced data points. The coefficients, as presented, yield estimates of the position and its derivatives at the center of the batch of measurements.