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));
参考: