3
$\begingroup$

I have a map $f:X\to \mathbb{N}$ and I wish to find $x,x'\in X$ such that $f(x)=f(x')$. Since such elements are rare, I will have to check very many elements and perform many comparisons, so I suspect the best way to do this is using an ordered tree data structure, which stores elements $x\in X$ by comparing their values $f(x)$, and tells if an element with same value is already in the tree.

Is there an OrderedTree data structure (or something similar, e.g. ordered list) implemented in Mathematica?

$\endgroup$
  • $\begingroup$ I there anything known about f, so one can use this to minimize the amount of work? $\endgroup$ – mgamer Jan 23 '15 at 6:59
  • 2
    $\begingroup$ Have a look at DownValues. I suspect that will serve you better. Basically you'd be storing values to give an "inverse" of f (quotes because it is multivalued), and any time one was encountered for some x', you'd have your corresponding x stored. $\endgroup$ – Daniel Lichtblau Jan 23 '15 at 15:56
  • 1
    $\begingroup$ @mgamer: Concretely, my function is y=StringTake[IntegerString[Hash[x,"SHA256"],16],-13];] where x=ToString@RandomInteger[1,1000000]. $\endgroup$ – Leon Jan 23 '15 at 22:54
  • $\begingroup$ @DanielLichtblau Hmm, in the Help manual and on the net, I did not find any command to obtain the preimage of f via DownValues. Any suggestions? $\endgroup$ – Leon Jan 24 '15 at 0:17
  • $\begingroup$ What's X ....? $\endgroup$ – alancalvitti Jan 24 '15 at 2:57
3
$\begingroup$
f[x_] := StringTake[IntegerString[Hash[ToString@x, "SHA256"], 16], -4]
(* tiny version of requested function *)

Clear[collision];
collision::usage = "store potential collisions as downvalues";

collision[_] = {};

Block[
  {y},
  For[i = 1, i <= 1000, i++,
   y = f[i];
   collision[y] = Append[collision[y], i]
   ]
  ];

Sort[Select[#[[1, 1, 1]] -> #[[2]] & /@ DownValues[collision], 
  Length[#[[2]]] > 1 &]]

Out[100]= {"1309" -> {202, 562}, "19db" -> {24, 597}, "4c33" -> {292, 329}, 
 "6a67" -> {98, 864}, "e10c" -> {214, 538}, "f256" -> {722, 899}}

Downvalues (as @DanielLichtblau states) have nice properties for writing and retrieving even as the number of stored instances gets quite large, much better than tree coded up the hard way. (That said, this coder does not expect success for the OP for a collision found for the desired function.)

(Forgive my Pythonesque MMA coding style)

$\endgroup$
  • 1
    $\begingroup$ Thank you, I found a collision for 10-digit function, but not for a 13-digit. $\endgroup$ – Leon Jan 24 '15 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.