読者です 読者をやめる 読者になる 読者になる

XorShiftの一例が周期最長になることを確かめるPari/GPプログラム

XorShiftと呼ばれる疑似乱数のうち状態ベクトルが64ビットである例を一つとり、これが最長の周期2^64-1を達することを確認する。

\\ determine that order of g equals to n
isprimitive(g, n, e=1) = {
  my(factors, p);
  if (g^n != e, return(0));
  factors = factor(n);
  for (i = 1, matsize(factors)[1],
    p = factors[i, 1];
    if (g^(n/p) == e, return(0)));
  return(1);
}
\\ identity matrix
E = matid;
\\ right & left shift matrix
R(n, k) = { return(matrix(n, n, i, j, i + k == j)); }
L(n, k) = { return(R(n, -k)); }
\\ convert to matrix on F_2
to_f2(mat) = { return(matrix(matsize(mat)[1], matsize(mat)[2], i, j, Mod(mat[i, j], 2))); }

n = 64;
T = to_f2((E(n) + L(n, 17)) * (E(n) + R(n, 7)) * (E(n) + L(n, 13)));
print(isprimitive(Mod(x, charpoly(T, x)), 2^n - 1));

参考: