Items tagged with modular modular Tagged Items Feed

Answering to that question, I posted several procedures finding minimal polynomials for the elements of finite fields. The best one was the following,

alias(a=RootOf(T^100+T^97+T^96+T^93+T^91+T^89+T^87+T^86+T^82+T^81+T^71+T^70+T^67+T^61+
T^60+T^57+T^54+T^53+T^52+T^49+T^48+T^45+T^44+T^42+T^39+T^36+T^33+T^32+T^31+T^29+T^28+T^27+
T^26+T^24+T^23+T^22+T^18+T^17+T^16+T^14+T^13+T^12+T^10+T^8+T^7+T^6+T^3+T+1)):

F:=GF(2,100,op(a)):
z:=F:-input(2):

MinPolyGF:=proc(x,y:=_X)
local A, i;
A:=Matrix(100,...

As alluded to in my previous post in this series, one of the most straight forward ways to test if a PRNG is generating good random sequences is by examining the frequency of 0's and 1's.  This is just a couple lines in Maple using Statistics:

(**) r1 := rand(0..1):L := [seq(r1(), i=1..10000)]:
(**) n := nops(L); tally := `+`(op(L));
(**) Statistics:-ChiSquareGoodnessOfFitTest(
      [n-tally, tally], [n/2, n/2], ':-output'=':-hypothesis');

Suppose you want to solve a large dense linear system AX=B over the rationals - what should you do? Well, one thing you should probably not do is directly apply Gaussian elimination. It does O(n^3) arithmetic operations, but the size of the numbers blow up, leading to an exponential bit complexity. Don't believe me? Try it:

with(LinearAlgebra):
for N from 5 to 9 do
  A := RandomMatrix(2^N, 2^N+1,generator=-10^5..10^5):
  TIMER := time(GaussianElimination(A...