General First Order Matrix Difference System — Existence and Uniqueness via New Lattice Based Cryptographic Construction

Abstract

This paper is concerned with the existence and uniqueness of solutions to two-point boundary value problems associated with general first order matrix difference systems. Modified Gram—Schmidt process and modified QR-algorithm are presented to find the best least square solution of the system of equations. An efficient closest point search algorithm is presented to further improve the best least square solution. Modified encoding and decoding algorithms are presented in the process of finding shortest lattice vector.

Рассмотрено существование и единственность решений двухточечных граничных задач, связанных с обобщенными матричными разностными системами первого порядка. Для нахождения наилучшего решения системы уравнений методом наименьших квадратов использован модифицированный процесс Грама—Шмидта и модифицированный QR-алгоритм. Для дальнейшего улучшения решения наименьших квадратов представлен эффективный алгоритм поиска ближайшей точки. В процессе нахождения кратчайшего вектора решетки получены модифицированные алгоритмы кодирования и декодирования.

Розглянуто існування та єдиність розв’язувань двоточечних граничних задач, зв’язаних з узагальненими матричними різницевими системами першого порядку. Для пошуку найкращого розв’язування системи рівнянь методом найменших квадратів використано модифікований процес Грама—Шмідта і модифікований QR-алгоритм. Для подальшого покращення розв’язування найменших квадратів наведено ефективний алгоритм пошуку найближчої точки. У процесі пошуку найкоротшого вектора решітки знайдено модифіковані алгоритми кодування та декодування.