Wikipedia:Reference desk/Archives/Mathematics/2014 December 11

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 11

Is the inverse of an odd/even function still odd/even?

If f(x) is an invertible odd function, is f^-1(x) an odd function too? If yes, how do you prove it?

If f(x) is an invertible even function, is f^-1(x) an even function too? If yes, how do you prove it?

Thanks. 175.156.91.156 (talk) 00:10, 11 December 2014 (UTC)

Is this homework? It has the feel of it, on its face, but the second one would actually be a fairly strange homework problem. Not a bad one, necessarily, because it makes you think about good things to think about, but an unusual one. --Trovatore (talk) 00:27, 11 December 2014 (UTC)

First question: can an odd function be invertible at all? If so, are all odd functions invertible, or only some of them?
And how about even functions—are they invertible? Every even function or only some of them? Or maybe none, or possibly there is one such even function?... --CiaPan (talk) 07:45, 11 December 2014 (UTC)

I don't think that there is any sort of correlation. Take f(x) = x², it is even, now the inverse is f(x) = {x^½, -x^½}, it is odd. Now, a cubic and its inverse are both odd. Plasmic Physics (talk) 10:20, 11 December 2014 (UTC)

Even functions are not one-to-one and so not invertible. In your example, $f(x)=x^{2}$, the "inverse" is double-valued (and is not an odd "function" in any sense of the term). So, of the two, only odd functions can be invertible. But obviously there are functions that are neither even nor odd that are invertible (e.g., f(x)=x+1), and odd functions that are not invertible, (e.g., $f(x)=x^{3}-x$). Sławomir Biały (talk) 13:03, 11 December 2014 (UTC)

Wrong, Sławek ;) actually some even functions are invertible. And I'm sure you can find them... --CiaPan (talk) 13:34, 11 December 2014 (UTC)

Not to spoil the hinting, but does the answer have more to do with exactly what elements in the domain sum to 0 than the function itself? I only ask because I can't see any other possibility.Phoenixia1177 (talk) 15:37, 11 December 2014 (UTC)

Well, obviously if you're allowed to invent nonstandard meanings of "even function", then anything goes. But that does not make what I said wrong for most standard meanings of the term. Sławomir Biały (talk) 15:51, 11 December 2014 (UTC)

Not that sophisticated as it seems. Just a direct implication of definitions.
For a function $f$ to be even its domain $D$ must be 'symmetric': $\forall _{x}\,(x\in D\iff (-x)\in D)$ and its values must be 'symmetric': $\forall _{x\in D}\,f(x)=f(-x)$.
On the other hand $f$ must also be injective to be invertible: $\forall _{x,y\in D}\,(x\neq y\implies f(x)\neq f(y))$.
The latter two imply together there must not be an element in a domain which is different from its additive inverse: $\lnot \exists _{x\in D}\,x\neq (-x)$, which in turns means all elements are equal to their inverses: $\forall _{x\in D}\,x=-x$. So, all elements of the domain are ZERO: $D=\{0\}$.
Now, each single-point function from zero to any real value V
      $f:\{0\}\to \{V\}$
is even, odd and invertible. Additionaly, if $V=0$ its inverse is also even and odd. --CiaPan (talk) 16:21, 11 December 2014 (UTC)

Like Sławomir, I don't really think this is an answer to the question as asked, though it might be a useful aside. But if you're going to go this route — don't forget the empty function. --Trovatore (talk) 17:50, 11 December 2014 (UTC)

Alternatively, over any field of characteristic 2, all functions are both even and odd; many of them are also invertible. -- Meni Rosenfeld (talk) 18:14, 11 December 2014 (UTC)

Usually, even/odd functions are functions of a real variable, which I take to mean that their domains are all of R (or at the very least symmetric domains, in the sense of analysis, meaning open sets). But as I said, if you allow non-standard definitions, then anything goes. Sławomir Biały (talk) 16:27, 11 December 2014 (UTC)

