Node:ICG, Next:LCG, Previous:EICG, Up:Definitions

ICG (inversive congruential generator)

• Definition:
  

  y_n = a * inv(y_{n-1}) + b (mod p)    n > 0
  

• Name (as given to prng_new): "icg(p,a,b,y_0)"
• Properties:
  • Period length = p. (for suitable parameters)
  • Strong non-linear properties. (e.g. no lattice)
  • Parameter selection not sensitive.
  • prng_is_congruential is TRUE.
  • prng_can_seed is TRUE.
    The parameter of prng_seed will be used as y_{n-1} in the next call to get_next.
  • prng_can_fast_sub and prng_can_fast_con are FALSE.
• Parameter selection: To ensure that the period length is p, a and b must be chosen in a way that x^2 - bx -a (\in F_p[x]) is a primitive polynomial over F_p.

  If ICG(p,a,1) has period length p, then ICG(p,a*c^2,c) will have period length p, too. For recommended parameters see Table_ICG.

• Introduced in: Eichenauer, J. and J. Lehn. "A non-linear congruential pseudo random number generator", Stat. Papers 27:315-326, 1986