НовостиСобытияКонференцииФорумыIT@Work
Идеи и практики автоматизации:

Блог

Грядёт Криптокалипсис и мега-бюджеты

Сергей Бобровский
15.08.2013 11:20:23

Американский генерал тем временем развалил науку в Yahoo.

Перед обещанным обзорчиком BI-клиентов сделаю отступление в скучную (не для всех, конечно)) тему прикладной математики и околонаучных инноваций. Пост получился сумбурным, просто скорее подборка тематических новостей.

Хорошая весть пришла из яхи: Yahoo Labs наконец-то реформируется, и уже объявлены амбициозные планы посоревноваться в инновационных исследованиях и разработках с лабораториями Microsoft и Google. Yahoo Labs возглавила Marissa Mayer -- на смену генералу Рону Брэчману, некогда возглавлявшему аж военное агентство передовых исследований США DARPA. Пообещав в 2005-м ни много ни мало «создать новое будущее Интернета», генерал в итоге развалил всю научную деятельность Yahoo, а лучший яховский инноватор Prabhakar Raghavan в прошлом году сбежал от шефа-зануды, попытавшегося обучить гиков строевому шагу, в Google на должность вице-президента по инженерии. Перепало и Microsoft Research, куда перешли три ведущих научных сотрудника яхи, в том числе и Duncan Watts, автор модели Watts-Strogatz случайной генерации графов.

Очередные достижения вычислительной математики сделали возможными ранее невозможные вычисления -- например, подсчёт огромного количества знаков квадрата числа пи. Интересно, что сложность подсчёта разных физических и математических констант принципиально различна. Так, если для пи рассчитаны пять триллионов цифр, то например постоянная Каталана известна только в размере 31 миллиард цифр.
Один из новых подходов -- это т.н. формула Бэйли-Боруэйна-Плаффа, возможность вычисления n-й цифры пи без вычисления предыдущих цифр!

Какая красота:


Сам факт наличия подобных формул открывает принципиально новые пути к решению достаточно важных вычислительных задач. Так, суперкомпьютер IBM BlueGene/P за несколько недель работы рассчитал 4096 цифр постоянной Каталана, начиная со знака в позиции 10 триллионов!
Подробности: http://www.ams.org/notices/201307/rnoti-p844.pdf

Не менее удивительно, впрочем, предположение исследователей BBP-формул в отношении e -- для основания натуральных логарифмов такой формулы, похоже, не существует. И ещё одна грустная smile:) новость из этой серии -- тензорные вычисления (наверное, любой знакомый с ними скажет, что это очень сложно) оказались действительно формально сложными: доказано, что почти все они являются NP-Hard. Увы, но моделировать гравитацию и реализовывать алгоритмы машинного зрения придётся, похоже, по старинке -- медленно и печально.
Впрочем, небольшой шанс пока остаётся: работа названа «Most tensor problems are NP-hard», и возможно, что какие-то полезные тензорные «технологии» удастся «взломать».

В ходе 12th Privacy Enhancing Technologies Symposium студенты Drexel University получили первый приз за работу
https://www.cs.drexel.edu/~sa499/papers/anonymouth.pdf

В ней они решили задачу, обратную задаче определения плагиата: как модифицировать стиль письма так, чтобы по нему невозможно было определить авторство. На основе этого алгоритма создан общедоступный фреймворк-анонимизатор JStylo-Anonymouth: https://github.com/psal/anonymouth

Позиционируется он как средство маскировать посты в соцсетях, где человек участвует анонимно -- ведь даже если использовать невинный ник, автора всё равно сегодня можно вычислить по его авторскому стилю.

Страуструп, комментируя очередную победу российских ребят в ACM International Collegiate Programming Contest, интересно высказался в отношении своего детища С++: «code is where the rubber hits the road». Он попутно поругал Си за чрезмерную низкоуровневость, а Java за то, что она уводит программиста «слишком далеко от реальной машины, провоцируя излишне косвенное и запутанное мышление».

В заключение про криптографию. Буквально за несколько часов перед тем, как я прочитал эту новость, мне приснился сон, где какой-то профессор заявил, что современные технологии шифрования зашли в тупик)) И действительно, сон оказался в тему -- на хакерской Black Hat прозвучало, что нынешним технологиям шифрования с открытым ключом осталось жить от силы лет пять.
В технических деталях я не разбираюсь, вот материал «The Factoring Dead: Preparing for the Cryptycalypse» с конференции:
http://www.slideshare.net/astamos/bh-slides

Позитивный месседж этой новости для профильных компаний в том, что грядут без преувеличения эпические заказы (понятно, от кого -- госструктуры, банки, ...) на реализацию agile-технологий шифрования нового поколения. Соответствующие алгоритмы будут неполиномиальными, что позволит использовать очень длинные, практически невзламываемые ключи. Ближайшие же реализации будут опираться скорее всего на Elliptic Curve Cryptography, но это будет временное решение, так как эффективность ECC тоже далеко не оптимальна.

Комментариев: 0

Только зарегистрированные и авторизованные пользователи могут добавлять комментарии