March 2016 - mathfun@mailman.xmission.com

[math-fun] Simpler provably random PRNG, and general conjecture about provably random PRNGs
by Warren D Smith 20 Mar '16

20 Mar '16

The Blum-Blum-Shub psu-random generator is this: x := x^2 mod M, then output LeastSignifBit(x) where M=p*q, with p<q both primes which both are 3 mod 4. The initial x must be relatively prime to M and not 1. It is "provably random" in the sense that if you wanted to "go backwards in time" to guess the random bit for the timestep 1 before the first bit you'd seen, then that would be impossible for you to do, for any guess correctness chance 0.5+epsilon, unless you did computation at least as hard as factoring M. (Here I am assuming you know M, but do not know p and q.) In other words this psu-random bit generator is immune to every statistical test that does less than Factoring(M) worth of computation. This also works if M is a product of any number (>=2) of distinct primes that are 3 mod 4, but it usually is presumed that M is hardest to factor if it has only 2 prime factors, in which case nobody cares. OK, I now make a very simple, but apparently new, remark. Just iterate y := y^2 mod p and z := z^2 mod q and then LeastSignifBit(x) at any time, equals the XOR of the LeastSignifBits of y and of z at that time. Because: if x were constructed by chinese remaindering y and z, that'd happen. Cool moral: This tells us that just by XORing two bitstreams that by themselves would fail randomness tests, we can make something immune to all efficient tests. So we might now CONJECTURE that if K different psu-random bitstreams are XORred together (all unrelated and with relatively prime periods) then in general there is going to be no statistical test that kills it, that is more efficient than brute force trial of all possibilities for the states of K-1 of the generators, then applying some test which breaks the final generator given that the other K-1 are known. I admit that conjecture is vaguely stated... and maybe too strong... But: here is something concrete. Suppose I give you three circular lists of the first N bits of pi, of e, and of EulerGamma. I then perform a secret circular shift of each of the 3 lists, and then output their XOR: N bits of output. Tell me: could you then detect anything nonrandom about those N bits, in any faster than quadratic(N) expected time? I do not see how... Therefore, I conjecture that if you XOR the outputs of three different psu-random generators of periods P1, P2, P3 and secret initial states, then "unless they were related or crappy" no statistical test will be able to tell the result is nonrandom, unless it does at least P1*P2*P3/max(P1,P2,P3) expected computation. This conjecture will really kick butt re the current world of crypto and PRNGs, if true. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Characterizing polys which permute GF(p)
by Henry Baker 20 Mar '16

20 Mar '16

So Dickson worked on this problem in 1896 ! I'll have to track down his work. Thanks very much, Victor -- I thought there might be some literature on this problem, but I didn't know what to search for. I guessed correctly that other people also called them "permutation polynomials". At 06:46 PM 3/19/2016, Victor Miller wrote: >My former colleague, Mike Zieve (now a professor at MIchigan) has written a >number of papers about permutation polynomials, the latest is >http://arxiv.org/pdf/1312.1325.pdf . It gives a lot of references to known >results and to his previous work.

4 4

[math-fun] NYTimes: Wave-piloting the Pacific w/o GPS
by Henry Baker 20 Mar '16

20 Mar '16

FYI -- http://www.nytimes.com/2016/03/20/magazine/the-secrets-of-the-wave-pilots.h… Apparently, ocean wave patterns can be seen & felt & used for navigating the Pacific. Humans have apparently been doing it for 60,000 years.

1 0

Re: [math-fun] Characterizing polys which permute GF(p)
by Warren D Smith 20 Mar '16

20 Mar '16

