April 2016 - mathfun@mailman.xmission.com

[math-fun] matrix multiply over GF(2) -- yet another machine instruction we wish we had
by Warren D Smith 02 Apr '16

02 Apr '16

Be nice if one could create an NxN bit-matrix (for example N=machine's wordsize) and then multiply it (mod 2) by an N-element bit vector (e.g machine word) in 1 instruction. This would help with cryptography, error correcting codes, and probably a lot of other stuff. Just saying. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

5 5

[math-fun] perm polys over GF(5), GF(7)
by Henry Baker 01 Apr '16

01 Apr '16

[I'm impressed by the amount of algebra that Dickson had to do by hand in the 1890's.] The only perm polys over GF(5) are: x*{1, x^2, x^2-2x-2, x^2+2x-2, x^2-x+2, x^2+x+2} and linear (a*x+b) functions of these. This makes sense, as there are 5 choices for b, 4 choices for a, and 6=3*2 choices for the non-x factor. There are 120 monic perm polys over GF(7) with an "x" factor; once again, this makes sense, as there are 7 choices for b and 6 choices for a when you do linear (a*x+b) functions of these. Many of these 120 factors are irreducible quartics, many have an irreducible cubic times another factor of "x", etc. There are also six factors which are squares of irreducible quadratics: (x^2-3x-1)^2, (x^2+3x-1)^2, (x^2-2x-2)^2, (x^2+2x-2)^2, (x^2-x+3)^2, (x^2+x+3)^2 None of these 120 factors seems to be a perm poly by itself.

1 0

[math-fun] true random generators based on iterating map, analog electrical
by Warren D Smith 01 Apr '16

01 Apr '16

My idea for that, which I had since the 1990s, was also thought of by: TonI Stojanovski, Johnny Pihl, Ljupco Kocarev: IEEE Trans Circuits & Systems 48,3 (2001) 281-288 & 382-385. They iterate a map which is (approximately) a 2-piece piecewise linear function with one discontinuous jump. They provide a plot of the function. They had conducted an exhaustive search over a 3D parameter space to find the best function of their form, where "best" for them basically meant "most likely to keep working after parameters perturbed." They also give a circuit diagram with 29 MOSFETs, 2 resistors, and 2 capacitors which computes and iterates function. They implemented it on a chip using 0.8-micron CMOS process. It appears to work and generates 1 million true-random bits per second. Looks like they did a pretty good job. I had actually considered maps of their form but dismissed them as too dangerously likely to fall into an attracting fixed point or 2-cycle. Their plot shows they avoid that fate, but not by much -- perturbing their plot a little would break their generator. I meanwhile had preferred piecewise linear maps with 3 pieces and no discontinuities -- those seemed more robust -- but I had not searched for the best parameter set. Their bits of course are going to be biased and correlated, but the correlations should fall off exponentially with time-separation. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0