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?

Improve this question
$\endgroup$
6
  • $\begingroup$ I there anything known about f, so one can use this to minimize the amount of work? $\endgroup$
    – mgamer
    Jan 23, 2015 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, 2015 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$
    – Leo
    Jan 23, 2015 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$
    – Leo
    Jan 24, 2015 at 0:17
  • $\begingroup$ What's X ....? $\endgroup$
    – alancalvitti
    Jan 24, 2015 at 2:57

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you, I found a collision for 10-digit function, but not for a 13-digit. $\endgroup$
    – Leo
    Jan 24, 2015 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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