We consider a two polynomials analogue of the polynomial interpolation problem. Namely, we consider the Mixing Modular Operations (MMO) problem of recovering two polynomials f ∈ Zp[x] and g ∈ Zq[x] of known degree, where p and q are two (un)known positive integers, from the values of f(t) mod p+g(t) mod q at polynomially many points t ∈ Z. We show that if p and q are known, the MMO problem can be reduced to computing a close vector in a lattice with respect to the infinity norm. Using the Gaussian heuristic we also implemented in the SAGE system a polynomial-time algorithm. If p and q are kept secret, we do not know how to solve this problem. This problem is motivated by several potential cryptographic applications.

Abstract We describe a polynomial‐time algorithm for deciding whether a given distance graph with a finite number of vertices is connected. This problem was conjectured to be NP‐hard in Draque Penso et al. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

In the study of double-loop computer networks, the diagrams known as L-shapes arise as a graphical representation of an optimal routing for every graph's node. The description of these diagrams provides an efficient method for computing the diameter and the average minimum distance of the corresponding graphs. We extend these diagrams to multiloop computer networks. For each Cayley digraph with a finite abelian group as vertex set, we define a monomial ideal and consider its representations via its minimal system of generators or its irredundant irreducible decomposition. From this last piece of information, we can compute the graph's diameter and average minimum distance. That monomial ideal is the initial ideal of a certain lattice with respect to a graded monomial ordering. This result permits the use of Gröbner bases for computing the ideal and finding an optimal routing. Finally, we present a family of Cayley digraphs parametrized by their diameter d, all of them associated to irreducible monomial ideals.

Let p be a prime and let c be an integer modulo p. The Pollard generator is a sequence (un) of pseudorandom numbers defined by the relation un+1equivun2+c mod p. It is shown that if c and 9/14 of the most significant bits of two consecutive values un,un+1of the Pollard generator are given, one can recover in polynomial time the initial value u0with a probabilistic algorithm. This result is an improvement of a theorem in a recent paper which requires that 2/3 of the most significant bits be known

The basis for designing error-correcting codes for two dimensional signal sets is considered in this paper. Both, algebraic and graph-theoretical approaches are employed in this research for establishing the fundamentals of these codes. We give a solution to the t-dominating set problem in a subfamily of degree four circulant graphs which directly provides perfect codes over the Gaussian integers. In order to show the applicability of our results, simple examples for designing different coding schemes are also presented

We obtain lower bounds on the linear and nonlinear complexity profile of a general nonlinear pseudorandom number generator, of the inversive generator, and of a new nonlinear generator called quadratic exponential generator. The results are interesting for applications to cryptography and Monte Carlo methods.

In this paper we present an algorithm to compute all unirational fields of transcendence degree one containing a given finite set of multivariate rational functions. In particular, we provide an algorithm to decompose a multivariate rational function f of the form f = g(h), where g is a univariate rational function and h a multivariate one. 1

Article A practical implementation of two rational function decomposition algorithms Share on Authors: Jaime Gutierrez View Profile , Tomas Recio View Profile Authors Info & Claims ISSAC '92: Papers from the international symposium on Symbolic and algebraic computationAugust 1992 Pages 152–157https://doi.org/10.1145/143242.143298Online:01 August 1992Publication History 1citation264DownloadsMetricsTotal Citations1Total Downloads264Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access