fork download
copy 
  1. <?php
  2.  
  3. define('MAX_NUMBER', 70);
  4.  
  5. function factorial($value) {
  6.     return array_reduce(range(1, $value), function($carry,$item){return $carry*$item;}, 1);
  7. }
  8.  
  9. function R($value) {
  10.     return floor(2*sqrt(log(($value))));
  11. }
  12.  
  13. function make_chain($start, $length) {
  14.     $chain['start'] = $start;
  15.     for($i = 0; $i < $length; ++$i) {
  16.         $hash = factorial($start);
  17.         echo ">>> $start! == $hash\n";            // диагностическое сообщение
  18.         $start = R($hash);
  19.         if($start == 0) break;
  20.     }
  21.     $chain['end'] = $hash;
  22.     echo "Chain from ${chain['start']} to ${chain['end']} is ready.\n"; // диагностическое сообщение
  23.     return $chain;
  24. }
  25.  
  26. function make_chains($count, $length) {
  27.     $chains = [];
  28.     mt_srand();
  29.     for($i = 0; $i < $count; ++$i) {
  30.         $number = mt_rand(0, MAX_NUMBER - 1);                // начинаем цепочку с псевдослучайного слова
  31.         $chain = make_chain($number, $length);
  32.         $hash = $chain['end'];                               // используем конец найденной цепочки как индекс для быстрого поиска
  33.         if(!isset($chains[$hash])) $chains[$hash] = [];      // если такого хэша не было в корзине, инициализируем её
  34.         if(!in_array($chain['start'], $chains[$hash])) {     // проверяем на дубли
  35.             $chains[$hash][] = $chain['start'];              // добавляем начало цепочки в корзину
  36.         }
  37.     }
  38.     return $chains;
  39. }
  40.  
  41. function find_hash_in_basket($needle, $haystack_start, $haystack_end) {
  42.     echo "Роемся в цепочке от $haystack_start до $haystack_end.\n";       // диагностическое сообщение
  43.     $current_number = $haystack_start;
  44.     do {
  45.         $current_hash = factorial($current_number);         // <-- сюда вставьте нужную хэш-функцию
  46.         if($current_hash <= $needle && $needle <= $current_hash * ($current_number + 1)) {
  47.              return $current_number;                  // нашли
  48.         }
  49.         $current_number = R($current_hash);  // роем в глубину
  50.     } while($current_hash !== $haystack_end);
  51.     return false; // не нашли
  52. }
  53.  
  54. function search_hash($hash, $chains, $length) {
  55.     $current_hash = $hash;
  56.     for($i = 0; $i < $length; ++$i) {
  57.           if(isset($chains[$current_hash])) {                // нашли хэш в одной из корзин
  58.               echo "Лезем в корзину $current_hash.\n";       // диагностическое сообщение
  59.               foreach($chains[$current_hash] as $start) {    // роемся в корзине
  60.                   $result = find_hash_in_basket($hash, $start, $current_hash); // пытаемся найти в каждой из цепочек корзины
  61.                   if($result) {
  62.                       return $result;                        // конец поиска
  63.                   }
  64.               }
  65.           }
  66.           $next_number = R($current_hash);             // копаем в глубину
  67.           $current_hash = factorial($next_number);
  68.     }
  69.     return false; // не нашли
  70. }
  71.  
  72. ///////////////////// ПРИМЕР //////////////////////////////////
  73.  
  74.  
  75. $chains = make_chains(10, 5);
  76. echo "Радужные таблицы готовы.\n";
  77. var_dump($chains);
  78.  
  79. $hash = 721;
  80. echo "Пытаемся обратить $hash.\n";
  81. $number = search_hash($hash, $chains, 5);
  82. echo $number . "! <= $hash <= " . ($number+1) . "!\n";
  83.  
Success #stdin #stdout 0.02s 24548KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
>>> 18! == 6402373705728000
>>> 12! == 479001600
>>> 8! == 40320
>>> 6! == 720
>>> 5! == 120
Chain from 18 to 120 is ready.
>>> 63! == 1.9826083154044E+87
>>> 28! == 3.0488834461171E+29
>>> 16! == 20922789888000
>>> 11! == 39916800
>>> 8! == 40320
Chain from 63 to 40320 is ready.
>>> 38! == 5.230226174666E+44
>>> 20! == 2.4329020081766E+18
>>> 13! == 6227020800
>>> 9! == 362880
>>> 7! == 5040
Chain from 38 to 5040 is ready.
>>> 11! == 39916800
>>> 8! == 40320
>>> 6! == 720
>>> 5! == 120
>>> 4! == 24
Chain from 11 to 24 is ready.
>>> 54! == 2.3084369733924E+71
>>> 25! == 1.5511210043331E+25
>>> 15! == 1307674368000
>>> 10! == 3628800
>>> 7! == 5040
Chain from 54 to 5040 is ready.
>>> 21! == 5.1090942171709E+19
>>> 13! == 6227020800
>>> 9! == 362880
>>> 7! == 5040
>>> 5! == 120
Chain from 21 to 120 is ready.
>>> 60! == 8.3209871127414E+81
>>> 27! == 1.0888869450418E+28
>>> 16! == 20922789888000
>>> 11! == 39916800
>>> 8! == 40320
Chain from 60 to 40320 is ready.
>>> 18! == 6402373705728000
>>> 12! == 479001600
>>> 8! == 40320
>>> 6! == 720
>>> 5! == 120
Chain from 18 to 120 is ready.
>>> 15! == 1307674368000
>>> 10! == 3628800
>>> 7! == 5040
>>> 5! == 120
>>> 4! == 24
Chain from 15 to 24 is ready.
>>> 20! == 2432902008176640000
>>> 13! == 6227020800
>>> 9! == 362880
>>> 7! == 5040
>>> 5! == 120
Chain from 20 to 120 is ready.
Радужные таблицы готовы.
array(4) {
  [120]=>
  array(3) {
    [0]=>
    int(18)
    [1]=>
    int(21)
    [2]=>
    int(20)
  }
  [40320]=>
  array(2) {
    [0]=>
    int(63)
    [1]=>
    int(60)
  }
  [5040]=>
  array(2) {
    [0]=>
    int(38)
    [1]=>
    int(54)
  }
  [24]=>
  array(2) {
    [0]=>
    int(11)
    [1]=>
    int(15)
  }
}
Пытаемся обратить 721.
Лезем в корзину 120.
Роемся в цепочке от 18 до 120.
6! <= 721 <= 7!
https://ideone.com/Q22EXy
language:
PHP (php 7.3.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!