The iterated Carmichael λ-function and the number of cycles of the power generator

Details The iterated Carmichael λ-function and the number of cycles of the power generator The iterated Carmichael λ-function and the number of cycles of the power generator

2004-06-16

arxiv.org/abs/math/0406335v1

Mathematics

Number Theory

28 pages

Scientific paper

Iteration of the modular l-th power function f(x) = x^l (mod n) provides a common pseudorandom number generator (known as the Blum-Blum-Shub generator when l=2). The period of this pseudorandom number generator is closely related to \lambda(\lambda(n)), where \lambda(n) denotes Carmichael's function, namely the maximal multiplicative order of any integer modulo n. In this paper, we show that for almost all n, the size of \lambda(\lambda(n)) is n/exp((1+o(1))(log log n)^2 log log log n). We conjecture an analogous formula for the k-th iterate of \lambda. We deduce that for almost all n, the psuedorandom number generator described above has at least exp((1+o(1))(log log n)^2 log log log n) disjoint cycles. In addition, we show that this expression is accurate for almost all n under the assumption of the Generalized Riemann Hypothesis for Kummerian fields. We also consider the number of iterations of \lambda it takes to reduce an integer n to 1, proving that this number is less than (1+o(1))(log log n)/log 2 infinitely often and speculating that log log n is the true order of magnitude almost always.

Affiliated with

Also associated with

No associations

Rating

The iterated Carmichael λ-function and the number of cycles of the power generator does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The iterated Carmichael λ-function and the number of cycles of the power generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The iterated Carmichael λ-function and the number of cycles of the power generator will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178290