前一陣子我遇到一個需求是這樣:我們需要給予客戶一個具有唯一性、可閱讀、長度不要太長的編號,以便客戶聯絡客服的時候可以用編號來確認身份,但是我們不希望這個編號是單純的流水號(因為我們不想從這個號碼上暴露出我們當前大概有多少客戶),可是同時我們也不想使用純粹的亂數,因為純粹亂數沒辦法兼顧碰撞機率跟長度(我們又不希望編號太長,又不希望隨著客戶增加而逐漸開始出現編號碰撞、導致我們越來越難取得可用的新編號)。我們希望的,是把固定位數的數字一對一地映射到看似亂數的相同長度數字之上。

要解決這個需求剛好可以用上我老本行的數論專長。一個很簡單可以產生看似亂數的數字的方法就是利用原根;簡單來說,一個自然數 m 的原根 r 是一個使得 r^1, r^2, ..., r^{\varphi(m)} \pmod{m} 都不相同的數字,其中 \varphi(m)Euler 函數。如果 m 是一個質數 p,那麼此時有 \varphi(p)=p-1,於是 r^1, ..., r^{p-1} \pmod{p} 就會不重複地對應到 1,2,...,p-1 之上,而且這裡頭的對應關係至少用眼睛看是看不太出來個所以然的 1。舉例來說,p=9973 是一個質數,我選 r=151 是它的一個原根,此時 r 的次方會是

151, 2855, 2266, 3084, 6926, 8634, 7244, 6787, 7591, 9319,\\
976, 7754, 4013, 7583, 8111, 8055, 9572, 9260, 2040, 8850,...,

這乍看之下是沒什麼規律性的。由於 9973 是最大的四位數質數,這樣產生的結果會不重複地涵蓋 1,2, ...,9972 的每一個數字,所以這可以當作是一個四位偽亂數(亦即看似亂數但其實不是亂數)的產生器。當然,如此一來最後的 9973, ..., 9999 幾個數字就用不到了,但是在實務上不差那最後幾個。

OK,到目前為止還很簡單,但是我遇到的需求還不只是這樣。除了客戶之外,廠商也需要編號,商品也需要編號……而且都需要用這樣的亂數,且還不希望它們的編號產生的邏輯是一樣的。換句話說,我的偽亂數產生器還必須要可以指定一個自訂的種子來產生不同的組合。我事後翻閱了一些既有的文章,有提到一種可能的作法是把公式 r^n\pmod p 改成 sr^n\pmod p,其中 s 是指定的種子,但是這樣做其實只是把對應的順序挪了一下而已:因為到頭來我的 s 其實也會等於是某個 r^t \pmod p,所以 sr^n \equiv r^{n+t}\pmod p,變成整個亂數生成的序列挪移了 t 個位置之後就會出現一樣的模式了。

這點我自己老早就評估到了,所以一開始我就想到應該要能夠針對不同的種子去產生不同的原根 r,使得產生出來的亂數序列完全沒有相似性才行。然而,一般而言即使要確認一個給定的 r 是不是給定的質數 p 的原根其實有一點小麻煩:或著我們暴力去列舉 r^1, ..., r^{p-1} \pmod{p} 看看有沒有重複,或著我們必須要對 \varphi(p)=p-1 作因數分解、然後去檢查看看是否 r 對於那些因數的次方會變成是 1\pmod p(因為對於任何的 r\not\equiv 0\pmod p,它的最小方次一定是 \varphi(p) 的因數)。但是這兩個作法要寫演算法都有一點煩。

此時有一個簡單得很多的辦法,就是限定我們的 p 是一個安全質數,也就是型如 2q+1、其中 q 也是質數的質數。此時因為 \varphi(p)=2q、其真因數只有 1,2,q 三個,所以我們要檢查 r 是不是原根只要確定 r\not\equiv 0,\pm 1\pmod p 而且 r^q\not\equiv 1\pmod p 就是了。不僅如此,很容易證明,此時如果給定的 s\not\equiv 0,\pm 1\pmod p 不是原根,那麼 -s 一定是原根(可以參見這裡),所以對於安全質數我們可以非常容易地輸入幾乎任意的種子 s 去產生原根。

這麼一來,為了方便產生指定位數的偽亂數,我只要預先把指定位數底下最大的安全質數寫死在程式碼裡面就好了。奇妙的是,截至這篇文章寫成為止,這個數列竟然沒有被收錄在 OEIS 裡面,難道之前沒有人特別注意到這個應用價值嗎?總之我自己算了前 18 項如下:

7, 83, 983, 9887, 99839,\\
999595, 9999047, 99998819, 999999503, 9999998783,\\
99999999647, 999999999959, 9999999999659, 99999999995927, 999999999994883,\\
9999999999996047, 99999999999994727, 999999999999999863,...

大致就是這樣;最後再補充今天遇到的一個小需求。在一個特別的情境之中,我們希望別人即使知道我們採用的偽亂數演算法、而且拿到了相鄰項的偽亂數,也沒辦法推算出我使用的種子、或是接下來的偽亂數是啥。這個需求光用前面的演算法當然達不到,因為一旦拿到了相鄰項,一除就知道我的原根了。

但是解決的方法也異常簡單;算兩次就好了:

f(n):=r^n \pmod p\\
g(n):=f(f(n))

如此一來,即使有人拿到相鄰的 g(n),g(n+1),... 也不可能有辦法簡單推算出再來會出現什麼了。


  1. 我事後查到,這種偽亂數產生器基本上就是 Lehmer 亂數產生器(又稱為 Park-Miller 亂數產生器)的一種特例,其中一個很有名的特例是取 p=2^{31}-1, r=16807(即一些程式語言內建的 MINSTD)。 

分享此頁至:
最後修改日期: 2020/06/11

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。