Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem
This paper presents criteria for the existence and uniqueness of solution to Kronecker product initial value problem associated with general first order matrix difference system. A modified least square method and a modified QR algorithm are developed to find the best least square solution of the Kr...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101603 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem / K.N. Murty, V.V.S.S.S. Balaram, K. Viswanadh // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 19-33. — Бібліогр.: 10 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101603 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1016032025-02-09T21:45:18Z Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem Murty, K.N. Balaram, V.V.S.S.S. Viswanadh, K. Математические методы и модели This paper presents criteria for the existence and uniqueness of solution to Kronecker product initial value problem associated with general first order matrix difference system. A modified least square method and a modified QR algorithm are developed to find the best least square solution of the Kronecker product of matrices. Using these methods as a tool the general solution of the Kronecker product initial value problem whose initial condition matrix is over determined is established. Using the method developed by Ishey Haviv and Îded Regev, on finding shortest vector problem we improve further the best least square solution. To boost the hardness factor we simply apply the standard Kronecker product or tensor product of lattices. Предложен критерий существования и единственности решения задачи кронекеровского произведения с начальными условиями, связанной с обобщенной разностной системой, имеющей матрицу первого порядка. Разработаны модифицированный метод наименьших квадратов и модифицированный QR алгоритм для нахождения наилучшего решения кронекеровского произведения матриц методом наименьших квадратов. Установлено, что при использовании этих методов для общего решения задачи кронекеровского произведения с начальными условиями ее матрица начальных условий является переопределенной. С использованием метода, разработанного Ishey Haviv и Оded Regev, при определении задачи кратчайшего вектора улучшено решение методом наименьших квадратов. Применено стандартное кронекеровское произведение или тензорное произведение на сетках для повышения коэффициента жесткости. Запропоновано критерій існування та єдиності розв’язку задачі кронекерового добутку з початковими умовами, яка пов’язана з узагальненою різницевою системою, що має матрицю першого порядку. Розроблено модифікований метод найменших квадратів і модифікований QR алгоритм для пошуку найкращого розв’язку кронекерового добутку матриць методом найменших квадратів. Встановлено, що при використанні цих методів для загального розв’язку задачі кронекерового добутку з початковими умовами її матриця початкових умов є переозначеною. З використанням методу, розробленого Ishey Haviv and Оded Regev, при визначенні задачі найкоротшого вектора покращено розв’язок методом найменших квадратів. Застосовано стандартний кронекерів добуток або тензорний добуток на сітках для збільшення коефіцієнта жорсткості. 2008 Article Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem / K.N. Murty, V.V.S.S.S. Balaram, K. Viswanadh // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 19-33. — Бібліогр.: 10 назв. — англ. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101603 519.816 en Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Математические методы и модели Математические методы и модели |
| spellingShingle |
Математические методы и модели Математические методы и модели Murty, K.N. Balaram, V.V.S.S.S. Viswanadh, K. Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem Электронное моделирование |
| description |
This paper presents criteria for the existence and uniqueness of solution to Kronecker product initial value problem associated with general first order matrix difference system. A modified least square method and a modified QR algorithm are developed to find the best least square solution of the Kronecker product of matrices. Using these methods as a tool the general solution of the Kronecker product initial value problem whose initial condition matrix is over determined is established. Using the method developed by Ishey Haviv and Îded Regev, on finding shortest vector problem we improve further the best least square solution. To boost the hardness factor we simply apply the standard Kronecker product or tensor product of lattices. |
| format |
Article |
| author |
Murty, K.N. Balaram, V.V.S.S.S. Viswanadh, K. |
| author_facet |
Murty, K.N. Balaram, V.V.S.S.S. Viswanadh, K. |
| author_sort |
Murty, K.N. |
| title |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem |
| title_short |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem |
| title_full |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem |
| title_fullStr |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem |
| title_full_unstemmed |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem |
| title_sort |
solution of kronecker product initial value problems associated with first order difference system via tensor— based hardness of the shortest vector problem |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2008 |
| topic_facet |
Математические методы и модели |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101603 |
| citation_txt |
Solution of Kronecker Product Initial Value Problems Associated with First Order Difference System via Tensor— based Hardness of the Shortest Vector Problem / K.N. Murty, V.V.S.S.S. Balaram, K. Viswanadh // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 19-33. — Бібліогр.: 10 назв. — англ. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT murtykn solutionofkroneckerproductinitialvalueproblemsassociatedwithfirstorderdifferencesystemviatensorbasedhardnessoftheshortestvectorproblem AT balaramvvsss solutionofkroneckerproductinitialvalueproblemsassociatedwithfirstorderdifferencesystemviatensorbasedhardnessoftheshortestvectorproblem AT viswanadhk solutionofkroneckerproductinitialvalueproblemsassociatedwithfirstorderdifferencesystemviatensorbasedhardnessoftheshortestvectorproblem |
| first_indexed |
2025-12-01T03:30:06Z |
| last_indexed |
2025-12-01T03:30:06Z |
| _version_ |
1850275068800663552 |
| fulltext |
ÓÄÊ 519.816
K. N. Murty
Aurora Engineering College
(Bhongir, Nalgonda Dist. A.P 508116, India,
E-mail: nkanuri@hotmail.com),
V.V.S.S.S Balaram
Aurora’s Technological and Research Institute
(Parvathapur, Uppal, Hyderabad — 500039, India,
E-mail: vadrevu_kinnera@yahoo.com),
K. Viswanadh
(1 Court Sq, Long Island City, NY — 11120,
E-mail: kasikv@hotmail.com)
Solution of Kronecker Product Initial
Value Problems Associated with First Order
Difference System via Tensor— based Hardness
of the Shortest Vector Problem
(Recommended by Prof. E. Dshalalow)
This paper presents criteria for the existence and uniqueness of solution to Kronecker product ini-
tial value problem associated with general first order matrix difference system. A modified least
square method and a modified QR algorithm are developed to find the best least square solution
of the Kronecker product of matrices. Using these methods as a tool the general solution of the
Kronecker product initial value problem whose initial condition matrix is over determined is es-
tablished. Using the method developed by Ishey Haviv and Îded Regev, on finding shortest vec-
tor problem we improve further the best least square solution. To boost the hardness factor we
simply apply the standard Kronecker product or tensor product of lattices.
Ïðåäëîæåí êðèòåðèé ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè ðåøåíèÿ çàäà÷è êðîíåêåðîâñêîãî
ïðîèçâåäåíèÿ ñ íà÷àëüíûìè óñëîâèÿìè, ñâÿçàííîé ñ îáîáùåííîé ðàçíîñòíîé ñèñòåìîé,
èìåþùåé ìàòðèöó ïåðâîãî ïîðÿäêà. Ðàçðàáîòàíû ìîäèôèöèðîâàííûé ìåòîä íàèìåíüøèõ
êâàäðàòîâ è ìîäèôèöèðîâàííûé QR àëãîðèòì äëÿ íàõîæäåíèÿ íàèëó÷øåãî ðåøåíèÿ
êðîíåêåðîâñêîãî ïðîèçâåäåíèÿ ìàòðèö ìåòîäîì íàèìåíüøèõ êâàäðàòîâ. Óñòàíîâëåíî,
÷òî ïðè èñïîëüçîâàíèè ýòèõ ìåòîäîâ äëÿ îáùåãî ðåøåíèÿ çàäà÷è êðîíåêåðîâñêîãî ïðîèç-
âåäåíèÿ ñ íà÷àëüíûìè óñëîâèÿìè åå ìàòðèöà íà÷àëüíûõ óñëîâèé ÿâëÿåòñÿ ïåðåîïðå-
äåëåííîé. Ñ èñïîëüçîâàíèåì ìåòîäà, ðàçðàáîòàííîãî Ishey Haviv è Îded Regev, ïðè
îïðåäåëåíèè çàäà÷è êðàò÷àéøåãî âåêòîðà óëó÷øåíî ðåøåíèå ìåòîäîì íàèìåíüøèõ êâàä-
ðàòîâ. Ïðèìåíåíî ñòàíäàðòíîå êðîíåêåðîâñêîå ïðîèçâåäåíèå èëè òåíçîðíîå ïðîèçâå-
äåíèå íà ñåòêàõ äëÿ ïîâûøåíèÿ êîýôôèöèåíòà æåñòêîñòè.
K e y w o r d s: product initial value problem, existence and uniqueness of solution, the best least
square solution, shortest vector problem.
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 19
1. Introduction. Kronecker product or tensor product of matrices is an inte-
resting area of current research and a great deal of work has been done by many
authors in recent years [1—3]. The application of Kronecker product matrix sys-
tem has been extended to various fields of control engineering, method of lines
and systems engineering. The importance of Kronecker products of matrices
gained momentum because of its computational and notational advantages. In
Cryptography the closet point search problem and shortest vector problem
(SVP) associated with lattices are the two main computational problems. The
closed vector problem (CVP) is inhomogeneous variant of SVP, in which given
a lattice and some target point one has to find the closet lattice point. The hard-
ness part of lattice problem mainly comes from the fact that there are many pos-
sible bases for the same lattice. One of the main reasons for research on the hard-
ness of lattice problem is their application in Cryptography. In the year 2004
Ajtai [4], came up with a construction of Cryptography primitives, whose secu-
rity relies on the worst case of hardness of certain lattice problems.
In this paper we shall be concerned with the general two first-order matrix
difference systems of equations of the form:
x n A n x n( ) ( ) ( )� �1 ,
y n B n y n( ) ( ) ( )� �1 ,
where A n( ), B n( ) are square matrices of orders ( p p� ) and (q q� ) respectively
and whose components are all real defined on
N n n n n kn
0
0 0 0 0
1 2
�
� � � �{ , , , ..., , ...}
where k N�
�
and n N
0
� , N being the set of integers. Before, we present our re-
sults in this paper we need the following basic properties of the Kronecker prod-
uct of matrices.
If A R m n
�
�
and B R p q
�
�
then the Kronecker product (or tensor product) of
A and B denoted by ( )A B� is defined as the partition matrix
( )A B
a b a b
a b a b
n
m mn
� �
�
�
�
11 1
1
�
� � �
�
and is in R mp nq�
.
The Kronecker product matrices defined above has the following proper-
ties:
( ) ( )A B A BT T T
� � � ,
( ) ( ) ( )A B C D AC BD� � � � ,
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
20 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
( )A B A B� � �
� � �1 1 1
,
( ) ( ) ( ( ) ( ))A B n A n B n� � � � � �1 1 1 ,
where the matrices involved are of appropriate dimensions to be conformable for
multiplication and inversion. For example ( )A B A B� � �
� � �1 1 1
we implicitly
assumed that A and B are non-singular square matrices. Initially we are not mak-
ing use of the theory of generalized inverse of matrices; this concept will be used
in our later discussions in developing modified-Gram-Schmidt algorithm and in
encoding and decoding algorithms. Usually search problems involving lattices
can be solved using modifications and extensions of the closest-point algorithm.
Given a lattice ��R m
, the shortest vector problem is to find a vector in ��{ }0
that has the smallest Euclidean norm. In fact, the history of the shortest vector
problem is closely interlinked with that of the closest point problem. Further, the
closest point algorithm can be straight forwardly modified to solve the shortest
vector problem [5].
This paper is organized as follows: in section 2 we present the general solu-
tion of the homogeneous Kronecker product difference system and then present
the general solution of the Kronecker product initial value problem; section 3 is
concerned with the method of least squares for Kronecker product system of
equations. We develop the method of least square problems to solve the Kro-
necker product system by using modified QR-algorithm. Section 4 provides a
brief work of khots work [6] together with the minor modifications; we boost the
hardness factor of the standard tensor product of lattices. To our belief it im-
proves the best least square solution and SVP technique further improves the ex-
isting methods to find the best least square solution of the Kronecker product ini-
tial value problem.
2. General solution of the kronecker product initial value problem. In
this section, the general form of the Kronecker product difference equation we
consider is of the form
[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( ) ( )]P n R n X n Y n Q n S n X n Y n� � � � � � � �1 1 0 , (1)
where P n( ), Q n( ) are invertible square matrices of order ( p p� ) and R n( ), S n( )
are square matrices order (q q� ) and x(n) and y(n) are vectors of orders ( p�1) and
(q�1) respectively. We now present the general solution of (1) in terms of funda-
mental matrix solutions of P n x n Q n x n( ) ( ) ( ) ( )� � �1 0 and R n y n( ) ( )� �1
� �S n y n( ) ( ) 0 in the next theorem.
Theorem 1. [ ( ) ( )]� �n n� is a fundamental matrix of (1) if and only if
� ( )n and � ( )n are fundamental matrices of P n x n Q n x n( ) ( ) ( ) ( )� � �1 0 and
R n y n S n y n( ) ( ) ( ) ( )� � �1 0 respectively.
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 21
P r o o f. Suppose�( )n and� ( )n are fundamental matrices of P n x n( ) ( )� �1
� �Q n x n( ) ( ) 0 and R n y n S n y n( ) ( ) ( ) ( )� � �1 0 respectively. Then
[ ( ) ( )] [ ( ) ( ) ( ) ( )][ ( ) ( )]� � � �n n P n Q n R n S n n n� � � � � �
� �
1 1
1 1
�
� � � �
� �
[ ( ) ( )][ ( ) ( )][ ( ) ( )]P n R n Q n S n n n1 1
� � .
Hence
[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( ) ( )P n R n n n Q n S n n n� � � � � � � �� � � �1 1 0] .
Hence [ ( ) ( )]� �n n� is a fundamental matrix of (1). Conversely, suppose
[ ( ) ( )]� �n n� be a fundamental matrix of (1). Then
[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( ) ( )]P n R n n n Q n S n n n� � � � � � � �� � � �1 1 0 .
Therefore
[ ( ) ( )] [ ( ) ( )][ ( ) ( )][ ( ) ( )� � �n R n P n R n Q n S n n n� � � � � �
� �
1
1 1
] .
This implies
[ ( ) ( ) ( ) ( )] [( ) ( ) ( ) (� � �n P n Q n n I I n R n S nq p� � � �� � � �
� �
1 1
1 1
) ( )]� n .
This relation is true if and only if � � � �
�
[ ( ) ( ) ( ) ( )]� �n P n Q n n I q1
1
and
� � �
�
� �( ) ( ) ( ) ( )n R n S n n1
1
are either identity matrices or null matrices of ap-
propriate dimensions. Thus, we have the following two cases.
Case 1:
� � � �
�
[ ( ) ( ) ( ) ( )]� �n P n Q n n I p1
1
and � �( ) ( ) ( ) ( )n R n S n n I q� � �
�
1
1
.
Then
� �( ) [ ( ) ( ) ( )]n I P n Q n np� � � �
�
1
1
and � �( ) ( ) ( ) ( )n I R n S n nq� � �
�
1
1
.
Case 2:
[ ( ) ( ) ( ) ( )]� �n P n Q n n I p� � �
�
1
1
and ��� �( ) ( ) ( ) ( )]n R n S n n I q� � �
�
1
1
.
Then
� �( ) ( ) ( ) ( )n I P n Q n np� � �
�
1
1
and � �( ) [ ( ) ( ) ( )]n I R n S n nq� � � �
�
1
1
.
Case 1 and 2 contradict each other. Thus
� � � �
�
[ ( ) ( ) ( ) ( )]� �n P n Q n n O p1
1
and � � � �
�
�� �( ) ( ) ( ) ( )]n R n S n n Oq1
1
.
Thus� ( )n and � ( )n are fundamental matrices of P n x n Q n x n( ) ( ) ( ) ( )� � �1 0
and R n y n S n y n( ) ( ) ( ) ( )� � �1 0 respectively.
Theorem 2. Any solution of the Kronecker product system of difference
equations (1) satisfying [ ( ) ( )] [ ]x n y n C C
0 0 1 2
� � � is of the form
[ ( ) ( )] [ ( , ) ( , )][ ]x n y n n n n n C C� � � �� �
0 0 1 2
,
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
22 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
where � � �( , ) ( ) ( )n n n n
0
1
0
�
�
and � � �( , ) ( ) ( )n n n n
0
1
0
�
�
with the prop-
erty� ( , )n n I p0
� and � ( , )n n I q0
� .
P r o o f. Proof is elementary and hence omitted.
The above solution may conveniently be written as
[ ( ) ( )] [ ( ) ( )][ ]x n y n n n C C� � � �� �
1 2
, (2)
where C1 and C2 are constant column vectors of order p and q respectively. We
now consider the Kronecker product Initial value problem of the form:
[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( ) ( )]P n R n x n y n Q n S n x n y n� � � � � � � �1 1 0 , (3)
( )( ( ) ( ) ( ]M N x n y n
1 1 0 0 1 2
� � � �� � ,
where M
1
and N
1
are constant matrices of orders ( p p� ) and (q q� ) respectively
and�
1
is ( p�1) and�
2
is (q�1) column vectors. Substituting the general form so-
lution given in (2) in (3), we get
[ ][ ( ) ( )][ ] [ ]M N n n C C
1 1 0 0 1 2 1 2
� � � � �� � � � .
Hence
[ ] [ ] [ ( ) ( )] [ ]C C M N n n
1 2 1 1
1
0 0
1
1 2
� � � � � �
� �
� � � �
� � �
� � � �
[ ( ) ( )][ ]M n N n
1
1 1
0 1
1 1
0 1 2
� � � � .
We are now in a position to give the general solution of (1) satisfying (3) and
is given by
[ ( ) ( )] [ ( ) ( )][ ( ) ( )][x n y n n n M n N n� � � �
� � � �
� � � �
1
1 1
0 1
1 1
0
�
1 2
� �� ]
� �
� � � �
[ ( ) ( ) ( ) ( ) ]� � � �n M n n N n
1
1 1
0 1 1
1 1
0 2
� � .
The solution of the initial value problem when M
1
and N
1
are invertible is
unique. However when M
1
and N
1
are rectangular matrices of order (m p� ) and
(n q� ) respectively, we develop modified QR algorithm in the next section [7].
We now establish variation of parameters formula associated with the
non-homogenous first order difference system
[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( ) ( )]P n R n x n y n Q n S n x n y n� � � � � � � �1 1
� �[ ( ) ( )]F n F n
1 2
, (4)
where F n
1
( )and F n
2
( )are column vectors of order ( p�1) and (q�1) respectively.
Theorem 3. A particular solution of (4) is given by
[ ( ) ( )] [ ( ) ( )] [ ( ) ( )][ (x n y n n n Q i S i F i
i n
n
� �� � �
�
� �
�� �
0
1 1
1
) ( )]�F i
2
.
P r o o f. Any solution of the homogeneous system (1) is of the form
[ ( ) ( )] [ ( ) ( )][ ]x n y n n n C C� � � �� �
1 2
,
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 23
where � ( )n is a fundamental matrix of P n x n Q n x n( ) ( ) ( ) ( )� � �1 0 and � ( )n
is a fundamental matrix of R n y n S n y n( ) ( ) ( ) ( )� � �1 0.
Since a solution cannot be a solution of (4) unless [ ( ) ( )] [ ]F n F n
1 2
0 0� � � .
Therefore, we seek a particular solution of (4) in the form
[ ( ) ( )] [ ( ) ( )][ ( ) ( )]x n y n n n C n C n� � � �� �
1 2
.
Then
[ ( ) ( )][ ( ) ( )][ ( ) ( )]P n R n n n C n C n� � � � � � � �� �1 1 1 1
1 2
� � � � �[ ( ) ( )][ ( ) ( )] [ ( ) ( )]� �n n C n C n S F n F n
1 2 1 2
ince � �( ) ( ) ( ) ( )n P n Q n n� � �
�
1
1
and� �( ) ( ) ( ) ( )n R n S n n� � �
�
1
1
. We have
� � � � � � � �[ ( ) ( )][ ( ) ( )] [ ( ) ( )][ ( )Q n S n C n C n Q n S n C n C
1 2 1 2
1 1 ( )]n �
� � � � � � � � �
� �
[ ( ) ( ) ( ) ( )] [ ( ) ( )][ (� n C n C n C n Q n S n F1 1
1 2 2
1 1
1
n F n) ( )]�
2
,
�C Q n S n F n F nn � � � �
� �
[ ( ) ( )][ ( ) ( )]
1 1
1 2
or
C n Q i S i F i F i
i n
n
( ) [ ( ) ( )][ ( ) ( )]� � � �
�
� �
�
0
1 1
1 2
.
Therefore
[ ( ) ( )] [ ( ) ( )] [ ] [ ( ) (x n y n n n C C Q i S i
i n
n
� � � � � �
�
� �
�� �
1 2
1 1
0
)][ ( ) ( )]F i F i
1 2
�
�
�
�
�
�
� .
Thus, we have the following theorem.
Theorem 4. Any solution of the first order difference system (4) is of the
form
[ ( ) ( )] [ ( ) ( )][ ]x n y n n n C C� � � � �� �
1 2
� � � �
�
� �
�[ ( ) ( )] [ ( ) ( )][ ( ) ( )]� �n n Q i S i F i F i
i n
n
0
1 1
1 2
.
P r o o f is immediate.
3. Method of least squares. In this section, we develop a method for least
square problems to solve the Kronecker product system of equations
( )( )A B x y� � � �� �. (5)
We need the following results for constructing least square algorithm and
the best least square algorithm.
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
24 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Result 1. Let A be an (m � n) given matrix with rank p � min{m, n}. Then
there exists a factorization AP = QR with the following properties:
i) P is an (n n� ) permutation matrix with the first p columns of AP form a ba-
sis of
I A Ax R x Rm
m n
( ) { / }� � � ;
ii) Q is an (m p� ) matrix with orthonormal columns and R is a ( p n� ) upper
trapezoidal matrix of the form R R R� [ ]
1 2
, where R1 is a non-singular ( p p� ) up-
per triangular matrix and R2 is a ( p n p� � ) matrix.
Note that in (5), A is (m n� ) and B is ( p q� ) rectangular matrices. Suppose
that A and B are QR decomposed as A=Q1 R1 and B=Q2 R2, where Q1 is (m m� )
matrix with orthonormal columns, R1 is (m n� ) upper trapezoidal matrix where Q
is ( )p p� matrix with orthonormal columns and R2 is ( p q� ) upper trapezoidal
matrix. Assuming that full rank case, i.e. �( )A n m� and �( )B q p� , R1 is of
the form
R
r r r
r r
n
n
1
11
1
12
1
1
1
22
1
2
1
0
�
( ) ( ) ( )
( ) ( )
..............
�
�
............
.........................
( )
0 0
0 0 0
1
�
�
rnn
.
......
( )
( )
0 0 0
0
1
1
�
�
�
�
�
�R
�
,
where R ( )1
indicates an (n n� ) matrix and 0
1( )
indicates an (( )m n n� � ) null ma-
trix and similarly
R
r r r
r r
r
q
q
qq2
11
2
12
2
1
2
22
2
2
2
2
0
0 0
0 0 0
0
�
( ) ( ) ( )
( ) ( )
( )
�
�
�
�
0 0
0
2
2
�
�
�
�
�
�
�
�
R ( )
( )
where R ( )2
is a ( p p� ) matrix and 0
2( )
is ( p q q� � ) null matrix.
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 25
............................
...........................
Theorem 5. If A and B have a QR factorizations of the form Q1 R1 and Q2 R2
respectively, then A B� has a permitted QR factorizations as
( ) ( ) ( )( )A B Q R Q R Q Q R R� � � � � �
1 1 2 2 1 2 1 2
.
P r o o f. Consider
( ) ( ) ( ) ( )Q Q Q Q Q Q Q Q I I IT T T
m p mp1 2 1 2 1 1 2 2
� � � � � � � .
This implies Q Q
1 2
� is orthogonal also to Z R R
x
( )
1 2
0
� �
�
�
�
where � is
( )nq nq� square matrix, 0 is an (( )mp np nq� � ) null matrix and z is a permutation
matrix.
Theorem 6. ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )R R R R R R R RT
1 2 1 2
1 2 1 2
� � � � � .
P r o o f. We know that
( ) ( ) ( ) ( )R R R R R R R RT T T
1 2 1 2 1 2 1 2
� � � � � �
�
� � � �
�
r R
r R R
T
q p q p q p q p
T T
q
11
1
2
12
1
2 21
1
2
0 0 0 0
0 0
( )
( ) ( )
� � �
p q p q p
n
T
n
T
nn
T
q p q pr R r R r R
� �
�
0 0
0 0
1
1
2 2
1
2
1
2
� �
� �
�
( ) ( ) ( )
�
�
�
r R r R r R
r R r
n
p q
11
1
2 12
1
2 1
1
2
21
1
2
0
( ) ( ) ( )
( )
�
�
2
1
2
1
2
0 0
0 0 0
0 0 0
n
p q p q nn
p q p q p q
p q p q p q
R
r R
( )
( )
� �
� � �
� � �
�
�
�
�
�
�
.
The block element in block row i and block j column n element is given by
[( ) ( )] ( )(
min{ , }
( ) ( )R R R R r r RT
ij
l
i j
li lj
T
1 2 1 2
1
1 1
2
� � �
�
� R
2
), 1� �i j n, .
The element in row i and column j of ( )R RT
2 2
is given by
( )
min{ , }
( ) ( )R R r rT
k
i j
ki kj2 2
1
2 2
�
�
� , 1� �i j q, .
Thus ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )R R R R R R R RT T
1 2 1 2
1 2 1 2
� � � � � .
Theorem 7. � �
T
is the cholesky factorization of ( ) ( )A B A BT
� � , where
� � �( )
( ) ( )R R1 2
.
P r o o f.
( ) ( ) ( ) ( )A B A B Q R Q R Q R Q RT T
� � � � � �
1 1 2 2 1 1 2 2
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
26 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
.................................................................
..........................................
.........................................
� � � � � �[( )( )] [( )( )]Q Q R R Q Q R RT
1 2 1 2 1 2 1 2
� � � � � �( ) ( ) ( )( )R R Q Q Q Q R RT T
1 2 1 2 1 2 1 2
� � � �( ) ( )R R z z R RT T
1 2 1 2
� � � �[ ( )] [ ( )]z R R z R R GGT T T
1 2 1 2
� � � ,
where GT
is lower triangular.
Now, applying these results to our main problem
( ) ( ) ( )A B x y n� � � � �
0
� �
the least square solution ( )( )x y n�
0
to the normal equation
( ) ( ) ( )( ) ( ) ( )A B A B x y n A BT T
� � � � � �
0
� �
can be obtained from the equivalent equation
� � � �
T Tx y n A B h h( )( ) ( ) ( ) ( )� � � � � �
0 1 2
.
Since the coefficient matrix is the product of the upper and lower triangular ma-
trices, the solution can be computed by the usual two step procedure:
1. Solve by forward substitutions.
2. Solve � ( )( ) ( )x y n w z� � �
0
by backward substitutions.
If the dimension of � ( )nq nq� is too large to permit the direct solution of �,
the above two-step procedure can be further refined. Partition of each vector
( )w z� and ( )h h
1 2
� into n-sub-vectors, with each sub-vector of dimension
(q�1) be an (nq�1) matrix can be partitioned as ( )
( ) ( )w zi j
� for i = 1, 2, …, n and
j = 1, 2, …, q. Similarly ( )h h
1 2
� and the solution vectors ( )( )x y n�
0
are parti-
tioned. In step1, �
T w z h h( ) ( )� � �
1 2
may be written in partitioned form as
r R
r R r R
r
T
q q
T T
q
11
1 2
12
1 2
22
1 2
0 0
0
( ) ( )
( ) ( ) ( ) ( )
[ ]
[ ] [ ]
� �
� �
1
1 2
2
1 2 1 2
n
T
n
T
nn
TR r R r R( ) ( ) ( ) ( ) ( ) ( )
[ ] [ ] [ ]
�
�
�
�
�
�
�
�
�
�
�
�
!
!
!
( ) ( )
( ) ( )
( ) ( )
1
2
�
�
�
�
�
�
�
�
�
�
�
�
�
�
z
z
z
j
j
n j
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
h h
h h
h h
j
j
n j
1
1
2
1
2
2
1 2
( ) ( )
( ) ( )
( ) ( )
, j = 1, 2, …, q.
(6)
Since [ ]
( )R T2
is a lower triangular matrix, the forward substitution solution can
be carried out in n sub-steps which is given in the following algorithm.
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 27
.........................................................................
.................
Algorithm.
1. Solve r R z h hT j j
11
1 2 1
1
1
2
( ) ( ) ( ) ( ) ( ) ( )
[ ] ( ) ( )! � � � by forward substitution.
2. Solve r R h h r R zT j T j
22
1 2
1
2
2 12
1 2 1( ) ( ) ( ) ( ) ( ) ( ) ( ) (
[ ] [ ] [ ] [� � � �!
)
]by forward sub-
stitution.
3. Solve
r R xz h h rin Rnn
T n j n j( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
[ ] [ ) ( ) [
1 2
1 2
1 2
! � � � ] ( )
( ) ( )T j
i
n
z!
1
1
1
�
�
�
�
by forward substitution.
Thus ( )( )x y n�
0
can be completed without explicit II formulation of R by
this two-step approach.
The vector ( )h h
1 2
� defined in (6) can be constructed as follows:
( ) ( )A B h hT
� � � �� �
1 2
or
( ) ( ) ( ) ( ) ( ) ( ) ( )h h I M Q R M R I Qm
T T T T
m
T
1 2 2 2 2 2
� � � � � � � � �� � � �
� �
�
�
�
( )
( )
( )
(
( ) ( )
( ) ( )
( ) ( )
M R
Q
Q
Q
T T
T l
T l
T m l
2
2
1
2
2
2
� �
� �
� � )
( ) ( )
�
�
�
� � �M RT T
2 1
� �
"
, l =1, 2, …, p,
where
( ) ( ) ( )� � � �
"1 2
� � � � �I Qm
T
� � � � � � � �(( ) ( ) ( ) ( ) ( ) ( )Q R I R R R Q IT
p
T T T T
p1 1 2 1 1 1 2 1
� � � �
� �( )
( ) ( ) ( )
( ) ( )
R R
q I q I q I
q I q I
T T
p p m p
p
1 2
11
1
12
1
1
1
21
1
22
1
�
p m p
m p m p mm p
q I
q I q I q I
�
�
�
�
�
�
�
�
2
1
1
1
2
1 1
( )
( ) ( ) ( )
�
�
�
� � � �( ) ( ) ( )� � � �
1 1 1 2 2 2
R RT T
,
( )
....................
( )
( )
� �
� �
� �
#
$"%
#
$ %
2 2
2
2
2
� �
�
�
l
l
� �
#
$ %m l
�
�
�
�
2
( )
,
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
28 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
where
� � � �
#
$ % $ %k l
rk
k l
r
m
q� � �
�
�2
1
1 1
1
( ) ( ) ( )
( ), k m�1 2, ,..., ,
q Q Q q
rk
T k l
r
m
T
rk
k l
r
m
( ) ( ) ( ) ( )
( ) ( )
1
2
1
2
1
1
� � � �
$ % $ %
� � �
� �
� � .
Therefore ( ) ( ) ( ) ( )
( )A B R RT T T k l
� � � � �� � � �
#
$ %
1 2 2
. Proceeding from here
( ) ( )
( )
( )
( ) ( )
R R
R r
R r
T T k l
T l
T
1 2 2
2 11
1
2
2 1
� � �
�
� �
� �
#
$ %
#
$"%
2
1 1
2
2 22
1 2
2
2
1
( ) ( )
( ) ( )
( )
( )
( )
� �
� �
#
$ %
#
$ %
�
� �
l
T l
T
kn
k
R r
R r
�
� �
�
�
�
�
�
1
2
1
1
2
n
k l
jh h
h
( )
( )
( ) ( )
� �
#
$ %
1
2
2
1 2
( ) ( )
( ) ( )
�
�
�
�
�
h
h h
j
n j
,
i. e.
h h R ri j T
kj
k
l
k l
1 2 2
1
1
2
( ) ( ) ( ) ( )
( )� � �
�
� � �
#
$ %
for i =1, 2, …, n, j = 1, 2, …, q.
Thus the vector ( )h h
1 2
� can be computed block by block as needed without re-
quiring the large matrix as claimed.
4. Modified Gram Schmidt process. In this section, we extend the method
of modified Gram Schmidt process given in [7 ] to the Kronecker product system
of equations. For let A be an (m n� ) matrix with rank r m n� min{ , } and B be
a p q( )� matrix with rank s p q� min{ , }. Then there exists a factorization of the
matrices A and B of the form AP Q R1 1 1
� and BP Q R2 2 2
� , with the following
properties:
1) P1
and P 2
are (n � n) and (q � q) permutation matrices with the first r col-
umns of AP1
form a basis of I Am( ) and the first q columns of BP 2
form a basis
of I Bm( );
2) Q1
and Q 2
are (m � r) and (p � s) matrices both with orthnormal columns
and R1
and R 2
are (r � n) and (s � q) upper trapezoidal matrices to the form
R R R1
1
1
1
2
� [ ]
( ) ( )
and R R R2
2
1
2
2
� [ ]
( ) ( )
,
where R
1
1( )
and R
1
2( )
are non-singular (r � r) and (s � s) upper triangualar matrices
and R
2
1( )
and R
2
2( )
are (r � n – r) and (q � q – s) matrices respectively.
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 29
Result 2. Let A and B be (m � n) and (p � q) matrices with ranks r and s
respectively. Write A a a an
� ( , , ..., )
1 2
and B b b b bs q
� ( , , ..., , ..., )
1 2
, where
a Ri m
� and b Rj q
� then all the least square solutions of the Kronecker product
system of equations can be obtained by solving the consistent Kronecker prod-
uct system given by
( ) [ ][( )( ) (
( ) ( ) * * ( ) (x y R R Q Q R R� � � � � � �
� �
1
1
2
1
1 2 1
2
2
2
1 1
� �
)
)( )]v v
1 2
� .
P r o o f. Consider the system of equations ( )( ) ( )A B x y� � � �� � . Let P1
and P 2
be permutation matrices such that AP Q R1 1 1
� and BP Q R2 2 2
� . Then
( )( ) ( )( ) ( )
* *A B x y Q P R P x y Q Q
T T
� � � � � � �
1
1
2
2
1 2
and therefore,
( ) ( )x y P P
u u
v v
P u P u
P v P v
� � �
�
�
�
�
�
�
�
�
�
1 2 1 2
1 2
1 1 2 2
1 1 2 2
�
�
.
Hence ( ) ( )( )( ) ( )
( ) ( ) * * ( )u u R R Q Q R v v
1 2 1
1
2
1
1 2 1
2
1 2
� � � � � � �� � , where
v R n r
1
�
�
and v R q s
2
�
�
. Note that a basic least square solution is obtained by
taking ( ) ( )v v
1 2
0 0� � � .
5. Shortest vector problem. In this section, we shall be concerned with the
search problems for lattices viewed as infinite point’s sets. It is quite clear that
general special circumstances, the methods presented in [8] can be modified to
solve search problems for finite subsets of lattices. This will have many impor-
tant applications in Communications. Since the invention of public key Cryptog-
raphy in 1976, a new direction in Cryptography came into existence. This was
mainly due to Diffe and Hellman [9] and security of most Cryptosystem is based
on the hardness of factoring / computing discrete logarithm. In the year 1996
Ajtai [4] presented an efficiently computable function and it is hard to invent on
the average if the underlying lattice problem is intractable. Further, Ajtai and
Dwork [10] designed a public key Cryptosystem based on the ill conditioned
hardness of a lattice problem. However, in the year 1998 Ngayen and Stern [5]
showed that breaking the Ajtai C.Dwork Cryptosystem is unlikely NP-hard and
for realistic theories of the parameter one may even reach the private key from
public key. In this section, we use the method described by Ishay Haviv and
Oded Regv [8] to improve the best least square solution obtained in section 4 in
the process of finding shortest vector in R pq
. In literature there are two main
computational problems associated in the lattices are the SVP and the CVP. In
the first one, we are supposed to find a shortest non-zero vector in the lattices.
The problem CVP is an inhomogeneous variant of SVP, in which given a lattice
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
30 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
and some target point, one finds the close lattice point. The hardness of lattice
problem is probably due to the fact that there are many possible bases for the
same lattice.
Definition. A lattice is a discrete additive sub groups of R n
. Equivalently,
fix n &1. Let S R m
' be a finite non-empty set. The lattice generates by S is the
set of integer linear combinations of the elements in S, i.e.
( )L b b b Z i mn i i i( ... ) :
1
� � � ��� � for all 1
of m linearly independent vectors b1, b2, …, bn in Rn
(n � m). If rank n equals the
dimension m, then we say that the lattice is of full rank.
The set {b1, b2, …, bn } is called a basis of the lattice. Note that a lattice has
many possible bases. We often represent a basis by an (m � n) matrix having the
base vectors as columns, and we say that the basis B generates the lattice L. The
determinant of a lattice L is given by
det ( ) : detL A A AT
,
where A is any basis with L (A) = A.
In this section we use two trapdoors given [8] for the shortest vector prob-
lem based on the tensor product of two full dimensional lattices, L R n
1
' . For let
L L L� �
1 2
denote the tensor product and L R q
2
' the lattice point b: = (b1, b2, ...
…, bpq ) � L can be written as a two dimensional array consisting of elements
b b b
b b b
b b b
q
q q q
n q n q nq
1 2
1 2 2
1 1 1 2
�
�
�
�
� �
� � � �
�
�
�
�
�
�
�
�
�
�
, ,
�
�
�
�
�
L
L
L
2
2
2
� � �L L L
1 1 1
so, that the column vectors belong to the lattice L
1
and the row vector to L
2
. We
have the following very important proposition.
Proposition. Suppose L1, L2 are any two full dimensional lattices then the
following are true:
dim ( ) dim , dimL L L L
1 2 1 2
� � ,
dim ( ) (det ) (det )
dim dim
L L L L
L L
1 2 1 2
2 1
� � .
N o t e. Let B: = (b1, b2, …, bq ) be an ordered set containing q linearly inde-
pendent column vectors in Rn
then the set of all integral linear combinations of
the vectors
L L B t b t ZZ ZZbi i i
i
m
i
i
qn
� � � �
� �
� �( ) : ( / )
1 1
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 31
is called the lattice generated by the base B. Its dimension is dim L: = q and if
p=q, we call it a full dimensional lattice. The vectors L are called lattice A lattice
points L sub ' L with dim L sum = dim L, is called a sub lattice of L. Suppose L1
be a sub lattice of ZZ p
and the elements are called integer lattices.
The lattice generated by the matrix A and L2 be the lattice generated by the
matrix B. Then the tensor product of L1 and L2 is defined as the mp dimensional
lattice generated by mp � nq matrix( )A B� and is denoted by L L L� �
1 2
. Equiv-
alently, L is generated by the nq vectors obtained by taking the tensor product of
two column vectors one from A and one from B. Let L1 be the vectors obtained by
taking the tensor of the two column vector x and y. If we think of the vectors in L
as m � p matrices, then we can define L L L A B x ZT n q
� � � � �
�
1 2
{ : }with each
entry in x corresponding to one of the nq generating vectors. In this section we
are interested in the behavior of the shortest vector in a tensor product of lattices.
For any two lattices L1 and L2, we have
* * *
1 1 1 1 1 1 2
( ) ( ) ( )b b bL L L L� � , (7)
where1 � +� [4]. Indeed for any two vectors x and y satisfying ( )x y p� �
� x yp p . Applying this to shortest non-zero vectors of L1 and L2, we get (7) Note
that *
1
( )
( )
p l is the minimum Lp distance between two distinct points in the lattice
L for any p, 1� +p , The Lp norm of a vector x R q
� is defined as
x xp i
p
i
q p
�
�
�
�
�
�
1
1/
and its L
+
norm is denoted by x x Li i
p
+
max ( )
( )
* is the Lp norm of a shortest
non-zero vector:
*
i
p
pL r L B r i( )
( ) min{ :dim ( ( ( )) }� , &span .
Minkowski’s first theorem: For any lattice L of rank r
det ( )
( )
L
L
r
i
r
&
�
�
�
*
.
For a full rank lattice L R q
' , its dual lattice denoted by L*
is defined as
L x R x y z y Lq*
{ / , }� � -� �for all .
And if L L� *
we say that it is a self-dual lattice. It can easily be shortest if L is lat-
tice generated by the basis B, then ( )B T�1
generates the lattice L*
.
Theorem 8. For any large q, there exists a q dimensional self-dual lattice L
satisfying * i L L q( )
*
� � .
K. N. Murty, V.V.S.S.S Balaram, K. Viswanadh
32 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
P r o o f. Let L be a lattice generated by a basis B: = (b1, …, bq ). Let ( )B T�1
=
�{ , ,..., }b b bq1 2
be the basis generated by the dual lattice L*
. Now the vector
e b b L Li i
i
q
� � � �
�
�
1
*
.
This vector can be written as BB I BI Bq q
T T� �
� �
1 1
(( ) ) , or B B I q
�
� �
1
�
�
(( ) )B I BT T
q
1
. And clearly has L2 norm q. The proof is complete. The shortest
vector problem discussed above is of immense importance in practical applications.
Çàïðîïîíîâàíî êðèòåð³é ³ñíóâàííÿ òà ºäèíîñò³ ðîçâ’ÿçêó çàäà÷³ êðîíåêåðîâîãî äîáóòêó ç ïî-
÷àòêîâèìè óìîâàìè, ÿêà ïîâ’ÿçàíà ç óçàãàëüíåíîþ ð³çíèöåâîþ ñèñòåìîþ, ùî ìຠìàòðèöþ
ïåðøîãî ïîðÿäêó. Ðîçðîáëåíî ìîäèô³êîâàíèé ìåòîä íàéìåíøèõ êâàäðàò³â ³ ìîäèô³êîâàíèé
QR àëãîðèòì äëÿ ïîøóêó íàéêðàùîãî ðîçâ’ÿçêó êðîíåêåðîâîãî äîáóòêó ìàòðèöü ìåòîäîì
íàéìåíøèõ êâàäðàò³â. Âñòàíîâëåíî, ùî ïðè âèêîðèñòàíí³ öèõ ìåòîä³â äëÿ çàãàëüíîãî ðîç-
â’ÿçêó çàäà÷³ êðîíåêåðîâîãî äîáóòêó ç ïî÷àòêîâèìè óìîâàìè ¿¿ ìàòðèöÿ ïî÷àòêîâèõ óìîâ º
ïåðåîçíà÷åíîþ. Ç âèêîðèñòàííÿì ìåòîäó, ðîçðîáëåíîãî Ishey Haviv and Îded Regev, ïðè
âèçíà÷åíí³ çàäà÷³ íàéêîðîòøîãî âåêòîðà ïîêðàùåíî ðîçâ’ÿçîê ìåòîäîì íàéìåíøèõ êâàäðàò³â.
Çàñòîñîâàíî ñòàíäàðòíèé êðîíåêåð³â äîáóòîê àáî òåíçîðíèé äîáóòîê íà ñ³òêàõ äëÿ çá³ëüøåííÿ
êîåô³ö³ºíòà æîðñòêîñò³.
1. Fausett D. W., Fulton C. T. Large Least Square Problem Involving Knocker Products//
SIAM J. matrix Analysis and Applications. — 1994. — Vol 15, No 1. — P. 219—227.
2. Brower J. W. Kronecker Products and Matrix Calculus in System Theory// IEEE Trans. CVC
System. — 1978. — Vol 25. — P. 772—781.
3. Murty K.N., Shaw M. On Kronecker Product Self Adjoint Boundary Value Problems// Engi-
neering Simulation. — 2001. — Vol 18. — P. 475—488.
4. Ajtai M. Generating Hard Instance of Lattice Problems Quad// Mod. — 2004. — Vol 13. —
P. 1—32. (Dept of Maths. Seconda univ. Napoli, Casetra).
5. Nguyen P., Stevna J. Crypto Analysis of the Ajtai Dwork Cryptosystem, Advances in
Cryptology — Proc. Crypto ‘98’, Lecture Notes in Computer Science. Vol 1294. — Berlin —
Heidulburg: Springer — Verlag, 1998. — P. 223—242.
6. Knot S. Hardness of Approximating the Shortest Vector Problem in Lattices// J. of the
ACM.— 2005. — Vol 52, No 5. — P. 789—808
7. Atkinson K. An Introduction to Numerical Analysis. Second Edition. — JohnWilley and
Sons, 1987.
8. Ias Hay Haviv, Odded Regev. Tensor-based Hardness of the Shortest Vector Problem to
Within Almost Polynomial Factors. Preprint. — March, 12. — 2007.
9. Diffie W., Heleman M. New Directions in Cryptography// IEEE Transactions of Information
Theory. — 1976. — Vol 22, No 6. — P. 644—654.
10. Ajtai M., Dwork C. A Public Key Cryptosystem with the Worst Case / Average Case Equiv-
alence// Proc. of the 29th Annual ACA symposium theory of computing (STOC). — ACM
press. — 1997. — P. 293 — 193.
Ïîñòóïèëà 15.02.08
Solution of Kronecker Product Initial Value Problems Associated
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 33
|