A note on local randomness in polynomial random number and random function generators (Q884595)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on local randomness in polynomial random number and random function generators |
scientific article |
Statements
A note on local randomness in polynomial random number and random function generators (English)
0 references
6 June 2007
0 references
Let \[ g_j(x)=\begin{cases} f_j(x) + \overline{x} \quad &\text{if }(x,N)=1,\\ x \quad &\text{otherwise}.\end{cases} \] Here \(j=1,\dots,l\), \(f_j\in \mathbb Z[x]\), \(N>3\) is odd and squarefree, \(x\overline{x}\equiv 1\,\text{mod}\,N\), \(1\leq \overline{x}\leq N\). Local randomness of these function families is studied. The results for \((g_1,\dots,g_l)\) are close to the results for \((f_1,\dots,f_l)\) obtained by \textit{H.~Niederreiter} and \textit{C.~P.~Schnorr} [SIAM J.~Comput.~22, No.~4, 684--694 (1993; Zbl 0789.94007)]. The novelty of the work under review consist in the absence of the linear independence condition on \((f_1,\dots,f_l)\) which was required in the cited work, namely, the following condition: for every prime divisor \(p_i\) of \(N\) the polynomials \(f_1,\dots,f_l\) are linearly independent modulo the subspace of polynomials of degree \(\leq 1\) in \(\mathbb Z_{p_i}[x]\).
0 references
local randomness
0 references
hash functions
0 references
cryptographic hash functions
0 references
random function generator
0 references
discrepancy
0 references