Construction of pseudorandom binary sequences using additive characters over GF(2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>) II

In a series of papers Mauduit and Sárközy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 ^k ) will be studied.     

More constructions of pseudorandom sequences of k symbols

We present some new constructions of families of pseudorandom sequences of k symbols, which generalize several previous constructions for the binary case.     

Construction of pseudorandom binary sequences using additive characters over GF(2 k )

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences and they constructed sequences with strong pseudorandom properties. In these constructions fields with prime order were used. In this paper a new construction is presented, which is based on finite fields of order 2 ^k .     

Modified constructions of binary sequences using multiplicative inverse

Two new families of finite binary sequences are constructed using multiplicative inverse. The sequences are shown to have strong pseudorandom properties by using some estimates of certain exponential sums over finite fields. The constructions can be implemented fast since multiplicative inverse over finite fields can be computed in polynomial time.     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

合数模上的伪随机二进制数列

设m为"RSA"类型的模,即m为两个大小差不多的素数的乘积:m=pqp,q为素数,p相似文献   

The study of collision and avalanche effect in a family of pseudorandom binary sequences

In an earlier paper we studied collisions and avalanche effect in two of the most important constructions given for large families of binary sequences possessing strong pseudorandom properties. It turned out that one of the two constructions (which is based on the use of the Legendre symbol) is ideal from this point of view, while the other construction (which is based on the size of the modulo p residue of f(n) for some polynomial f(x) ∈ $ \mathbb{F}_p $ \mathbb{F}_p [x]) is not satisfactory since there are “many” collisions in it. Here it is shown that this weakness of the second construction can be corrected: one can take a subfamily of the given family which is just slightly smaller and collision free.     

On a family of pseudorandom binary sequences

Recently, numerous constructions have been given for finite pseudorandom binary sequences. However, in many applications, e.g., in cryptography one needs large families of good pseudorandom sequences. Very Recently L.~Goubin, C.~Mauduit, A.~Sárkzy succeeded in constructing large families of pseudorandom binary sequences based on the Legendre symbol. In this paper we will generate another type of large family of pseudorandom sequences by using the notion of index (discrete logarithm).     

A note on certain modular constructions of pseudorandom binary sequences with composite moduli

J. Rivat and A. Sárközy extended two large families of pseudorandom binary sequences to the case of composite moduli m, where m is the product of two different primes not far apart. In this paper we continue the study in this direction. We shall improve the estimates for the correlation measure of the sequences.     

Construction of large families of pseudorandom binary sequences

Oon constructed large families of finite binary sequences with strong pseudorandom properties by using Dirichlet characters of large order. In this paper Oon’s construction is generalized and extended. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol.      

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

On p-pseudorandom binary sequences

The pseudorandom properties of finite binary sequences have been studied recently intensively. In the papers written on this subject the two distinct elements of the sequences are chosen equally with probability 1/2. In this paper the authors extend the work to the more general case when the two elements are chosen with probability p, resp. 1-p. This revised version was published online in August 2006 with corrections to the Cover Date.     

Construction of large families of pseudorandom binary sequences

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences. They showed that the Legendre symbol forms a “good” pseudorandom sequence, and they also tested other sequences for pseudorandomness, however, no large family of “good” pseudorandom sequences has been found yet.In this paper, a large family of this type is constructed by extending the earlier Legendre symbol construction.     

On the pseudorandomness of binary and quaternary sequences linked by the gray mapping

Binary and quaternary sequences are the most important sequences in view of many practical applications. Any quaternary sequence can be decomposed into two binary sequences and any two binary sequences can be combined into a quaternary sequence using the Gray mapping. We analyze the relation between the measures of pseudorandomness for the two binary sequences and the measures for the corresponding quaternary sequences, which were both introduced by Mauduit and Sárközy. Our results show that each ‘pseudorandom’ quaternary sequence corresponds to two ‘pseudorandom’ binary sequences which are ‘uncorrelated’.     

Concatenation of pseudorandom binary sequences

In the applications it may occur that our initial pseudorandom binary sequence turns out to be not long enough, thus we have to take the concatenation or merging of it with other pseudorandom binary sequences. Here our goal is study when we can form the concatenation of several pseudorandom binary sequences belonging to a given family? We introduce and study new measures which can be used for answering this question.     

Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

We describe a polynomial time algorithm to compute Jacobi symbols of exponentially large integers of special form, including so-called sparse integers which are exponentially large integers with only polynomially many nonzero binary digits. In a number of papers sequences of Jacobi symbols have been proposed as generators of cryptographically secure pseudorandom bits. Our algorithm allows us to use much larger moduli in such constructions. We also use our algorithm to design a probabilistic polynomial time test which decides if a given integer of the aforementioned type is a perfect square (assuming the Extended Riemann Hypothesis). We also obtain analogues of these results for polynomials over finite fields. Moreover, in this case the perfect square testing algorithm is unconditional. These results can be compared with many known NP-hardness results for some natural problems on sparse integers and polynomials.     

On pseudorandom properties of some Dirichlet characters

In this paper, we try to generalize the Mauduit–Sárközy pseudorandom properties of the Legendre symbol to Dirichlet characters. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol. Furthermore we provide with sufficient conditions to ensure the coincidence of two binary sequences using the Legendre symbol.     

Construction of pseudorandom binary lattices based on multiplicative characters

In this paper a large family of pseudorandom binary lattices is constructed by using the multiplicative characters of finite fields. This construction generalizes several one-dimensional constructions to arbitrary dimensions.     

Modular constructions of pseudorandom binary sequences with composite moduli

Summary Recently, Goubin, Mauduit, Rivat and Sárk?zy have given three constructions for large families of binary sequences. In each of these constructions the sequence is defined by modulo <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"3"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"4"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"5"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"6"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"7"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"8"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"9"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>p$ congruences where $p$ is a prime number. In this paper the three constructions are extended to the case when the modulus is of the form $pq$ where $p$, $q$ are two distinct primes not far apart (note that the well-known Blum-Blum-Shub and RSA constructions for pseudorandom sequences are also of this type). It is shown that these modulo $pq$ constructions also have certain strong pseudorandom properties but, e.g., the (``long range') correlation of order $4$ is large (similar phenomenon may occur in other modulo $pq$ constructions as well).     

On finite pseudorandom lattices of k symbols

In earlier papers Mauduit and Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences and sequences of k symbols. Later they (with further coauthors) extended the notation of binary sequences to binary lattices. In this paper measures of pseudorandom lattices of k symbols are introduced and studied for “truly random” lattices.