科研之友
微信
新浪微博
Facebook
分享链接
摘要
We study two functionals of a random matrix A with independent elements uniformly distributed over the cyclic group of integers {0, 1, ... , M - 1) modulo M. One of them, V-0(A) with mean mu, gives the total number of solutions for a generalised birthday problem, and the other, W (A) with mean lambda, gives the number of solutions detected by Wagner's tree based algorithm. We establish two limit theorems. Theorem 2.1 describes an asymptotical behaviour of the ratio lambda/mu, as M -> infinity. Theorem 2.2 gives bounds for the total variation distance between Poisson distribution and distributions of V-0 and W.
- 出版日期2015-12
