跳至內容

置換同餘生成器

維基百科，自由的百科全書

置換同餘生成器，簡稱PCG（英語：Permuted congruential generator）是一個用於產生偽隨機數的算法，開發於2014年。該算法在線性同餘生成器（LCG）的基礎上增加了輸出置換函數（output permutation function），以此優化LCG算法的統計性能。因此，PCG算法在擁有出色的統計性能的同時[1][2]，也擁有LCG算法代碼小、速度快、狀態小的特性。[3]

置換同餘生成器（PCG）和線性同餘生成器（LCG）的差別有三點，在於：

  1. LCG的模數以及狀態大小比較大，狀態大小一般為輸出大小的二倍。
  2. PCG的核心使用2的N次冪作為模數，以此實現一個非常高效的全周期、無偏差的偽隨機數生成器。
  3. PCG的狀態不會被直接輸出，而是經過輸出置換函數計算後才輸出。

使用2的N次冪作為模數的LCG算法，普遍出現輸出低位周期短小的問題，而PCG通過輸出置換函數解決了這個問題。

種類

[編輯]

PCG算法由兩個部分組成：狀態轉換函數以及輸出置換函數，其中輸出置換函數可以根據使用場景進行改變。PCG因此屬於一個算法家族，每個分支的不同之處在於其使用的輸出置換函數。

狀態轉換函數定義為大小介於8位至128位的LCG算法，但是被真正推薦應用的只有64位和128位的版本，其餘的僅作該PCG算法的統計測試使用。LCG算法中的增量可以更改成任意奇數，以此產生不同的流。又因為增量是任意的，將生成器狀態的地址的最低位設為1後（即地址 OR 1），該地址亦可作為增量使用。[4]

PCG算法亦定義了數種輸出置換函數。這些函數都表現良好，但是一些函數展示的性能更為優秀。[3]:39這些函數由以下部件合併而成：

  • RR（random rotation）：隨機（依賴於輸入）旋轉，輸出大小為輸入大小的一半。給定一個 2b 位的輸入數字，最高的 b-1 位用於循環移位量，將輸入的下半部分位向右循環移位，並將循環後的結果輸出，而最低的 2b-1+1-b 位則被丟棄。
  • RS（random shift）：隨機（依賴於輸入）移位，適用於循環移位成本更高的場景。同上，輸出是輸入大小的一半。從 2b 位輸入開始，前 b-3 位用於移位量，該移位量應用於接下來的 2b-1+2b-3-1 位，並將最終結果的下半部分輸出，而最低的 2b-1-2b-3-b+4 位則被丟棄。
  • XSH（xorshift）：相當於x ^= x >> 常数。選擇的常數為下一個操作沒有丟棄的位的一半（向下取整）。
  • XSL：XSH的簡化版本，將輸入的上半部分與下半部分進行異或操作。產生的值將會用於後續的循環移位操作。
  • RXS（random xorshift）：類似於XSH，但使用一個隨機（依賴於輸入）的移位量。
  • M（multiply）：將輸入乘以一個固定常數。

這些部件被組合成以下（受推薦的）置換輸出函數，此處以這些組合最常見的輸入與輸出大小進行說明：

  • XSH-RR：
    (64位→32位) count = (int)(x >> 59); x ^= x >> 18; return rotr32((uint32_t)(x >> 27), count);
  • XSH-RS：
    (64位→32位) count = (int)(x >> 61); x ^= x >> 22; return (uint32_t)(x >> (29 - count));
  • XSL-RR：XSH-RR的簡化版，屬於提供給使用2個64位數字模擬128位運算的64位計算機的優化。
    (128位→64位) count = (int)(x >> 122); x64 = (uint64_t)(x ^ (x >> 64)); return rotr64(x64, count);
  • RXS-M-XS：當輸出為輸入大小的一半時，這個是最慢也是性能最強的輸出函數。但若按照其預期使用場景使用該函數，即輸出與輸入大小一致時，這個函數則是最弱的輸出函數。在狀態大小必須是32位或64位的場景下使用。
    (32位→32位) count=(int)(x >> 28); x ^= x >> (4 + count); x *= 277803737u; return x ^ (x >> 22);
    (64位→64位) count=(int)(x >> 59); x ^= x >> (5 + count); x *= 12605985483714917081u; return x ^ (x >> 43);
  • XSL-RR-RR：同上，這個輸出函數的輸入與輸出大小一致，以提供128位的偽隨機數。
    (128位→128位) count = (int)(x >> 122); low64 = rotr64((uint64_t)(x ^ (x >> 64)), count); high64 = rotr64((uint64_t)(x >> 64), low64 & 63); return (uint128_t)high64 << 64 | low64;

由於以上這些輸出轉換的每一個步驟都是可逆的，又或者是截尾性質的，所以它們可以確保皆是一一對應的雙射函數。因此，它們的複合函數能夠將一定數量的輸入值，映射到不同的輸出值上，以此保留了LCG算法的均衡分布特性。

最後，如果所需要的循環周期超過 2128，實現者可以使用子生成器陣列來擴展生成器。每次從這個陣列中輪流抽選一個子生成器，將其輸出與主生成器輸出相加，形成最終輸出。每當主生成器的狀態達到零時，子生成器陣列會被進行循環，使循環周期相對總狀態大小呈指數級增長。

代碼範例

[編輯]

推薦並且適用於大多數用戶的生成器，是具有64位狀態和32位輸出的 PCG-XSH-RR 生成器。[3]:43它可以通過以下方式實現： 

