Period of the power generator and small values of Carmichael's function期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Period of the power generator and small values of Carmichael's function

Authors:	John B Friedlander Carl Pomerance Igor E Shparlinski

Institution:	Department of Mathematics, University of Toronto, Toronto, Ontario M5S 3G3, Canada ; Department of Fundamental Mathematics, Bell Labs, Murray Hill, New Jersey 07974-0636 ; Department of Computing, Macquarie University, Sydney, New South Wales 2109, Australia

Abstract:	Consider the pseudorandom number generator $\begin{equation}u_n\equiv u_{n-1}^e\pmod{m},\quad 0\le u_n\le m-1,\quad n=1,2,\ldots, \end{equation}$ where we are given the modulus , the initial value $u_0=\vartheta$ and the exponent . One case of particular interest is when the modulus is of the form , where are different primes of the same magnitude. It is known from work of the first and third authors that for moduli , if the period of the sequence exceeds $m^{3/4+\varepsilon}$ , then the sequence is uniformly distributed. We show rigorously that for almost all choices of it is the case that for almost all choices of $\vartheta,e$ , the period of the power generator exceeds $(pl)^{1-\varepsilon}$ . And so, in this case, the power generator is uniformly distributed. We also give some other cryptographic applications, namely, to ruling-out the cycling attack on the RSA cryptosystem and to so-called time-release crypto. The principal tool is an estimate related to the Carmichael function $\lambda(m)$ , the size of the largest cyclic subgroup of the multiplicative group of residues modulo . In particular, we show that for any $\Delta\ge(\log\log N)^3$ , we have $\lambda(m)\ge N\exp(-\Delta)$ for all integers with $1\le m\le N$ , apart from at most $N\exp\left(-0.69\left(\Delta\log \Delta\right)^{1/3}\right)$ exceptions.

Keywords:	Carmichael's function RSA generator Blum--Blum--Shub generator

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

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