<?php

define('MAX_NUMBER', 70);

function factorial($value) {
    return array_reduce(range(1, $value), function($carry,$item){return $carry*$item;}, 1);
}

function R($value) {
    return floor(2*sqrt(log(($value))));
}

function make_chain($start, $length) {
    $chain['start'] = $start;
    for($i = 0; $i < $length; ++$i) {
        $hash = factorial($start);
        echo ">>> $start! == $hash\n";            // диагностическое сообщение
        $start = R($hash);
        if($start == 0) break;
    }
    $chain['end'] = $hash;
    echo "Chain from ${chain['start']} to ${chain['end']} is ready.\n"; // диагностическое сообщение
    return $chain;
}

function make_chains($count, $length) {
    $chains = [];
    mt_srand();
    for($i = 0; $i < $count; ++$i) {
        $number = mt_rand(0, MAX_NUMBER - 1);                // начинаем цепочку с псевдослучайного слова
        $chain = make_chain($number, $length);
        $hash = $chain['end'];                               // используем конец найденной цепочки как индекс для быстрого поиска
        if(!isset($chains[$hash])) $chains[$hash] = [];      // если такого хэша не было в корзине, инициализируем её
        if(!in_array($chain['start'], $chains[$hash])) {     // проверяем на дубли
            $chains[$hash][] = $chain['start'];              // добавляем начало цепочки в корзину
        }
    }
    return $chains;
}

function find_hash_in_basket($needle, $haystack_start, $haystack_end) {
    echo "Роемся в цепочке от $haystack_start до $haystack_end.\n";       // диагностическое сообщение
    $current_number = $haystack_start;
    do {
        $current_hash = factorial($current_number);         // <-- сюда вставьте нужную хэш-функцию
        if($current_hash <= $needle && $needle <= $current_hash * ($current_number + 1)) {
             return $current_number;                  // нашли
        }
        $current_number = R($current_hash);  // роем в глубину
    } while($current_hash !== $haystack_end);
    return false; // не нашли
}

function search_hash($hash, $chains, $length) {
    $current_hash = $hash;
    for($i = 0; $i < $length; ++$i) {
          if(isset($chains[$current_hash])) {                // нашли хэш в одной из корзин
              echo "Лезем в корзину $current_hash.\n";       // диагностическое сообщение
              foreach($chains[$current_hash] as $start) {    // роемся в корзине
                  $result = find_hash_in_basket($hash, $start, $current_hash); // пытаемся найти в каждой из цепочек корзины
                  if($result) {
                      return $result;                        // конец поиска
                  }
              }
          }
          $next_number = R($current_hash);             // копаем в глубину
          $current_hash = factorial($next_number);
    }
    return false; // не нашли
}

///////////////////// ПРИМЕР //////////////////////////////////


$chains = make_chains(10, 5);
echo "Радужные таблицы готовы.\n";
var_dump($chains);

$hash = 721;
echo "Пытаемся обратить $hash.\n";
$number = search_hash($hash, $chains, 5);
echo $number . "! <= $hash <= " . ($number+1) . "!\n";