Oops, I didn't quite have the definition of an odd function correct. That said, I don't know of any even graph that can be rotated about the xy-diagonal and yield an odd graph. All though if you invert f(x) = 0 (even), then you get f(y) = 0 (even). Plasmic Physics (talk) 20:55, 11 December 2014 (UTC)

Algorithm

What is the most efficient algorithm for calculating x and y in (A + B*sqrt(C))^n = x + y*sqrt(C), for positive integer n? 70.190.182.236 (talk) 04:04, 11 December 2014 (UTC)

I'm not sure I fully understand what you are asking, as it stands, you can subtract the quantity involving y from both sides and have x vary with y. Is there a context you are omitting, or are you asking how to quickly calculate the roots, or something else?Phoenixia1177 (talk) 15:33, 11 December 2014 (UTC)

Presumably $A,B,C,x,y$ are all integers (though it could be made a bit more general). The question is how to find the coefficients of the simplified form of the expression with the radical. -- Meni Rosenfeld (talk) 16:18, 11 December 2014 (UTC)

If I'm not mistaken, $(A+B{\sqrt {C}})^{n}=[1\ {\sqrt {C}}]{\begin{bmatrix}A&BC\\B&A\end{bmatrix}}^{n}[1\ 0]^{T}$. Find the eigendecomposition of the matrix, and use it to calculate this power. Then you can find x and y. -- Meni Rosenfeld (talk) 16:14, 11 December 2014 (UTC)

Clearly $\scriptstyle {A}$, $\scriptstyle {B}$ and $\scriptstyle {C}$ are of a type which does not include $\scriptstyle {\sqrt {C}}$ (e.g. integers with non-square $\scriptstyle {C}$). You can get an approximate answer by evaluating $\scriptstyle {(A+B{\sqrt {C}})^{n}}$ and $\scriptstyle {(A-B{\sqrt {C}})^{n}}$ in floating-point arithmetic (where $\scriptstyle {\sqrt {C}}$ is defined), and then taking the nearest-integer values of

$x={\frac {(A+B{\sqrt {C}})^{n}+(A-B{\sqrt {C}})^{n}}{2}}$

$y={\frac {(A+B{\sqrt {C}})^{n}-(A-B{\sqrt {C}})^{n}}{2{\sqrt {C}}}}$

More likely, you want to use exponentiation by squaring. The article make it seem more complicated than it is so here is some code:

/*define Pair to represent (a + b*sqrt(c))*/
typedef int Type;
typedef struct{Type a; Type b;} Pair;

/*function to calculate arg^n*/
Pair
power(Pair arg, Type c, int n)
{
  Pair power, running_sqr;
  Type temp;


  /*initialize - power = arg^0*/
  power.a = 1;
  power.b = 0;
  /*running_sqr = arg^1*/
  running_sqr.a = arg.a;
  running_sqr.b = arg.b;

  /*for each bit of n (ignoring leading 0s)*/
  while (n){
    if (n & 1){
      /*lowest bit of n is 1 - multiply power by running_sqr*/
      temp    = power.a * running_sqr.a + power.b * running_sqr.b * c;
      power.b = power.a * running_sqr.b + power.b * running_sqr.a;
      power.a = temp;
    }
    /*square running_sq*/
    temp          = running_sqr.a * running_sqr.a + running_sqr.b * running_sqr.b * c;
    running_sqr.b = running_sqr.a * running_sqr.b + running_sqr.b * running_sqr.a;
    running_sqr.a = temp;
    /*shift n right 1 bit (divide by 2)*/
    n >>= 1;
  }

  return power;
}

It could be made more efficient - there is one more squaring than necessary. --catslash (talk) 17:15, 11 December 2014 (UTC)

Actually, I'm not sure my diagonalization method above (or catslash's method, which is equivalent) is the best way, since floating-point operations are less efficient than integer operations. Instead, I'd keep the matrix as is, and calculate its nth power directly, with exponentiation by squaring and the Strassen algorithm. -- Meni Rosenfeld (talk) 12:21, 12 December 2014 (UTC)

