Hadamard matrices are n × n matrices with elements in {1, -1} for which the inverse of the matrix is the transpose scaled by 1/n. The most important conjecture in the theory of Hadamard matrices is their existence when n is a multiple of 4. Although algebraic constructions have been proposed for some specific values, no general constructions exist in the literature, and they are usually found by computational search for a given n. The smallest value for which a Hadamard matrix of order n is not known, is n = 668.

Families of binary sequences with good auto- or cross-correlation properties are required in areas such as cryptography, wireless communications, and digital watermarking. Algebraic constructions present an advantage over random sequences in that fixed bounds can be provided for the off-peak correlation. The interleave and the composition method take a well-distributed pseudonoise sequence, such as an m-sequence, that can be extended to produce larger families with given properties and longer periods. The interleave method or row-by-row folding of a sequence is a popular approach to generate families such as Gordon Mill Welch (GMW) sequences, which are constructed using a shift sequence with good correlation properties. The method of composition (a different approach) also requires a shift sequence and a pseudonoise sequence to construct a new family more related with multidimensional periodic arrays. In this work, we develop new families of binary sequences with good pseudorandom properties based on both the interleave and composition methods, which offer flexible periods and easy implementation. This new construction is based on the generalized Extended Rational Cycle (ERC) construction developed by Rivat and Niederreiter. The results show that for certain parameters the obtained families are close to optimal in terms of family size and correlation.

Costas arrays are fundamental to the operation of radar and sonar systems, yet it is still an open problem how to generate a Costas array for an arbitrary length. A way to improve computer search is to make use of a characterization of the structural properties in order to reduce the search space. In this work, we use techniques from uniform distribution theory to study several structural constraints on Welch and Golomb constructions of Costas arrays. Then, we find bounds on the number of streaks of a given length and their deficiency and test their tightness with several numerical experiments. These results partially answer questions posed by Correll, Jedwab, and Wodlinger.

Families of binary sequences with low correlation are required in applications such as wireless communications, ranging and time delay measurement and digital watermarking, among others. Many constructions have been proposed that employ m-sequences as basic building blocks, such as the Gordon-Mills-Welch (GMW) sequences. In this work we present a unified construction of GMW sequences derived from suitable m-sequences by using the method of composition, producing sequences of length$2^{n}-1$with$n$being an integer composite number. A given m-sequence is folded using the Chinese remainder theorem (CRT) into a two dimensional array, whose columns are either constant or cyclic shifts of a short$m$-sequence. Then, the array can be summarized by a short$m$-sequence and the sequence of shifts (shift sequence). By looking at array interpretation, we avoid using Trace representation of intermediate fields, which makes its implementation more straightforward and secure. Pseudonoise arrays can be produced by constructing all the valid columns and shift sequences, the latter obtained by proper decimations and proper multiplication. Equivalences are removed by selecting a cyclotomic set leader from the degenerate conjugacy class. The window properties of these sequences can be exploited to construct generalized GMW sequence generators for lengths as large as the long codes in GPS i.e.$2^{42}-1$. A similar generalisation of the small Kasami sets can be constructed using this algorithm. The complexity of the algorithms is$\sqrt{L}$where$L$is the length of the sequence, improving known algorithms. Finally, the shift sequences constructed in this work are good candidates to frequency hopping and time hopping sequences in UWB wireless communications and localisation systems.

We build on the work of Drakakis et al. (2011) on the maximal cross-correlation of the families of Welch and Golomb Costas permutations. In particular, we settle some of their conjectures. More precisely, we prove two results. First, for a prime p ≥ 5, the maximal cross-correlation of the family of the φ(p-1) different Welch Costas permutations of {1, . . . , p-1} is (p - 1)/t, where t is the smallest prime divisor of (p - 1)/2 if p is not a safe prime and at most 1 + p1/2otherwise. Here φ denotes Euler's totient function and a prime p is a safe prime if (p - 1)/2 is also prime. Second, for a prime power q ≥ 4 the maximal cross-correlation of a subfamily of Golomb Costas permutations of {1, . . . , q - 2} is (q - 1)/t - 1 if t is the smallest prime divisor of (q - 1)/2 if q is odd and of q - 1 if q is even provided that (q - 1)/2 and q - 1 are not prime, and at most 1 + q1/2otherwise. Note that we consider a smaller family than Drakakis et al. Our family is of size φ(q - 1) whereas there are φ(q - 1)2different Golomb Costas permutations. The maximal cross-correlation of the larger family given in the tables of Drakakis et al. is larger than our bound (for the smaller family) for some q.

In 2012, Diem introduced a new figure of merit for cryptographic sequences called expansion complexity. In this paper, we slightly modify this notion to obtain the so-called irreducible-expansion complexity which is more suitable for certain applications. We analyze both, the classical and the modified expansion complexity. Moreover, we also study the expansion complexity of the explicit inversive congruential generator.

Linear complexity is a measure of how complex a one dimensional sequence can be. In this paper we extend the concept of linear complexity to multiple dimensions and present a definition that is invariant under well-orderings of the arrays. As a result we find that our new definition for the process introduced in the patent titled “Digital Watermarking” produces arrays with good asymptotic properties.

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