Hull-Dobell Theorem

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

全部评论

·