is there a zero-knowledge proof whether 1 number you hold is in a Set of numbers held by the second party?

Hi, I was reading this article

http://www.wired.com/2014/12/facebook-knows-ads-influence-offline-purchases/

which had a comment on it elsewhere:

“ > The trick is that the hash of a phone number captured on Facebook will look just like the hash of the same phone number captured in a brick and mortar store, so the two companies can match the numbers without actually trading them.

This just isn't possible. How many cents would it cost to brute-force hash all legal American phone numbers?

”

I agree! It's trivial to brute-force all hashes.

So the question is, is there an actual zero-knowledge algorithm that the two parties could use?

To simplify, if I have an integer, and you have a set of integers, can we check whether my integer is in your set of integers without divulging any information other than Yes or No? (i.e. not leaking what my integer had been, and not leaking what your set had been.) 82.131.223.148 (talk) 22:23, 11 December 2014 (UTC)

How about this? (Assuming you have parties A and B, where A needs to check for numbers in B list without letting B know the numbers and without A getting B's list.) B creates an encryption function h, encrypts all the numbers on B's list and sends A the list of encrypted numbers and the algorithm for h. B does not send a decryption algorithm for h, in fact there does not need to be one. If A wants to see if a number is on B's list, A encrypts it using h, checks the encrypted value against the list from B. There are reasonably secure encryption algorithms so the drawback is that B has to send A a large amount of data, comparable to the size of B's list. I thought about B keeping the encrypted list but then B could keep a table of which plaintext numbers map to which encrypted numbers and decode A's encrypted value. This would be possible even if A chose the encryption function. So I don't believe is possible if there isn't information exchanged comparable to the size of the list. Not really my area of expertise so correct me if I'm wrong. --RDBury (talk) 23:28, 11 December 2014 (UTC)

I'm sorry to say that yes (Op here) this is totally wrong for the exact same reason I quoted. So it doesn't work at all. Likewise if A sends h(42) to B for B to check on B's end, B can simply try h(1) through h(100) and learn exactly which number A held - B doesn't have to start by hashing B's actual list of numbers. So this really doesn't work at all.

specifically, it doesn't work for US telephone numbers since even if we take all integers 1 000-000-0000 through 1 999-999-9999 (which aren't all valid) that is 10 billion numbers. That is 10 gigahashes. For comparison, the bitcoin network currently hashes 294 million gigahashes per second, so if this network would like to try to find your hash it would take something like 10/294,000,000 = one 29 millionth of a second. If you used the bitcoin network to break this hash, it would be done by the time light could travel 10 meters. More realistically, a single cheap server can probably check all hashes in a matter of minutes to hours. If you tried to make the hashing difficulty very prohibitive, it would be only a matter of time, or of inclination to do it ten billion times instead of 1 time. It's not crypographically secure. It's not zero-knowledge proof. What we want is a zero-knowledge proof algorithm, that runs interactively. 212.96.61.236 (talk) 00:12, 12 December 2014 (UTC)

You're right in that if the universe of possible values is small enough to do a brute force search then my scheme wouldn't work. In such a case it would have to be the case that A would not receive an encrypted list. For the reason I gave above, I believe this implies that no scheme is possible. Perhaps if the universe of possible values was expanded then it would work though, e.g instead of just phone number make is the list of phone number + name + address. --RDBury (talk) 02:26, 12 December 2014 (UTC)

Nonono, you just don't know that there exists an academic disclipline called 'zero-knowledge proofs'. here is a primer http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html -- I think it's particularly clear. If a ZKP interactive algorithm exists, then you should be able to prove that some number is in a set even if the possible values of the number are like 1, 2, 3, 4, and 5 - without giving *any* more information about the number away, other than whether it is in the set. 212.96.61.236 (talk) 02:35, 12 December 2014 (UTC)

