Ignoring depth, and just counting gates, I've heard rumors that the best known result for reversing an xor circuit is a ratio of 1.5+epsilon. I.e., there is a K-input, 1-1, N-gate-dag-circuit (no feedback) of xor gates whose inverse circuit (also a dag of xor gates) requires 1.5N+change gates. The example is pretty simple: the inputs are arranged in a polygon, each is xored with a neighbor or two and maybe with the total parity. For reversing a sparse NxN matrix multiply, it appears you need to compute a few inverse values directly at cost few*N. But then you may be able to capitalize on the sparseness to compute the remaining values cheaply from the forward-direction equations, solving one equation at a time. The big unknown here is how large "few" must be. I encountered this problem when I was trying to solve the finite-field equation X^2 + X = A over GF[2^155]. My field polynomial is U^155+U^62+1. The low bits of X and A are forced to 0, to make the problem 1-1. My best answers (lowest gate count), for several different 2^odd field sizes, use a direct method to compute 20-40 values, and then fill in the others at a cost of a couple of gates each. Rich --------- Quoting Warren Smith <warren.wds@gmail.com>:
Much or all of cryptography depends on the claim that there is a bijective map F such that computing y=F(x), is a lot easier than computing x=Finverse(y).
For example, if F maps (a,b,c) to (b^a mod c, b, c) where gcd(b,c)=1, then many people think/hope that Finverse is a lot harder than F ("discrete logarithm problem").
But my QUESTION is: what is the best result one can actually PROVE of the form "Finverse is a lot harder than F"?
==============================================
Dhananjay S. Phatak pointed out to me (then I improved by consulting Joerg Arndt's book...) that the "Gray coding" problem is a provable (pitifully weak, but provable) example. In C-language notation
g = x ^ (x>>1) will convert bitstring x to Gray code g. This is implementable by a parallel circuit with depth=1, and #gates=wordlength-1.
Reverse operation accomplished by: x = g; x ^= x>>1; x ^= x>>2; x ^= x>>4; x ^= x>>8; x ^= x>>16; ... keep going until word length.
This can be done by a circuit with O(N) gates, but the depth is now log2(wordlength) not 1, and this is best possible in the sense that no circuit made of (<=2-input, <=2-output) binary logic gates can do it with less depth.
---
More generally, multiplying y=Mx where M is an NxN sparse matrix, and x,y each are N-vectors (in some field) is easy to do forward (assume at most a constant number of nonzeros per row of M): order N field operations and time; parallelizes to depth=O(1) if at most. But computing x=Minverse y is provably harder, requiring depth of order log(N) at least. The proof is to observe that in general each entry of x will depend on all N entries of y.
[I actually do not know how to do it in less than order N^2 operations, but I do not have a proof that's best possible.]
Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun