ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
Повышение быстродействия и обеспечение безопасности и надежности программной реализации алгебраических преобразований в системах передачи и защиты информации и в задачах классификации текстовых документов путем решения комплекса задач по темам 1 Обоснование эффективных алгоритмов кодирования и декодирования двоичных кодов. 2. Исследование алгоритмов умножения в некоторых конечных кольцах и их применение для извлечения корней произвольной степени и решения алгебраических уравнений. Обоснование эффективных алгоритмов извлечения квадратных и кубических корней и решения уравнений невысокой степени над некоторыми конечными полями характеристики, малой относительно порядка поля. Построение новых эффективных алгоритмов умножения и деления в башнях конечных полей нечетной характеристики с использованием различных типов базисов в этих полях. 3. Создание новых алгоритмов матричного умножения на распределенных вычислительных ресурсах, а также на кристалле. 4,а. Получение нового доказательства условия безопасности схемы Блома общего вида и уточнение условия ее вскрытия, систематизация неинтерактивных протоколов с нулевым разглашением. 4,б. «Обоснование алгоритмов вычисления комбинаторных блок-схем, порядок которых есть степень простого числа, в задачах предварительного распределения ключей в компьютерной сети и выбора структуры вычислительной сети» 5.Минимизация числа сравнений в задаче сортировки. 6. Исследование метода сокращения избыточности данных посредством поиска похожих частей полиномов при классификации с помощью метода опорных векторов с целыми коэффициентами, глубоких нейронных сетей и других методов в задачах классификации текстовых документов. 7. Исследование некоторых методов и программных инструментальных средств организации и реализации компьютерных экспериментов при исследовании и изучении алгоритмов компьютерной алгебры и криптографических протоколов.
The project is devoted to the problems of increasing the reliability and efficiency of computer implementation of algebraic transformations and operations in encoding-decoding and information protection systems, as well as in text document classification systems. The approach to their solution involves the analysis and construction of efficient algorithms with appropriate estimates of complexity, analysis of security and conditions for breaking some cryptographic protocols. On the basis of constructions of generalized Fibonacci codes, a sequence of Boolean functions is constructed, the depth of which in a monotone basis exceeds the binary logarithm of the complexity of formulas by c> 1.06 times. Thus, the non-uniformity of the basis M is established, that is, impossibility of full parallelization of computations in it. Algorithms are obtained for extracting square and cube roots and for solving arbitrary equations of no higher than the fourth degree over some finite fields whose bit complexity in order of magnitude exceeds the complexity of multiplication in these fields by a factor equal to the double logarithm of the field order. An overview of the current state of the theory of fast algorithms for multiplying numbers and polynomials is given. The process of evolution of multiplication methods from the first block algorithms of Karatsuba and Toom of the 1960s to the methods of the 1970s, based on the discrete Fourier transform (DFT), and further to the newest methods developed in 2007–2019, is considered. Also, there are highlighted models of computations in which multiplication has linear or quadratic complexity. We prepared a survey of the results obtained by V.M. Khrapchenko, one of the pioneers of Russian theoretical cybernetics. A new modification of the Coppersmith algorithm is proposed for multiplying block vectors, the width of which is equal to the length of a machine word, one by another and by square matrices. There is considered a case when the coefficients lie in a field of two elements. The obtained results can be applied to Boolean matrices without significant changes. The proof of the unconditional security (k, m) of the Blom scheme with respect to the compromise of key materials of m participants is obtained. It is shown that to break the (k, m) -Blom scheme, it is sufficient to use exactly as many definite coefficients m + 1 of compromised polynomials as there are in the non-redundant representation of the original symmetric polynomial. There are considered methods and algorithms for the distributed computation of blocks and dual blocks of cyclic and acyclic projective geometries, as well as linear and quadratic transversal combinatorial block schemes, whose order is a prime power. The algebraic aspects of the construction and application of wireless sensor networks based on combinatorial block diagrams are discussed in a constructive way. A new method of sorting via group insertions is proposed. It achieves a new upper bound for the number of comparisons in the worst case and, as a consequence, on the average. Two ways to save memory when using integer fully connected neural networks have been developed. Software has been developed for combining the capabilities of the MPEI Algebraic Processor and the Sage computer algebra system, which made it possible to use this system for [multilateral computations on computers remotely remote from one another] distributed computations?, in particular for computer modeling of cryptographic protocols. IT solutions for modeling cryptographic protocols for educational purposes are obtained. The results are published in 15 scientific articles (including 8 indexed in Scopus and WoS, 11 from the list of the Higher Attestation Commission), two textbooks and 11 abstracts in the proceedings of five International conferences.
грант РФФИ |
# | Сроки | Название |
1 | 24 января 2019 г.-1 января 2020 г. | Построение эффективных алгоритмов для систем кодирования и защиты информации и для задач распознавания образов |
Результаты этапа: | ||
2 | 1 января 2020 г.-1 января 2021 г. | Построение эффективных алгоритмов для систем кодирования и защиты информации и для задач распознавания образов |
Результаты этапа: |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".