Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.01.2011, 02:27
Новичок

Отправить личное сообщение для algol Посмотреть профиль Найти все сообщения от algol
 
Регистрация: 21.01.2011
Сообщений: 2

Нужен быстропроверяемый, но трудновычислимый алгоритм
Добрый день, господа математики и алгоритмисты,

потребовался такой специфический компьютерный алгоритм (функция), имеющий вполне конкретное практическое значение (см. ниже):

Основные свойства:
1) Вычисление результата достаточно трудоемко (O(n^2))
2) Проверка правильности результата (т.е. имея результат и вход) вычисляется очень быстро (O(1) или O(N))
3) Сам процесс вычисления не должен распараллеливаться, т.е. итерации вычисления должны быть зависимы от предыдущих итераций.

Дополнительные свойства:
4) Объем входных данных должен лежать примерно в диапазоне 8...256 бит.
5) Объем выходных данных (результата) должен лежать в диапазоне 8..256 бит
6) Сложность вычисления функции (время на вычисление функции) должно прямо зависеть от объема входных данных и иметь экспоненциальную зависимость (желательно O(n^2))
7) Сложность подбора результата (перебора всех возможных результатов) должен быть гораздо сложнее (не менее чем в сотни тысяч раз) честного вычисления.
8) Время вычисления функции на среднем современном компьютере при N-битном входе должно занимать ~2 секунды, (N+1)-битном ~4 секунды и т.д., где N - лежит в начале диапазона 8..256.
9) В идеале результат выполнения функции должен быть единственным, но если их много, то они должны быть равномерно (равновероятно) распределены по всему множеству возможных решений. Количество решений должно быть строго > 0.
10) Легкость в генерации входных данных. В идеале входные данные должны быть случайной последовательностью битов. В идеале любые входные данные должны быть пригодными для выбранной функции.

Что это может быть? Например, функция может быть решением какой-нибудь формулы, уравнения, в общем виде - какое-то вычисление, но, главное, правильность которого очень просто проверить.

Пример неправильной (непригодной) функции:
Дано: случайная последовательность N-бит.
Задача: найти такую строку S, хеширование которой (например, алгоритмом MD5), выдает на конце входные N-бит.
Честное решение: перебор на одном процессоре всех строк, начиная с однобайтовой и до "победы".
Проверка: вычислить хеш от результата, сравнить последние N-бит с входной последовательностью.
Плюсы: отлично масштабируется время вычисления в зависимости от длины входной последовательности, любая входная последовательность является пригодной для вычисления.
Почему не подходит: Поиск решения может полностью распараллеливаться на сотни, тысячи процессоров, что ускоряет поиск решения по сравнению с честным.

Другой пример может быть вычислением корня N-степенного уравнения.
Дано: коэффициенты при членах уравнения
Задача: найти корень уравнения с заданной наперед точностью
Честное решение: реализация какого-либо алгоритма решения уравнений N-ой степени
Проверка: решение уравнения с найденным неизвестным
Плюсы: Очень плохо распараллеливается, решение четкое, пошаговое по конкретному алгоритму. Количество возможных решений невероятно велико, перебор всех решений нецелесообразен.
Минусы: главный - нет гарантии, что решение существует при любых входных данных. Сложность задания входных данных, объем хранения которых может выйти за допустимые пределы (256, 512, на крайний случай 1024 бита). Нет зависимости сложности вычисления от входных данных, но если еще и задавать степенность уравнения, то зависимость будет, но не такая плавная, как хотелось бы.


Расскажу, для чего это вообще нужно: в итоге это будет альтернативным вариантом капчи (думаю все знают что это такое), противостоящая спамерам.
Т.е., например, при регистрации пользователя на каком-нибудь сайте вместо картинки с буковками или собачками пользователю выдается входная последовательность и ожидается результат вычисления искомой функции. Пользователю не остается ничего иного, как запустить механизм вычисления (неважно как, откуда, где), подождать, скажем, 5 минут, ввести результат и тем самым подтвердить регистрацию.

Именно поэтому решение функции не должно разбиваться на сотни или тысячи компьютеров, чтобы спамеры не могли воспользоваться ботнетами.

Тем, кто дочитал до конца - спасибо за внимание.
  #2  
Старый 21.01.2011, 06:22
гocть

 
Сообщений: n/a

вы неграмотно используете математическую нотацию. O-большое - это верхняя граница на сложность алгоритма.. Нотация для нижней границы - это Omega-большое. Точная сложность - Theta.

n^2 операций при n=256 это совсем не трудоемко. Современные процессоры выполняют миллиарды операций в секунду. 65536 операций это несколько микросекунд.

Цитата:
Пример неправильной (непригодной) функции:
Дано: случайная последовательность N-бит.
Задача: найти такую строку S, хеширование которой (например, алгоритмом MD5), выдает на конце входные N-бит.
...
Почему не подходит: Поиск решения может полностью распараллеливаться на сотни, тысячи процессоров, что ускоряет поиск решения по сравнению с честным.
Да будь у тебя хоть трильон процессоров, "в лоб" случайный md5 ты никогда в жизни не расшифруешь. Там 128 бит, это надо 2^128 вариантов перебрать. И не в лоб тоже - согласно википедии, самая хитрая preimage-атака (так это по научному зовется) на md5 на сегодняшний момент не далеко от этой цифры ушла - "2^123.4 for full preimage and 2^116.9 for a pseudo-preimage"

Цитата:
Минусы: главный - нет гарантии, что решение существует при любых входных данных.
глупости, учи основную теорему алгебры

