Аннотация доклада.

Задачи представления регулярных языков в виде конкатенации языков из фиксированного множества обладают высокой алгоритмической сложностью. Даже в случае разложения конечных языков известные алгоритмы имеют экспоненциальную сложность. В докладе рассматриваются основные проблемы криптосистем с открытым ключем и исследуется возможность построения такой системы на основе разложения регулярных языков.