RCS: The function S(x) = (x-1)^(p-1) - x^(p-1) + x in GF(p) swaps 0 and 1, and fixes the other residues. WDS: Verify directly for 0 and 1; use Lagrange theorem that x^(p-1)=1 if x>0 for all other x mod p. Check. RCS: For the other group generator, either A(x) = x+1, or G(x) = gx with g a primitive root may be used. Composing these in all possible ways, while reducing mod x^p-x, generates the permutations. WDS: correct: x+1 is the p-cycle, and the 01 swap is then all you need to generate every permutation. The reduction modulo x^p-x causes the reduced polynomial to have degree<p. RCS: For higher degree extensions GF[p^e], A is no longer a single loop, but G is still a single loop, WDS: this cyclic-multiplicative-group fact is a theorem by E.Galois. Proofs are available in 1 Andre Weil: Basic number theory, on page 2, can read this page online here http://www.amazon.com/Basic-Number-Theory-Classics-Mathematics/dp/3540586555 2 J-P. Serre: A course in arithmetic, 3 Loo-Keng Hua: Introduction to number theory However: A. I disagree with RCS: though g must be from the extension field. Actually, g is a plain old field element, and Weil proves that. B. And the loop is among the q-1 NONZERO elements of GF(q), where q=p^e, not ALL elements like for x+1 if q prime. So it really is "a single loop plus an isolani." However, using S(x-K) rather than S(x) swaps K and K+1. Therefore, we can by composing S(x-K) and g*x in all possible ways reducing modulo x^p-x as RCS says, generate all permutations of the nonzero elements of GF(q). We then can also swap 0 with 1 using S(x)... which enables seeing that all permutations of the whole kaboodle, are accessible. RCS: The exponents in S become p^e-1, and the mod polynomial becomes x^p^e - x. Returning to GF[p]: If you add a third generator, L(x) = x + 1 - x^(p-1), which maps 0->1 and everything else to self, thereby losing some information, you can generate all the maps from GF[p]->GF[p]. These are 1-1 with the polynomials of degree < p. Similarly for GF[p^e]. WDS: it was anyhow obvious that the polynomials of degree<q generate all maps if GF(q) to self, by use of Lagrange interpolation. It seems to me this whole short post by RCS, is brilliantly simple, and (after my slight corrections) totally characterizes and constructs all permutation polynomials over all finite fields. However, there still is this criticism: what if I want the perm polynomials which work REGARDLESS of the value of q? RCS's generation method sort of handles each GF(q) by itself, it does not handle all of them in a unified way. So for example, the fact that x^k is a permutation polynomial in GF(q) if GCD(k,q-1)=1, which is fairly obvious from Galois' theorem, is not so obvious from RCS's construction (is it?). Is there a way to overcome this criticism? And by the way, to mention the obvious, see https://en.wikipedia.org/wiki/Permutation_polynomial which also gives the following beautiful characterization of the perm polynomials over the ring Z mod p^e: F(x) is a perm polynomial if and only if 1. it permutes Z mod p, and 2. F'(x) is nonzero for every ring element x. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 4

[math-fun] Salmon paper on PRNGs
by Warren D Smith 20 Mar '16

20 Mar '16

The random-gen paper LeBrun mentioned is here http://www.thesalmons.org/john/random123/papers/random123sc11.pdf Nothing is inherently wrong with their philosophy of F[0], F[1], F[2], etc rather than F[0], F[F[0]], F[F[F[0]]] etc, but it is just moronic to go as far as they do in literally adding 1 then re-encypt. Instead, adding a better constant than 1, such as 93db2dffa70bac57 mod 2^64, which has the property that 93db2dffa70bac57 / 2^64 has all partial quotients 1 or 2 in continued fraction, would be equally fast, more random. And the source code Salmon et al distribute is very long and hairy. And presumably best is to use a mildly-decent randgen of the F[F[F[]]] type combined with a mildly-decent post-encrypt of their type, to get the best of both worlds. Which actually, is exactly what Melissa O'Neill does. Part of the problem is the incredible asininity of most (all?) programming languages in refusing to give you the mullo(a,b) and mulhi(a,b) primitives for double=single*single multiply. Seriously. This is the year 2016. Why haven't programming language designers figured out yet, that computer hardware can multiply? Will it happen before I die?

2 1

Re: [math-fun] the 26720 cubelets of the 5th order Menger Sponge
by Bill Gosper 20 Mar '16

20 Mar '16

It's actually a Plot3D. E.g., here are the 720 cubes near the conventional slice: gosper.org/mengslice2.svg You can climb it but for one double-step. --rwg On 2016-03-20 01:38, Dan Asimov wrote: > Wow, Bill, how do you get that amazing 3D effect? > > —Dan > > >> On Mar 19, 2016, at 10:07 PM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >> nearest the plane through the center, perpendicular to (2,3,2): >> gosper.org/mengslice3.svg <http://gosper.org/mengslice3.svg> >

