基于有限域中的二次特征生成的伪随机二进制格点

本文利用有限域的二次特征与乘法逆构造了大族的伪随机格点,并研究了其密码学性质:伪随机性、碰撞和雪崩效应.     

等分布度与伪随机性检验

本文从熵的角度探讨了伪随机性检验问题，提出了有关序列的等分布度ｒｎ（Ｋ）概念，并证明：一序列｛Ｘｎ｝（０≤ｘｎ≤１）为等分布的充分必要条件是：Ｋ＞１，ｎ→∞ｌｉｍｒｎＫ＝１。利用这一结果对几个典型伪随机序列的等分布度进行了比较，给出了它们的伪随机性优劣排序。     

全部 n 级 M 序列构造方法的计算机实现

<正> 最长 n 级非线性移位寄存器序列简称为 n 级 M 序列,记为(a_0,a_1,…,a_2~n-1),a_i=0或1,它是以2~n 为周期的序列.在序列中连续 n 个元(a_ia_(i+1)…a_(i+n-1))称为状态,n级 M 序列中,全部2~n 个状态两两不同.M 序列具有较好的伪随机性与相关特性,而且数目多,容易保密,因此在通信等工程领域得到了重要应用.例如,M 序列可以在多址通信     

列序的复杂度与相关函数

M 序列因其庞大的数量和良好的伪随机性,在现代通讯等领域中有着广泛的应用.线性复杂度作为 M 序列复杂性的一种主要度量方法,不论在实际应用中还是在理论上,均有较为重要的意义.本文主要讨论了 M 序列的复杂度与相关函数的一些关系.     

一种基于线性同余算法的伪随机数产生器

线性同余算法作为使用最为广泛的伪随机数产生算法,具有产生速度快、输出序列周期长等特点,但安全性能不佳的弱点始终制约着该算法在密码学领域的应用.本文在对线性同余算法详细分析的基础上,给出了一种不受乘数a选择限制的伪随机数产生器.该算法具有良好的伪随机性和安全性.     

M列序的复杂度与相关函数

M序列因其庞大的数量和良好的伪随机性,在现代通讯等领域中有着广泛的应用.线性复杂度作为 M 序列复杂性的一种主要度量方法,不论在实际应用中还是在理论上,均有较为重要的意义.本文主要讨论了 M 序列的复杂度与相关函数的一些关系.     

Q矩阵的结构与有限域上多项式的可约性

<正> 近年来,由移位寄存器所产生的序列在一些实际问题中得到了应用,例如数字通信中的纠错编码、测距等,因此种序列的伪随机性还可用于一些需要随机数的领域,如蒙特卡罗方法等.     

关于拟Koszul模的注记

对于每个诺特半完全代数A上的模M,都有一个谱序列E_（pq）～＊（M）与之相对应.本文证明了有限生成A-模M是拟Koszul的当且仅当谱序列E_（pq）～＊（M）的第E～2层是平凡的.与之对偶,本文叙述了余拟Koszul模情况下的类似结果.     

关于拟Keszul模的注记

对于每个诺特半完全代数A上的模M1都有一个谱序列E*pq(M)与之相对应.本文证明了有限生成A-模M是拟Koszul的当且仅当谱序列E*pq(M)的第E2层是平凡的.与之对偶,本文叙述了余拟Koszul模情况下的类似结果.     

基于谱密度评价随机性

为了评价一个平稳过程的随机性, 我们基于谱密度提出了一个图方法. 当图中的散点呈现线性关系的时候, 我们可以判定这个序列是随机的. 为了说明这个思想, 我们用模拟的办法来检验伪随机数的随机性. 另外, 我们也用了一个实际数据来考察数据的相关性. 这两个例子都说明了我们的图方法是非常有效的.     

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

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

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.     

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.     

On finite pseudorandom sequences of k symbols

In earlier papers C. Mauduit and A. Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences. In [8] they extend this theory to sequences of k symbols: they give the definitions and also construct a “good” pseudorandom sequence of k symbols. In this paper these measures are studied for a “truely random” sequence.     

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.     

Growth along a ray of a subharmonic function,having a mass distributed on the negative axis

Let U be a subharmonic function in C with a Riesz mass , distributed on the negative semiaxis without some neighborhood of zero, let and be its order and lower order, and let B(r, U) be the maximum of U(z) for ¦z¦=r. Estimates are obtained for the measure of sets of those values of r 0 for which certain inequalities hold. The following result is typical. LetE = {r:u(re ^l)–cosB<(r,U) > 0}. If < < 1, ¦¦=., then the lower logarithmic density of the set E is at least 1 – /. If < > 1,¦¦ ., then the upper logarithmic density of the set E is at least 1 – /.Translated from Teoriya Funktsii, Funktsional'nyi Analiz i Ikh Prilozheniya, No. 50, pp. 31–38, 1988.     

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.     

Collision and avalanche effect in families of pseudorandom binary sequences

Recently a constructive theory of pseudorandomness of binary sequences has been developed and many constructions for binary sequences with strong pseudorandom properties have been given. In the applications one usually needs large families of binary sequences of this type. In this paper we adapt the notions of collision and avalanche effect to study these pseudorandom properties of families of binary sequences. We test two of the most important constructions for these pseudorandom properties, and it turns out that one of the two constructions is ideal from this point of view as well, while the other construction does not possess these pseudorandom properties. Communicated by Attila Pethő     

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.     

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.