Predicting nonlinear pseudorandom number generators期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Predicting nonlinear pseudorandom number generators

Authors:	Simon R Blackburn Domingo Gomez-Perez Jaime Gutierrez Igor E Shparlinski

Institution:	Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, United Kingdom ; Faculty of Science, University of Cantabria, E-39071 Santander, Spain ; Faculty of Science, University of Cantabria, E-39071 Santander, Spain ; Department of Computing, Macquarie University, Sydney, NSW 2109, Australia

Abstract:	Let be a prime and let and be elements of the finite field $\mathbb{F} _p$ of elements. The inversive congruential generator (ICG) is a sequence of pseudorandom numbers defined by the relation $u_{n+1} \equiv a u_n^{-1} + b \bmod p$ . We show that if sufficiently many of the most significant bits of several consecutive values of the ICG are given, one can recover the initial value (even in the case where the coefficients and are not known). We also obtain similar results for the quadratic congruential generator (QCG), $v_{n+1} \equiv f(v_n) \bmod p$ , where $f \in \mathbb{F} _pX]$ . This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), $x_{n+1} \equiv a x_n + b \bmod p$ , but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.

Keywords:

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文

设为首页 | 免责声明 | 关于勤云 | 加入收藏