On 3/21/16, rcs@xmission.com <rcs@xmission.com> wrote:
I'm not seeing this CRT reconstruction property. Can you fill in a detail or two? I know that the sum of the two reconstruction coeffs must be pq+1, since (1,1) must reconstruct to 1. But I don't see how the general case turns into the XOR property: It seems to depend on the quotient of the raw reconstructed number Kp+Lq, divided by pq. Awaiting enlightenment,
Rich
--WDS: sorry folks, it appears my claim about Blum-Blum-Shub getting simpler, does not work. Post mortem below: We want to reconstruct x from y=x mod p and z=x mod q. Remember p and q are both primes with p mod 4=q mod 4=3. An answer is x=A*y+B*z, where A is a multiple of q with A mod p=1, and B is a multiple of p with B mod q=1. Then necessarily A and B both are odd, so that LeastSignifBit(x)=LeastSignifBit(y) XOR LeastSignifBit(z). Why? Well, if one or more were even, then LeastSigBit(x) would simply be constant, or would simply equal (say) LeastSignifBit(y). If so, then the bit sequence LeastSignifBit(x) would not be a hard Blum-Blum-Shub sequence, it would be an easy sequence. Just to be sure that this obvious, here's somebody recapitulating Blum-Blum-Shub: http://diamond.boisestate.edu/~liljanab/ISAS/course_materials/BBSpresentatio... Well, that all sounded like a great argument. But: Counterexample, p=7, q=11. Then A=22 and B=56. Well, humbug. We can overcome any such counterexample by adding or subtracting M=p*q (which is odd, indeed is 1 mod 4) to either A or B if it were even, to make it become odd. Then A=-55 and B=-21. So x = -55*(x mod 7)-21*(x mod 11)+(some multiple of 77). So, provided the "multiple of 77" is held fixed, my claim is valid in this case. But we can't hold it fixed. Crap. So, OK, my claim is refuted. The reason for failure is: when you chinese remainderize to construct x=A*y+B*z from y=x mod p and z=x mod q, this does NOT really yield x. It really yields "x plus a highly varying multiple of M=p*q, which needs to be removed." ============================== Meanwhile, I nevertheless remain interested in the CONJECTURE: Given K circular sequences of N random bits, and also given a further N-bit "message" which is the XOR of the first K sequences after secret cyclic shifts are applied to each... there is no algorithm that will detect the nonrandomness of the message (e.g. by determining the K private shift values) in expected time less than N^(K/2) operations. REMARK: Here (to make a little progress) the exponent K/2 appears to be tight. We can achieve N^(K/2) * 2*log(N)*K expected running time as follows. Build a McCreight suffix tree indexing all possible log(N)*K-long bit strings arising inside all possible shifted XORs of the first K/2 sequences. But if K is odd, then only index substrings beginning at locations that are multiples of sqrt(N). Now consider all XORs of the message plus the last K/2 sequences shifted all possible ways. Look up their initial 2*log(N)*K bits in the suffix tree, or if K is odd do this not for the "initial" bits but rather try every startpoint from 1 up to sqrt(N). Whenever a lookup succeeds that tells you that you probably won, plus tells you the shifts you need. THE USE OF IT: Seems to me this conjecture is plausible and fundamentally useful for devising psu-random generators immune to statistical tests, crypto, and for devising alleged lower bounds on computational complexity probably all over the place, with your favorite polynomial degree.