免費乘以攜帶期

Question

我想弄清楚特定的CMWC僞隨機數發生器的週期是什麼。

維基百科頁面有一些標準MWC和CMWC不同參數週期的例子，但並沒有真正回答這是如何計算的。

是否有一種簡單的方法來計算給定的乘數，r種子數和基數b？

例如，假設我有以下參數（一CMWC）：

b=2^32-1
a=4294966362
r=32

我已經驗證p=a*b^r+1是素數。

編輯：oops，複製了錯誤的值。修正它，所以p現在應該是素數。

Answer 1

我誤解了什麼是需要得到一個完整的週期：

b也必須是p的原根，我不認爲這是這裏的情況（說實話，我不有數學背景甚至開始瞭解什麼是原始根）。如果有一個完整的期限，則該期限將爲a*b^r。據我所知，這是不可能的（或者至少是非常困難的）告訴什麼時期會是另外的（坦率地說，這是沒有用的，因爲實際上需要一整段時間）。

來源：Journal Of Modern Applied Statistical Methods

Answer 2

b是原始根時，其順序是P-1，所以B^K可從1假設的每一個值，以P-1，這取決於k的值。

元素的階數是b^s = 1（mod p）的最小值。對於phi（p）的每個k除數，phi（p）=（p-（p）/ k）= 1（！=意味着不同） 1）是歐拉的總功能（http://en.wikipedia.org/wiki/Euler%27s_totient_function）。

在您的例子：
- 島（P）= A * B^R = P - 1。
- 一個是{1，2，3，31，23091217，4294966362}的除數。
- b的除數是{1,3,5,17,257,65537,4294967295}。 （p-1）= 2 *（3^33）*（5^32）*（17^32）* 31 *（257^32）*（65537^32）* 23091217。
P-1具有322570512個除數（http://en.wikipedia.org/wiki/Divisor_function）

隨着模冪，所以可以看到， b ^（（P-1）/ 3）= 1（mod p） 因此b的順序與p-1不同。

這是每一個除數ķ最好選擇號碼一個和 b很少除數，則P-1也將有少數除數，這將是很容易計算（PHI（P）/ K）。 b的階數將爲min {phi（p）/ k} = min {（p-1）/ k}。

在Marsaglia的文章「關於Pi和其他十進制擴展的隨機性」（http：// interstat。statjournals.net/YEAR/2005/articles/0510005.pdf），有一些a，b和r的值。不完整的時期也是有用的（見文章）。

基數b = 2^32沒有滿週期，但它返回從0到2^32-1的整數。 Base b = 2^32-1不能返回無偏32位整數（它永遠不會返回數字2^31-1 = 4294967295）。