#include <stdint.h>
static uint64_t       state      = 0x4d595df4d0f33173;		// 生成器的状态，初始值可以根据种子进行改变
static uint64_t const multiplier = 6364136223846793005u;    // 状态转换函数——线性同余方法（LCG）的乘数
static uint64_t const increment  = 1442695040888963407u;	// 线性同余方法（LCG）的增量，可以是任意奇数

// 循环移位函数
static uint32_t rotr32(uint32_t x, unsigned r)
{
	return x >> r | x << (-r & 31);
}

// 使用PCG生成器生成伪随机数
uint32_t pcg32(void)
{
	uint64_t x = state;
	unsigned count = (unsigned)(x >> 59);		// 59 = 64 - 5

	state = x * multiplier + increment;
	x ^= x >> 18;								// 18 = (64 - 27)/2
	return rotr32((uint32_t)(x >> 27), count);	// 27 = 32 - 5
}

// 使用提供的种子值初始化生成器
void pcg32_init(uint64_t seed)
{
	state = seed + increment;
	(void)pcg32();
}

範例中的生成器為了促進處理器的指令級並行，以提高該生成器在現代超純量處理器上的性能，選擇了將初始狀態作為輸出函數的輸入，而非其最終狀態（即狀態轉換函數執行後的狀態）。

此外，還有一個稍微更快的版本，剔除了LCG算法中的增量，使其狀態轉換函數成為萊默生成器的一種變體，並且使用了性能更弱的XSH-RS輸出函數。其循環周期僅為上述範例的四分之一： 

static uint64_t mcg_state = 0xcafef00dd15ea5e5u;	// 必须是奇数

uint32_t pcg32_fast(void)
{
	uint64_t x = mcg_state;
	unsigned count = (unsigned)(x >> 61);	// 61 = 64 - 3

	mcg_state = x * multiplier;
	x ^= x >> 22;
	return (uint32_t)(x >> (22 + count));	// 22 = 32 - 3 - 7
}

void pcg32_fast_init(uint64_t seed)
{
	mcg_state = 2*seed + 1;
	(void)pcg32_fast();
}

儘管如此，由於這個算法依舊保留了性能開銷最大的64位×64位乘法，其增加的性能並不多，因此第二個範例內的生成器只應在極端場景下使用。

在 32 位處理器上執行時，以上所有代碼範例都必然會使用三個 32×32→64 位的乘法運算來實現 64×64 位乘法。 為了將這個運算減少到兩個，可以使用一些性能幾乎與 64 位乘數一樣好的 32 位乘數，例如 0xf13283ad[4]、0xffffffff0e703b65 或 0xf2fc5985。

對比其它偽隨機數生成器

[編輯]

BigCrush測試通過獲取足夠的數據，來發現235或以下的循環周期。即便是理論最佳的偽隨機數生成器，也至少需要36位的狀態才能通過該測試。有些非常差的偽隨機數生成方法可以依賴使用極大的狀態大小來通過該測試，但是這項測試可以側面反映出這些算法的質量，生成器通過測試所需要的狀態越小越好。[5]

PCG-RXS-M-XS算法（32位輸出）最低使用36位的狀態大小便能通過BigCrush測試，而PCG-XSH-RR （以上範例中的pcg32()）需要39位，PCG-XSH-RS （範例中的pcg32_fast()）需要49位才能通過該測試。作為對比，PCG算法的常見另類選擇xorshift*算法需要40位的狀態，而梅森旋轉算法即便狀態為19937位亦無法通過該測試。[6]

預測性與種子可恢復性

[編輯]

有研究已經表明，在給定 512 個連續輸出字節的情況下，通過大量計算恢復偽隨機生成器的種子是實際可行的。這意味著攻擊者實際上可以通過512位元組的偽隨機流，預測該流接下來會生成的隨機數。[7]

參考

[編輯]
  1. ^ Lemire, Daniel. Testing non-cryptographic random number generators: my results. 22 August 2017 [2017-10-03]. （原始內容存檔於2021-08-29）. 
  2. ^ Cook, John D. Testing the PCG random number generator. 7 July 2017 [2017-10-03]. （原始內容存檔於2021-08-29）. 
  3. ^ 3.0 3.1 3.2 O'Neill, Melissa E. PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation (PDF) (技術報告). Harvey Mudd College. 5 September 2014 [2021-08-29]. HMC-CS-2014-0905. （原始內容存檔 (PDF)於2021-12-20）. 
  4. ^ 4.0 4.1 O'Neill, M.E. Critiquing PCG's streams (and SplitMix's too). 10 August 2017 [2017-11-03]. （原始內容存檔於2021-09-16）. 
  5. ^ O'Neill, M.E. Too Big to Fail. 20 August 2017 [2017-11-03]. （原始內容存檔於2022-01-10）. 
  6. ^ L'Ecuyer, Pierre; Simard, Richard. TestU01: A C library for empirical testing of random number generators (PDF). ACM Transactions on Mathematical Software. August 2007, 33 (4): 22-1–22-40 [2021-08-29]. CiteSeerX 10.1.1.499.2830 可免費查閱. doi:10.1145/1268776.1268777. （原始內容存檔 (PDF)於2021-04-28）. 
  7. ^ Bouillaguet, Charles; Martinez, Florette; Sauvage, Julia. Practical seed-recovery for the PCG Pseudo-Random Number Generator. IACR Transactions on Symmetric Cryptology. 28 September 2020, 2020 (3): 175–196. doi:10.13154/tosc.v2020.i3.175-196. 

外部連結

[編輯]
取自「https://wiki.zwnes.eu.org/w/index.php?title=置换同余生成器&oldid=76844414」