| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > генерация списка поралей |
| Автор: Shadowlord 21.5.2011, 17:59 |
| Для демонстрации работы кластера решили написать не большую программку по полному перебору паролей. Проблема стала как разделить генерацию пароле между узлами. То есть у нас есть алфавит, количество узлов и максимальная длина пароля. Нужно что бы каждый узел генерировал для себя часть общего списка паролей и в сумме они перекрывали все множество. Появилась идея каждому узлу отдавать n количество символов и что бы он генерировал только пароли начинающиеся на один из этих символов. Запутался пытаясь описать алгоритм. |
| Автор: esperanto 21.5.2011, 18:39 |
| Если паролей х, а кластеров м, то каждому из м, кластеров дайте с генирировать м\х паролей упорядоченых в лексикографическом порядке. Если не хотите заморачиваться с алгоритмом, пусть каждый из кластеров сгенерирует просто случайно х\м* 2логарифм(х) паролей. |
| Автор: Shadowlord 21.5.2011, 18:54 |
| esperanto, А при таком случайном подходе, с какой вероятностью мы закроем все множество паролей ? |
| Автор: esperanto 22.5.2011, 09:38 |
| С вероятностью стремящейся к нолю с экспоненциальной скоростью. Можно получить точную оценку используя неравенство Чернова, например |
| Автор: Silent 22.5.2011, 21:39 |
| Блин, дожили - кластер появляется вперед умений писать параллельные программы. считаем количество возможных паролей (N!, N - мощность алфавита), делим на количество узлов M - столько паролей каждому (последнему может и не хватить, ну и пусть). Запускаем эти самые M процессов, каждому передаем два параметра - с номера какого пароля начинать, и сколько всего паролей обрабатывать. 100% покрытие (и тут смайлик в черных очках и с жевательной резинкой). |