无k次幂因子数的伪随机性

摘要

集合{1,2,…,N}的伪随机子集在密码学中有广泛的应用.Cécile Dartyge和AndrásSárk(o)zy运用筛法证明了集合{1,2,…,N}中无平方因子数构成的子集不是一个好的伪随机子集.研究集合{1,2,…,N}中无k次幂因子数构成的子集Qk(N),并对应地定义了序列EN(Qk(N))=(e1,e2,…,eN),其中qN=card Qk(N) /N,en={1-qN如果n为无k次幂因子数；-qN,其他.进而通过讨论序列EN(Qk(N))的伪随机测度,证明子集Qk(N)同样没有好的伪随机性.