1 0

[math-fun] PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation.
by Joerg Arndt 20 Mar '16

20 Mar '16

As some of us are interested in random number generation, I'd like to point to https://www.cs.hmc.edu/~oneill/ I'll unlike find time to read the paper (preprint as of now), so comments are welcome. Best regards, jj

3 3

[math-fun] PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
by Warren D Smith 20 Mar '16

20 Mar '16

> From: Marc LeBrun <mlb(a)well.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] PCG: A Family of Simple Fast Space-Efficient > Statistically Good Algorithms for Random Number Generation. > Message-ID: <D3141CB8.1DCD3%mlb(a)well.com> > Content-Type: text/plain; charset="ISO-8859-1" > >>="Joerg Arndt" <arndt(a)jjj.de> >> As some of us are interested in random number generation, >> I'd like to point to https://www.cs.hmc.edu/~oneill/ >> I'll unlike find time to read the paper (preprint as >> of now), so comments are welcome. > > Comments? Heh, be careful what you wish for! I'll try to be brief, but > this provokes a pet peeve (please delete if unfun)... > > > I skimmed the paper, and at risk of missing something of value, I'll also > pass on chewing deeper into all that verbal excelsior because I think it's > ultimately a huge waste of time. > > My opinion is that academics have created a tiny but evergreen cottage > industry around PRNG design for decades by presuming the problems they are > addressing are actually interesting. > > One of the biggest outdated misapprehensions is that, while it may have > been > vital to minimize internal state in the von Neumann era, today it's just > quaint. After progressive decades of "Moore's Law", statements like the > following from the paper sound like outtakes from a "Downton Abbey" > episode: > > "If the entire state of a random number generator can be represented in a > single processor register, we may reasonably expect it to offer performance > advantages compared to a generator that requires hundreds or thousands of > bytes of memory to represent its state." > > Confining attention to algorithms operating on a single register is like > insisting on programming while peeping through a keyhole. A nice circus > stunt if one can pull it off perhaps, but of little real relevance today. > > As much as I love Don Knuth, I think he, with the best of intentions, did > the art a disservice by obsessing at such length in TAOCP over the Linear > Congruential Generator. I suspect in part this was because there was such > a > sunk investment in all that pretty analysis. I regret that a consequence > has been a pernicious misplacement of priorities, resulting in blizzards of > this kind of misdirected academic snow ever since. But what's done is > done. > > Ironically, TAOCP actually briefly treats some alternative approaches with > much longer legs. Here's an example I've used, thanks to a suggestion by > Bill Gosper: > > ======== implementation sketch ======== > > Take the structure of a classic 1965 "Tausworthe" (circular-shift-with-XOR) > bit generator, expand each of the BITS to an entire WORD, and add (rather > than XOR) their values to get the next output word. So a classic 64-BIT > (say) shift-register generator expands into a 64-WORD generator (now with > 4096 bits of state). > > This is incredibly trivial to implement and very fast: a circular buffer of > 64 "registers" (that will be cached in fast memory of course), a handful of > auto-incrementing pointers and some additions. Not even multiplies or > mods. > > Now look at the LSB of the outputs. This will be the sequence of bits the > Tausworthe generator produced. But furthermore, the higher order bits will > be likewise, except that they will be perturbed by the cascade of "noise" > carries coming out of the lower-order bits. > > This has a huge state space and hence period (if you're obsessed with that) > and I expect is more than plenty good for almost any practical purpose. > > However if you're worried about an adversary that's reading the output > stream and trying to invert it, then you can mess up the rigid time > correlations by adding a scrambling post-process (also essentially > described > in Knuth) as follows: > > Take the upstream generator, call it R1, a second table T2 (likewise > initialized with noise) and some other generator R2 (actually R1 and R2 > could probably just be alternating outputs of the wide-Tauseworthe thingy). > Output T2[R2}, then increment T2[R2] += R1. > > Now T2 is accumulating a turbulent rain of the noise from R1, mixed by R2. > > ======== end of implementation ======== > > This thing is cheap to implement, very fast and easy to understand and > test. > > But, also probably less fun for academic analysis (due to being both too > easy and too hard). > > And of course 2048 bits, or even a megabit, is a pittance nowadays. > > Think it'd work? Maybe we can stop churning out papers about new PRNGs? > > > PS: for an interesting alternative for fast clean noise, but with different > design criteria (basically NO state update, F[n] vs. F[F[...), see > > John K. Salmon, Mark A. Moraes, Ron O. Dror, and David E. Shaw, "Parallel > Random Numbers: As Easy as 1, 2, 3,"?Proceedings of the International > Conference for High Performance Computing, Networking, Storage and Analysis > (SC11), New York, NY: ACM, 2011. --I disagree with LeBrun. First, if your PRNG consumes a megabit, its performance is going to suck because of cache misses. Second, the idea LeBrun mentions was discussed by Knuth TAOCP as Richard Brent's idea and is one instance of what is called "lagged fibonacci" generator. As Brent realized the LS bit is then a max-period sequence (if parameters chosen right). However, the Brent generator in my opinion sucks because using an array of N words each W wide, we do not get a period of order 2^(N*W) which is what we want; we get a period more like order 2^(N+W), and the high bits are more random than the low bits in each word. It also is known to fail various tests in the BigCrush battery. LeBrun's next idea is basically a scrambler similar to one Knuth mentions, applied to output of his lagged fibo. That also sucks cachewise. Other kinds of lagged fibo generators can do better, however. Third, I agree with LeBrun the academics have gone a bit nuts, and often done badly, but there is some rationale: The fact is, no generator I fully approve of has yet been constructed. That I know of. So make one. I agree we should be annoyed. But not because this area is being worked on. We should be annoyed because the work has not been good enough. And Knuth's own suggestions also were quite poor, and usually fail BigCrush.

