§4.1 — period of the base-b digits of k/m
ProvedCarryRNG.SWB.expansion_period_eq_orderOfnumber-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-expansionrandom-number-generationsubtract-with-borrow
Let and be integers relatively prime to one another. Let be relatively prime to , and let be the th base- digit of . For every positive integer ,
Consequently the least positive digit period is the multiplicative order of modulo . This supplies the number-theoretic period used for the generator.
Preamble
import Definitions.Def_CarryRNG_AWC_digit
Formal statement
namespace CarryRNG.SWB
/-- Section 4.1: the least positive period of the digits of `k/m` is the order of `b` mod `m`. -/
theorem expansion_period_eq_orderOf (b m k p : ℕ) (hb : 2 ≤ b) (hm : 1 < m)
(hk : 0 < k ∧ k < m) (hkm : Nat.Coprime k m) (hbm : Nat.Coprime b m)
(hp : 0 < p) :
(∀ j : ℕ, 1 ≤ j → CarryRNG.AWC.digit b m k (j + p) = CarryRNG.AWC.digit b m k j) ↔
orderOf (b : ZMod m) ∣ p := by sorry
end CarryRNG.SWB
Source
G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), p. 467, Section 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.