Hull-Dobell Theorem
1269 2022-08-02 23:05
relatively prime 英 [ˈrelətɪvli praɪm]
互质; 互素
prime factors 英 [praɪm ˈfæktəz]
质因数
primitive root 英 [ˈprɪmətɪv ruːt]
原根; 本原根;
common multiple 英 [ˈkɒmən ˈmʌltɪpl]
公倍数;
混合同余的公式
X_{n+1} = (aX_n + c) mod m
定理1:
当c neq 0
1. m和c互质
2. a-1 能被m的所有质因数整除
3. 如果m能被4整除,那么a-1也要能被4整除
定理2:
1. x_0 与m互质
2. a 是p的n次幂的原根,如果p的n次幂是m的因数,并且(p是奇数,并且a尽可能的大),或者并且(p=2并且(a=1或者2))
3. a属于2的(a-2)次幂,如果2的a次幂是一个m的因数,并且a>2. 此外,对于任何m,存在满足这些条件的值,最后,关于素数幂的因数们,最大周期是最小周期的公倍数,(p-1)倍的p的(n-1)次幂或者2的(n-2)次幂,
Hull, T.E.,Dobell, A.R., “Random Number Generators,” SIAM Review,4, 230–254, 1962.
全部评论