March 2016 - mathfun@mailman.xmission.com

[math-fun] HB's reasoning about repeated roots
by Warren D Smith 30 Mar '16

30 Mar '16

> From: Henry Baker <hbaker1(a)pipeline.com> > Permutation polynomials aren't so easy to factor -- at least not into 2 > factors that are both permutations. > > Suppose that a permutation poly p(x) factors into q(x)*r(x), where q(x) & > r(x) are also perm polys. But p(x) must have exactly 1 root, else two > distinct roots map into zero. But since q(x) and r(x) are also perm polys, > they must each have a single root. If they are different, then p(x) would > have two distinct roots, a contradiction. If q(x) and r(x) share the same > root, then p(x) has a repeated root. > But if p(x) has a repeated root, then > by the pigeonhole principle, there is some field element without a preimage > via p(x), so p(x) can't be a permutation poly -- once again a contradiction. --that is where you went wrong. > Scratch that reasoning! > x^3 is a perm poly mod 5, & has a repeated root! > So a permutation poly can't possibly factor into two permutation polys. --so what you really proved was, a permpoly cannot factor into two permpolys, unless all three have the same root. Without loss of generality we can demand that root be 0 (via a translation). What about the SUM of two perm polys? When can it be a permpoly? This often happens when all three are linears. For example, perms F(x) with the property that F(x)+x also is a perm, might be called "queen perms" (?) due to their use in the N-queens problem. I would like to know this: Suppose I tell you K different linear polynomials L1(x), L2(x), ..., LK(x). About how many permutations F(x) of a finite field with q elements are there, such that F(x)+Lj(x) is always a permutation as well (for each j=1,2,...,K)? -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] some permutation non-polynomials
by Warren D Smith 30 Mar '16

30 Mar '16

(A*x+B)*x+C (mod 2^wordsize) is a permutation polynomial (quadratic), iff A=even, B=odd. But it seems to me this remains true if either or both "+" operations are replaced by XORs. Proof sketch: First of all, if A=odd, B=odd, then (A*x+B)*x will map both odd x and even x to even, hence not a permutation. That argument also works if + is changed to XOR. If A=odd, B=even, then let B=2*Q and note A has a unique reciprocal modulo 2^wordsize, whereupon (A*x+B)*x/A =(A*x*x+B*x)/A =x*x+(B/A)*x =x*x+(2*Q/A)*x =(x+Q/A)^2+const which plainly is a 2-to-1 map (consider negating x+Q/A) not a permutation. But: can this argument be made to work when the + is changed to XOR? I think it can, because we can produce the "evil twin" x by working its bits out one at a time starting from the least-significant end. So A=even is necessary for permitude. Once A=even, then B=odd is forced (in both the + and XOR cases) otherwise we'd be multiplying x by an even number, clearly losing information since always yields even product. Now to see that if A=even, B=odd we always get a permutation: We merely need to show there is no "evil twin" x causing the quadratic to have the same value. This is true if the wordsize is small by simply exhaustively verifying it. Now work inductively upward one bit at a time, i.e. increasing the wordsize by 1. We inductively know the evil twin x must have (in binary form) the same suffix as the original x. If the next-up bit differs, we can see that is not going to yield the same quadratic value because only the linear term matters. OK, we have now sketched a proof this yields a permutation iff A=even and B=odd. ======= Now, what about the period when you iterate this map: (A*x+B)*x+C (mod 2^wordsize) Iterating this yields full period 2^wordsize (using + and + with wordsize>2 bits) if A=even, B=odd, C=odd, and 4 divides 3+B-A. (Proof in Knuth.) When do the XOR versions yield full period? ======= RotateLeft(x, F(x)) is a permutation among the 2^wordsize possible x's, where the number of hops F(x) is any rotation-invariant function. Two that spring to mind are the "PopCount" function and constants, and functions thereof. Of course these permutations have all cycles short (<=Wordsize). ======== x XOR RightShift(x,K) is a bijection for any K>0. It is self-inverse. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Factoring perm polys
by Henry Baker 29 Mar '16

29 Mar '16

