[erlang-questions] Pointless md5 Problem

[Colin Z]

So I came across a pointless/impossible problem someone had about md5
hashing. The goal is to find an MD5 hash that hashes to itself: MD5( X ) = X

My goal in coming up with a solution "finder" was just as an exercise in
distributed Erlang, not necessarily to achieve the near impossible and brute
force the problem.

I wrote up a quick and dirty distributed app, but the performance seems
really bad (around 10,000 keys/sec on a 3700+ Athlon) It scales nicely, but
10,000 keys/sec/machine is terrible when other languages can get 1M+/sec
(some CUDA GP/GPU implementations get 300M+/sec)

So, now my interest lies in what's so slow about my code....maybe it's
Erlang's md5 implementation, or more probably how I'm generating the random
string?

What does everyone think?


-module(md5id).

-export([start/0]).
-export([recv/1]).
-export([start_slave/1]).
-export([spawner/2]).
-export([checkMD5/2]).
-export([randomHexString/0]).
-export([randomHex/0]).

start()->

    register(receiverProc, self()),

    SpawnerPid = spawn(?MODULE, spawner, [0, receiverProc]),

    recv(0),

    io:fwrite("Exiting~n"),
    exit(SpawnerPid, done)
.

recv(T)->
    receive
        {found, String} ->
            io:fwrite("Found the Identity String: ~p~n", [String])
        ;
        {checked, Count} ->
            T1 = T + Count,
            io:fwrite("Checked ~p hashes so far~n", [T1]),
            recv(T1)
        ;
        {connected, Node}->
            io:fwrite("Node ~p connected to help out~n", [Node]),
            recv(T)
    end
.


start_slave(MasterNodeName)->
    pong = net_adm:ping(MasterNodeName),
    {receiverProc, MasterNodeName} ! {connected, node()},
    spawn(?MODULE, spawner, [0, {receiverProc, MasterNodeName}])
.

%% send an update message after every 10,000 keys
spawner(10000, ReceiverPid)->
    ReceiverPid ! {checked, 10000},
    spawner(0, ReceiverPid)
;
spawner(N, ReceiverPid)->
    spawn(?MODULE, checkMD5, [randomHexString(), ReceiverPid]),
    spawner(N+1, ReceiverPid)
.


checkMD5(String, ReceiverPid)->

    Hashed = lists:flatten([io_lib:format("~.16b",[N]) || N <-
binary_to_list(erlang:md5(String))]),
    case Hashed == String of
        true ->
            ReceiverPid ! {found, String}
        ;
        false ->
            ok
    end
.


randomHexString()->
    lists:flatten( lists:foldl( fun(_X, Accumulator) -> [randomHex() |
Accumulator] end, [], lists:seq(1,32) ) )
.

randomHex()->
    N = random:uniform(16)-1,
    Hex = io_lib:format("~.16b",[N]),
    lists:flatten(Hex)
.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20090506/5c74a553/attachment.htm>