1 0

[math-fun] the 26720 cubelets of the 5th order Menger Sponge
by Bill Gosper 20 Mar '16

20 Mar '16

nearest the plane through the center, perpendicular to (2,3,2): gosper.org/mengslice3.svg --rwg

4 3

[math-fun] Characterizing polys which permute GF(p)
by Henry Baker 19 Mar '16

19 Mar '16

A polynomial f(x) with coefficients in GF(p) permutes p iff f(x) is 1-1 function. We call f(x) a "perm" for short. After some deep discussions with Maxima, the permutation polynomials for GF(2) are [x, x + 1], while those for GF(3) are [x, - x - 1, - x, x - 1, x + 1, - x + 1]. As expected, there are 5!=120 perm polys for GF(5), with most being of degree 3. The simplest ones are: x, 2*x, -2*x, -x, x^3, 2*x^3, -2*x^3, -x^3. I. f(x)=x is a perm. II. If f(x) is a perm, then so is f(x)+c, c=0,1,2,...,p-1. Rules I+II take care of GF(2). And the evening and the morning were the first day. III. If f(x) is a perm, then so is c*f(x), c=1,2,3,...,p-1. Rules I+II+III take care of GF(3). And the evening and the morning were the second day. IV. x^k is a perm when gcd(k,p-1)=1. Rule IV subsumes rule I. Rules II+III+IV take care of GF(5). And the evening and the morning were the third day. V. If f(x) is a perm, then so is f(f(x)), etc. Rules II+III+IV+V take care of GF(7). And the evening and the morning were the fourth day. Now, once we have rule V, we can simplify rule II: If f(x) is a perm, then so is f(x)+1. Once we have rule V, we can simplify rule III: If f(x) is a perm, then so is g*f(x), where g is a generator of the multiplicative group of GF(p). Notice that rule II permutes *all* p elements, while rule III permutes the p-1 *all but zero* elements. Conjecture: rules II-V are sufficient for *every* GF(p). ??? We still don't have a trivial way to generate permutations which map one element to itself -- e.g., 0. Note that rules III,IV,V keep 0 fixed, but I don't think that they are sufficient to perform all permutations of the p-1 non-zero elements. We also don't have a trivial way to exchange only 2 adjacent elements & leave the rest fixed. If we could do this, then the theorem is proved, because we can use rules II & III to move any 2 elements adjacent to one another.

2 1