Permutation polynomials aren't so easy to factor -- at least not into 2 factors that are both permutations. Suppose that a permutation poly p(x) factors into q(x)*r(x), where q(x) & r(x) are also perm polys. But p(x) must have exactly 1 root, else two distinct roots map into zero. But since q(x) and r(x) are also perm polys, they must each have a single root. If they are different, then p(x) would have two distinct roots, a contradiction. If q(x) and r(x) share the same root, then p(x) has a repeated root. But if p(x) has a repeated root, then by the pigeonhole principle, there is some field element without a preimage via p(x), so p(x) can't be a permutation poly -- once again a contradiction. So a permutation poly can't possibly factor into two permutation polys. The same argument works for any number of factors on the right hand side, so a permutation polynomial can't factor into multiple permutation polynomials, either. By the above reasoning, if p(x)=q(x)*r(x), and p(x), q(x) are permutation polynomials, then p(x) & q(x) must share the same zero, and r(x) has *no* zeros -- i.e., r(x) has no linear factors.

1 1

[math-fun] BH/BH collision releases 2-3 solar masses of gravity wave energy
by Henry Baker 28 Mar '16

28 Mar '16

30-solar mass black hole coalesces with a 35-solar mass black hole, producing a 62-solar mass hole, giving out 2-3 solar masses worth of gravitational wave energy in approx. 1/5 second ! 76-minute video of the talk Rainer Weiss from MIT recently gave at KITP. It was an excellent talk that explains much about their detection of gravity waves. http://online.kitp.ucsb.edu/online/colloq/weiss1/

4 3

[math-fun] Quickies
by Keith F. Lynch 28 Mar '16

28 Mar '16

Here are three problems, all original with me, that you can solve in your head. They're perfect for keeping from being bored when you're out walking or otherwise unable to safely read or do other tasks. Inspired by Sloane's strange-looking A258107 (2, 3, 4, 82000), I thought about the smallest number (other than "1") that's represented by nothing but odd digits in the first N bases (binary, ternary, etc.). I quickly proved to myself that no number has this property for bases 2, 3, and 4. What about just in odd bases? I quickly proved to myself that no number (except "1") has this property in bases 3, 5, 7, and 9. I had been saving the dead president's problem for just after the next president died. But I've decided that would be in bad taste. So here goes: There are currently 38 dead US presidents. Their dates of birth and death are all known. If I sort them in order of birth, they're in a certain order, starting with Washington and ending with Kennedy. If I sort them in order of death, they're in a slightly different order, starting with Washington and ending with Ford. Suppose I sort them by the date on which they had been (or will have been) dead longer than they were alive? I get yet a third slightly different order. (Once again it begins with Washington and ends with Ford. So does sorting them by when they will have been dead twice as long as they were alive.) The question is: How many different sort orders are there, as you vary the parameter X for "dead X times longer than alive" over all real numbers, including negatives. Yes, you can solve it in your head, and no, the answer isn't 38 factorial. All of these puzzles of course give rise to more challenging puzzles.

5 4

[math-fun] some full period 32-bit and 64-bit single-word psu-random generators
by Warren D Smith 28 Mar '16

28 Mar '16