Цитата:
Пользователю не остается ничего иного, как запустить механизм вычисления (неважно как, откуда, где), подождать, скажем, 5 минут, ввести результат и тем самым подтвердить регистрацию.
размечтался.

1) javascript и компилируемые языки по скорости в десятки-сотни раз отличаются. 5 минут у пользователя в браузере - 5 секунд у спамера в программе на с++. а какой-нибудь activex плагин для ускорения расчетов ты нынешнему пользователю уже не впаришь. не 90-е на дворе

2) что мешает спамеру за копейки понакупить машин от amazon elastic cloud, или ботнет от хакеров, и параллельно щелкать там все ваши капчи. каждая капча = 5 минут последовательных вычислений, на одном из тысяч серверов.
  #3  
Старый 21.01.2011, 12:20
Новичок

Отправить личное сообщение для algol Посмотреть профиль Найти все сообщения от algol
 
Регистрация: 21.01.2011
Сообщений: 2

Сообщение от гocть Посмотреть сообщение
вы неграмотно используете математическую нотацию. O-большое - это верхняя граница на сложность алгоритма.. Нотация для нижней границы - это Omega-большое. Точная сложность - Theta.
За неграмотность прошу прощения, я не математик по образованию.

Сообщение от гocть Посмотреть сообщение
n^2 операций при n=256 это совсем не трудоемко. Современные процессоры выполняют миллиарды операций в секунду. 65536 операций это несколько микросекунд.
Вы неправильно поняли и как-то неправильно посчитали. При N=256 (бит входящих данных) операций будет 2^256 (это очень много).

Сообщение от гocть Посмотреть сообщение
Да будь у тебя хоть трильон процессоров, "в лоб" случайный md5 ты никогда в жизни не расшифруешь. Там 128 бит, это надо 2^128 вариантов перебрать.
Здесь вы тоже недопоняли. В первом примере неправильной функции я указал для входа N-бит. Т.е. задача, например, будет подобрать 3 байта (24бита) хеша, а это проходит достачно быстро.

Сообщение от гocть Посмотреть сообщение
глупости, учи основную теорему алгебры
Извините, а где тут я не прав? Или вы утверждаете, что для любых коэфициентов уравнения гарантированно существует корень? Хотя если работать еще с мнимыми числами - то да, видимо, вы правы.


Сообщение от гocть Посмотреть сообщение
1) javascript и компилируемые языки по скорости в десятки-сотни раз отличаются.
Оставьте решение этой задачи мне.

Сообщение от гocть Посмотреть сообщение
2) что мешает спамеру за копейки понакупить машин от amazon elastic cloud, или ботнет от хакеров, и параллельно щелкать там все ваши капчи.
Да, тут вы абсолютно правы, но здесь все упирается в стоимость таких вычислений. Вычисления в амазоне не такие уж и дешевые. И мы все прекрасно понимаем, что взломать можно любую систему, имея неограниченные финансовые средства.

Я вам открою секрет: нынешние капчи (циферки и собачки) сейчас "щелкаются" на преотлично по сотням в час нанятыми для этого индусами, у спамеров есть даже специальные сервисы для этого.

Я прекрасно вижу недостатки этого подхода, и всеравно прошу у вас помощи в нахождении такой функции!
  #4  
Старый 21.01.2011, 16:26
гocть

 
Сообщений: n/a

Сообщение от algol Посмотреть сообщение
Вы неправильно поняли и как-то неправильно посчитали. При N=256 (бит входящих данных) операций будет 2^256 (это очень много).
вы написали n^2, а не 2^n.

или в уме вы все это время держали 2^n?

Цитата:
Извините, а где тут я не прав? Или вы утверждаете, что для любых коэфициентов уравнения гарантированно существует корень? Хотя если работать еще с мнимыми числами - то да, видимо, вы правы.
да, комплексный корень есть всегда

Цитата:
Да, тут вы абсолютно правы, но здесь все упирается в стоимость таких вычислений. Вычисления в амазоне не такие уж и дешевые.
$0.085 в час => $1 покупает 12 часов => 12*60/5=144 капч за $1

дешевле чем у ваших индусов
  #5  
Старый 04.04.2011, 19:01
_persicum_

 
Сообщений: n/a

Ответ в принципе широко известен - это разложение на множители или дискретный логарифм. Правда, размер чисел конечно не будет прямо так вписываться во многочисленные дополнительные ограничения, поставленные автором. Но пусть роет в эту сторону...
  #6  
Старый 04.04.2011, 19:07
_persicum_

 
Сообщений: n/a

От самого дискретного логарифма можно брать MD5 скажем и уже его высвечивать, если нужно 128 бит. Ничего другого кроме разложения на множители или дискретного логарифма в принципе нет в современном программизьме, чтобы вычислялось тяжело, а проверялось ляхко.
  #7  
Старый 07.04.2011, 10:13
_persicum_

 
Сообщений: n/a

ну и третий вариант - нахождение прообраза какой-нить ХЭШ функции, например MD5 или SHA1. Его проще всего реализовать, но и проще всего распараллелить или затабулировать.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
нужен алгоритм трассировки лучем Not Goth Вычислительная геометрия 1 20.06.2009 22:11
Нужен эффективный алгоритм Argon Математические алгоритмы 8 22.05.2008 06:57
нужен алгоритм решения задачи Neeka Математические алгоритмы 4 17.05.2008 19:09
Бинарная сортировка. Нужен алгоритм на паскале vovs Сортировка и поиск 2 10.12.2007 14:12
срочно, нужен алгоритм XakDN Вычислительная геометрия 0 21.12.2006 14:47