Interesting article and, like I said, it's not my area of expertise, so it's a new concept for me. But I still don't think that there is a scheme which does what you describe. A can query B for the existence of a piece of data and get a yes/no answer. (I think what you may be getting at is that B may return a probabilistic answer as in the example in the primer, but A still eventually gets a yes/no answer by repeating the query.) If the universe of possible data is small then A can repeat this query for every possible value and eventually get all of B's list. It doesn't really matter what the algorithm is. Actually I don't think the zero-knowledge concept really applies here because every time A queries B, A gets 1 bit of information about B's list, unlike the example given in the primer where A (the client) gets no information about B's (Google's) 'solution', not even 1 bit, no matter how many times A runs the query. In the example given in the primer, Google basically knows everything, both about the graph and it's own solution while the client knows the graph and only has zero-knowledge about the solution. In your problem it seems to me you're asking for more than the zero-information situation in that both sides have limited information and this information must remain limited. But this results in a contraction because of the fact that when A queries B the information A has increases by one bit. Increasing the length of the data gets around this, practically if not theoretically, because instead of just 10^10 bits needed to specify the list you now need say 64^80 bits which is large enough to be considered infinite for practical purposes. (The 64^80 isn't really needed on B's side because B stores the list as a list rather than a bitmap, essentially compressing the data. But from A's point of view, not knowing how many items are on the list, it may as well be that big.) In any case, you may want to wait for an answer from someone who knows more about this subject than I do. --RDBury (talk) 05:03, 12 December 2014 (UTC)

It's definitely the case that A can always get the list to within any certainty. While I lack solutions, as of now, we could consider the problem where A is verifying one number and A should not know B's list and B not know A's number. And, perhaps, the related problem of A has a list and B has a list, A and B want to know how many from A's list are on B without revealing anything else. Would either of these be of interest? As mentioned, arbitrary questioning from A should eventually get B's list, but something that satisfies for specific instances may still be of value (since, in the real world, no sensible B should allow arbitrary inquiry...).Phoenixia1177 (talk) 08:59, 12 December 2014 (UTC)

Not really. who says B is willing to answer more than a single question by A? Who says A is willing to match A's number (run the protocol) more than once? If there is a ZKP, then B can commit to a list, and A can verify whether A's number is on that list (or prove it to B), a single time, interactively. Yes, they give up exactly 1 piece of information: whether A's number is in B. If they did it repeatedly A could learn B's list (by sending every number, and seeing which ones B proves he has.) Or B could learn A's number by asking for it repeatedly, against the sets: {1}, {2}, etc. None of this matters. The point is that in a *single* transaction, is A giving up any more information than whether his number is in a set B committed to? In the case of a hash, definitely. In the case of a ZKP, no. A can agree to run a ZKP proof algorithm a single time. I actually found such an algorithm: http://www.ippari.unict.it/~catalano/CaFiMe08.pdf I'm not an expert and it might not be exactly what is needed, but it's along those lines. 212.96.61.236 (talk) 16:56, 12 December 2014 (UTC)

Not sure if you're the OP, or not, but " Namely, A can simply try encrypting everything and see what matches. (For a trivial example, let's say A's number is between 1-100 and in fact (without loss of generality) it's 42. B has a 7 numbers between 1 and 100, does not want to reveal which ones he holds. If B does as you suggest, A can simply do h(1) through h(100) - and not only h(42) - and learn all of B's list. ", from the op, does seem to indicate that A can do exactly your "who says" above. Thus why I suggested considering the case of a single transaction and a single number for A...for that exact reason.Phoenixia1177 (talk) 04:33, 13 December 2014 (UTC)