18 different 32-bit generators each with period 2^32-1, consisting of all nonzero words (each generator is a single line of code consisting of 2 shifts, 2 XORs, and an AND, in C language ^ denotes XOR, & denotes AND, ~ denotes bit-complement): x ^= (x>>7)&(~(1<<3)); x ^= (x<<1); x ^= (x>>5)&(~(1<<4)); x ^= (x<<2); x ^= (x>>6)&(~(1<<6)); x ^= (x<<1); x ^= (x>>6)&(~(1<<7)); x ^= (x<<1); x ^= (x>>13)&(~(1<<7)); x ^= (x<<4); x ^= (x>>5)&(~(1<<8)); x ^= (x<<6); x ^= (x>>13)&(~(1<<8)); x ^= (x<<6); x ^= (x>>5)&(~(1<<9)); x ^= (x<<2); x ^= (x>>8)&(~(1<<10)); x ^= (x<<9); x ^= (x>>13)&(~(1<<10)); x ^= (x<<6); x ^= (x>>8)&(~(1<<11)); x ^= (x<<9); x ^= (x>>13)&(~(1<<11)); x ^= (x<<4); x ^= (x>>8)&(~(1<<12)); x ^= (x<<9); x ^= (x>>8)&(~(1<<13)); x ^= (x<<9); x ^= (x>>5)&(~(1<<17)); x ^= (x<<2); x ^= (x>>5)&(~(1<<18)); x ^= (x<<6); x ^= (x>>6)&(~(1<<18)); x ^= (x<<1); x ^= (x>>6)&(~(1<<19)); x ^= (x<<1); There are also various re-coded versions of these obtained by time-reversal and/or bit-order-reversal, etc. The AND-mask here was always taken to have all bits 1 except for a single hole. But entirely general masks also would be possible in an enormous number of possible ways, roughly 0.2% of parameter choices in x ^= (x>>A)&C; x ^= (x<<B) work to yield period = 2^32-1. For 64-bit words, it turns out we can save an instruction since the all-1's AND-mask happens to yield a solution: x ^= (x<<7); x ^= (x>>9); has period=2^64-1. This has exactly 3 more variants arising from time- and/or bit-order-reversal but aside from that is unique. For 16-bit words, these work: x ^= (x>>2)&(~(1<<2)); x ^= (x<<1); x ^= (x>>7)&(~(1<<3)); x ^= (x<<2); x ^= (x>>7)&(~(1<<5)); x ^= (x<<2); x ^= (x>>2)&(~(1<<11)); x ^= (x<<1); How to find these: All the above generators are linear transformations of vectors over the 2-element field GF(2) and the period is the order of the linear transformation. By fast matrix powering over GF(2) you verify (for a good parameter choice) that no divisor of 2^wordsize-1 is the period, but 2^wordsize-1 is. Bad parameter choices that do not pass that test are discarded. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Alternating subgroup of perm polys
by Henry Baker 27 Mar '16

27 Mar '16

Re permutation polynomials over a finite field GF(p). It would be nice to characterize the alternating (normal) alternating subgroup of permutation polys. We already know that {x,x+1,1/x} generates full group of perm polys GF(p)(x). {x,x+1,2*x^3} generates alternating subgroup of GF(5)(x). {x,x+1,2*x^5} generates alternating subgroup of GF(7)(x). {x,x+1,3*x^5} generates all of GF(7)(x). Note that x^(p-2) = 1/x, so {x,x+1,2/x} generates alt subgroup of GF(5)(x). {x,x+1,2/x} generates alt subgroup of GF(7)(x). {x,x+1,3/x} generates full group of GF(7)(x). which seems to beg the following conjecture: The alternating subgroup of perm polys of GF(p)(x) is generated by {x,x+1,g/x} when g is NOT a generator of the multiplicative group of GF(p), but instead generates but half of that multiplicative group.

1 0

[math-fun] a few cheap linear congruential randgen cases
by Warren D Smith 27 Mar '16

27 Mar '16

X := RotateLeft(X,L) + X X := X + carry (look Ma, no multiply instruction!) implements a linear congruential generator modulo the "Mersenne" modulus 2^wordsize-1, with multiplier 1+2^L, where the first add generates boolean carry, used in the second add. This code however has an off-by-1 error when the second add involves both X=2^wordsize-1 and carry=1; thw wrong result is X=0. That, when it happens, is embarrassing, since then all subsequent "random" numbers will be 0. That error happens only once per period and if desired could be corrected by adding a third statement if(X==0){ replace X by some other appropriate value } someplace, the new value being chosen to make the period be whatever we like, e.g. to get a prime period skip over a few entries in the hypothetical full period, just enough to reduce period to some large prime a bit below it. We actually can, in basically the same way, implement any of the four multipliers 1+-2^K and 2^K+-1 by using some subtractions instead of adds. "Fermat" moduli 2^wordsize+1 can also be done, but unfortunately it costs more instructions: if(X==0){ X := replacement value; } Y := ShiftLeft(X,L); Z := ShiftRight(X,L); if(Y==0 && Z!=0){ Y:=1; } X := (+-X) + (+-)(Y - Z); X := X +- carry; with three appropriate sign choices, most simply +, +, and -. If we skipped the final X+carry, so only employ the single line X := RotateLeft(X,L) + X then we are implementing a linear congruential randgen modulo 2^wordsize-1, except that "noise" of value -1 or 0 is added each step (the noise being the skipped carries) -- and this noise will tend to shorten the period drastically by sending us back to some already-used X. Since the "Fermat" number 2^64+1 = 274177*67280421310721 we can in this way achieve period arbitrarily below 274176*67280421310720=2^63.999994738; the elements of the period are the numbers relatively prime to 2^64+1, except for the ones skipped. Similarly 2^32+1=641*6700417 allowing any period below 640*6700416=2^31.99774733329, and 2^16+1 actually is the (last?) Fermat prime. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] RSA versus ECC
by Henry Baker 26 Mar '16

26 Mar '16

At 12:00 PM 3/26/2016, Warren D Smith wrote: >> Message: 4 >> Date: Sat, 26 Mar 2016 09:57:12 -0700 >> From: Henry Baker <hbaker1(a)pipeline.com> >> Subject: Re: [math-fun] Why elliptic curve superior to RSA >> >> The problem with fixing a curve is that with enough memory, someone >> can do some pretty elaborate precomputation. > >--Au contraire. With RSA, you fix your private primes p & q, then publish p*q. >Somebody can precompute the hell out of that. > >With EC, pick a curve, once and for all, publish it, and I don't care >what precomputation anybody does on it, no matter how large, provided >its results are concisely stated. >And the entire world can examine this curve to be sure it seems good. https://weakdh.org/ "Millions of HTTPS, SSH, and VPN servers all use the same prime numbers for Diffie-Hellman key exchange. Practitioners believed this was safe as long as new key exchange messages were generated for every connection. However, the first step in the number field sieveÂthe most efficient algorithm for breaking a Diffie-Hellman connectionÂis dependent only on this prime. After this first step, an attacker can quickly break individual connections. "We carried out this computation against the most common 512-bit prime used for TLS and demonstrate that the Logjam attack can be used to downgrade connections to 80% of TLS servers supporting DHE_EXPORT. We further estimate that an academic team can break a 768-bit prime and that *a nation-state can break a 1024-bit prime.* Breaking the single, most common 1024-bit prime used by web servers would allow passive eavesdropping on connections to 18% of the Top 1 Million HTTPS domains. A second prime would allow passive decryption of connections to 66% of VPN servers and 26% of SSH servers. A close reading of published NSA leaks shows that the agency's attacks on VPNs are consistent with having achieved such a break."

1 0

Re: [math-fun] RSA versus ECC
by Warren D Smith 26 Mar '16

26 Mar '16

> Message: 4 > Date: Sat, 26 Mar 2016 09:57:12 -0700 > From: Henry Baker <hbaker1(a)pipeline.com> > To: <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Why elliptic curve superior to RSA > Message-ID: <E1ajrWO-000258-Om(a)elasmtp-kukur.atl.sa.earthlink.net> > Content-Type: text/plain; charset="us-ascii" > > The problem with fixing a curve is that with enough memory, someone > can do some pretty elaborate precomputation. --Au contraire. With RSA, you fix your private primes p & q, then publish p*q. Somebody can precompute the hell out of that. With EC, pick a curve, once and for all, publish it, and I don't care what precomputation anybody does on it, no matter how large, provided its results are concisely stated. And the entire world can examine this curve to be sure it seems good. > This is part of the problem with NIST's ECC random number generator: > you couldn't trust it not to have a back door. --no, you are confused. This was not a "standard ECC cryptosystem." That was "an intentionally-designed fake-secure intentionally backdoored algorithm foisted on NIST by its corrupt lying NSA advisors, which was soon detected by Microsoft analysts, and then it also was revealed by Snowden to have been indeed intentionally implanted as an NSA conspiracy." It was more complicated than the standard ECC systems because the extra complexity was used to hide the backdoor; other NIST advisors saw no reason for the extra complexity and inelegance of the scheme but were shouted down by the NSA liars who just tried to claim it was there for secret security reasons, and they were the NSA experts who knew All while the others were mere dillentantes, so shut up, it has to be exctly the way we say wiht not one comma altered. > Indeed, Juniper found > to their horror that their ECC systems did indeed have such a back > door, although it isn't clear who else had the backdoor key -- NSA? > Chinese? Israeli's? Russians? --NSA. > Better to take the hit on using RSA with seriously large primes, and > carefully choosing different ones each time. --In fact, a simple GCD-based study found that a large fraction of all RSA public keys published on the internet, all time, were easily broken by finding factrs of M's by taking GCDs of many M's out there. I do not know the fraction, but it was of order 10%. The problem was some RSA package included a poor random number generator which output only a few possible random numbers -- which perhaps was due to an innocent mistake or perhaps intentionally implanted. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0