Hull-Dobell Theorem

930 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.

博客