Sorry for the confusion - so far I'm every IP in this thread. I'm the OP and the person you just quoted. What I said applies ONLY to a function h(), since you have to give h() out (h stands for 'hash' presumably.) You can't say, "here's a function h, tell me what it says on your number - but PLEASE only run it once, and only on your number!!". See? Whereas, an interactive 'zero-knowledge proof' protocol can let the other person agree to run it a single time only. Unlike giving out the plans for some function h()! Please note that most zero-knowledge proofs (I think) are interactive. (They have to be, otherwise what's to stop the person with the number from running it again and again against different numbers. It has to be an interacive protocol that just works as many times as the other party plays ball.) Does this make sense? 212.96.61.236 (talk) 18:12, 13 December 2014 (UTC)

Thank you for clarifying, I see where you are coming from. I don't have a good answer, as of now, but I love problems of this nature; in the event I do come up with anything...well, I don't know, you don't have a talk page, or anything to leave it on, but should you decide to register, drop me a line on my talk page, and I'd be happy to share anything I come up with -- I want to read up a little more, so it will probably be after this is archived before I'd have anything except the cursory to share (and should you come up with a really awesome solid solution, please do share as well - I intend to read over the paper you presented tomorrow, so apologies if the solution is contained therein already). :-) Phoenixia1177 (talk) 08:32, 14 December 2014 (UTC)

Re comparison with the Bitcoin network: "Hash" isn't a thing, there are different hash functions. Bitcoin uses (double) SHA-256, which is extremely simple and quick. The hash function chosen for this application can be such that calculating one hash when you know what to look for is cheap, and yet calculating 10B hashes is expensive (you don't need to be overly creative for this, simply n repetitions of some known hash function, for large enough n, will do). Thus, the comparison is invalid. -- Meni Rosenfeld (talk) 19:29, 13 December 2014 (UTC)

anyway it's enough that whatever you're asking A to do, you can do a billion times. If the retailer takes 30 seconds to chain hashes, you can take 30 billion CPU-seconds and find out all the possibilities. (even if they weren't in your smaller set.) the space of entropy is just not large enough. but ZKP's can still work. Meni, does a ZKP interactive proof exist for this domain? 212.96.61.236 (talk) 04:13, 14 December 2014 (UTC)

I don't know of a ZKP system for the application in the OP. But I'm not a cryptographer and I wouldn't know if one exists.

In case you're asking about ZKPs in the Bitcoin domain, SNARKs (succinct non-interactive ZKPs) are used in Zerocash. -- Meni Rosenfeld (talk) 22:53, 14 December 2014 (UTC)

Even if you can create an effectively secure situation using hashes, and such, in principle, it can still be broken in P time - unless you are doing something else quite interesting. Nonetheless, with the above modifications (or clarifications), it is possible that a zkp does exist, even if it is not needed. It's an interesting question, I'd be curious if anyone comes up with an answer - even if down the road.Phoenixia1177 (talk) 08:36, 14 December 2014 (UTC)

I think it's doable if you involve a third party. A provides B with a hashing algorithm (or B provides A with the algorithm), but not the list of numbers. A and B each hash their lists of numbers, and send the hashed list to C. C compares the hashed lists and returns the identities of the values which match to A. If the number of queries to C is limited so that A cannot query for the entire phonebook, then neither A, B, or C can determine any information they did not already have, aside from the overlap between A's list and B's list. Neither A nor B have the other's list (hashed or unhashed), and while C has both lists, it does not have the hashing algorithm so cannot brute force it. Of course, this requires C to be independent (so it can't just get the hashing algorithm from A or B, or send A or B the other's list), so it's probably not what happens in practice. MChesterMC (talk) 09:35, 12 December 2014 (UTC)

I believe you can do it fairly easily supposing A and B have encryption keys such that A's encryption commutes with B's, which is fairly easy with a modulo encryption function. A encrypts their number v to A(v) and passes that to B. B encrypts the list to B(n1), B(n2) etc and passes those to A and also encrypts A(v) to BA(v) which is the same as AB(v) and passes that back to A. A can then encrypt B(n1) to AB(b1) etc and compare them to AB(v) and if there is a match they say they've found v in the list. Dmcq (talk) 10:20, 17 December 2014 (UTC)