격자 축소

2차원 격자 감소: 검은색 벡터는 격자의 주어진 기준(파란색 점으로 표시됨)이고 빨간색 벡터는 축소 기준입니다.

수학에서 격자 기저 감소의 목적은 입력으로 정수 격자 기저가 주어졌을 때 짧고 거의 직교하는 벡터를 가진 기저를 찾는 것이다.이것은 실행 시간이 적어도 격자의 치수가 지수인 다른 알고리즘을 사용하여 실현됩니다.

거의 직교

거의 직교하는 척도의 하나가 직교 결점입니다.이것은 기본 벡터의 길이의 곱과 벡터가 정의하는 평행관의 부피를 비교합니다.완벽하게 직교하는 기저 벡터의 경우 이러한 양은 동일합니다.

n $(\displaystyle$ n $)$ 벡터의 $n$ $특정$ 베이스는 행렬 $B$ (\ $displaystyle$ B $B$ 로 나타낼 수 있습니다.행렬의 열은 $b_{i},i=1,\ldots ,n$ $b_{i},i=1,\ldots ,n$ $b_{i},i=1,\ldots ,n$ $b_{i},i=1,\ldots ,n$ , $b_{i},i=1,\ldots ,n$ (\ $displaystyle b_{i$ }, $i=1,\ldots,n$ 입니다.기본 벡터 수가 이 벡터가 차지하는 공간의 차원과 동일한 경우,ix는 정사각형이며, 기본 평행 입방체의 부피는 단순히 이 $\det(B)$ det ( $\det(B)$ 의 행렬식 절대값입니다. 벡터 수가 기본 공간의 치수보다 작을 경우 볼륨 ${\sqrt {\det(B^{T}B)}}$ det ( ${\sqrt {\det(B^{T}B)}}$ T B $)$ (\ $displaystyle \det (B^{T})$ A ${\sqrt {\det(B^{T}B)}}$ 에 대해 볼륨 det (B ${\sqrt {\det(B^{T}B)}}$ )가 ${\sqrt {\det(B^{T}B)}}$ . $λ$ { $displaystyle$ \ $\Lambda$ Lambda $\Lambda$ }, 이 볼륨은 어떠한 기준으로도 동일하기 때문에 $\det(\Lambda )$ 격자 디트 $($ δ $style \det(\$ Lambda $\det(\Lambda )$ $d(\Lambda )$ 또는 $d(\Lambda )$ 상수 d( $δ)$ 의 행렬식이라고 합니다.

직교성 결점은 기본 벡터 길이를 평행입방체 체적으로 나눈 값이다.

\displaystyle (B)={Pi _{i=1}^{n}\b_{i}}{\}{\displayrt {det(B^{T}B}}}=b_{i}\}{d(\Lambda)}

기하학적 정의에서 기초가 직교하는 경우에만 등식을 갖는 $\delta (B)\geq 1$ ( $\delta (B)\geq 1$ 1 { $displaystyle \delta (B)\geq$ 1 $}$ 을 $\delta (B)\geq 1$ 알 수 있다.

격자 감소 문제가 가능한 결점이 가장 작은 기준을 찾는 것으로 정의되면 문제는 NP-hard입니다^{[citation needed]}.단, 결점 $\delta (B)\leq c$ ( $\delta (B)\leq c$ ) $\delta (B)\leq c$ c $\delta (B)\leq c$ { $displaystyle \delta (B)\leq$ c $}$ 의 $\delta (B)\leq c$ 기저를 구하는 다항식 시간 알고리즘이 존재합니다.여기서 c는 기저 벡터의 수 및 기저 공간의 치수(^{[citation needed]}다른 경우)에만 일정합니다.이것은 많은 실용적인^{[citation needed]} 응용 분야에서 충분히 좋은 솔루션입니다.

2차원

단 두 개의 벡터로 구성된 기초에 대해, 두 정수의 최대공약수에 대한 유클리드 알고리즘과 매우 유사한 단순하고 효율적인 환원 방법이 있다.유클리드 알고리즘과 마찬가지로 방법은 반복적이다; 각 단계에서 두 벡터 중 큰 벡터는 작은 벡터의 정수 배수를 더하거나 빼서 감소한다.

Lagrange 알고리즘 또는 Lagrange-Gauss 알고리즘으로 알려진 알고리즘의 의사 코드는 다음과 같습니다.

 ${\textstyle (u,v)}$  ( ${\textstyle (u,v)}$  , ${\textstyle (u,v)}$ v ) { $textstyle$  $(u,$ v)} 격자 ${\textstyle (u,v)}$  ${\textstyle L}$ 입니다.그렇지 않으면 v  ${\textstyle ||v||\leq ||u||}$   $textstyle$ v \ $leq$  u  ${\textstyle ||v||\leq ||u||}$ 가 교환된다고 가정합니다. ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ :  ${\textstyle (u,v)}$ basis (  ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$   ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$  $v$  ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ ) ${\textstyle (u,v)}$ = = 1 ( L ) , v ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$   ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ 2 (  ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$  ) \  $textstyle = {1}$  ( $L$  ) , v ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ = \  $textstyle$ = { $2$ （ L ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ ） } 。

 ${\textstyle ||v||\leq ||u||}$  ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$  ${\textstyle ||v||\leq ||u||}$   ${\textstyle ||v||\leq ||u||}$   $textstyle$  ${\textstyle ||v||\leq ||u||}$ v \ $leq$  u  ${\textstyle ||v||\leq ||u||}$  : q :  $=$  ,  ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$   ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$   $、$  { \  $frac$ {  $v$ } { v ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ ^ {2 $}$  } \  $rceil$ } ${\textstyle r:=u-qv}$  ${\textstyle u:=v}$  :  ${\textstyle r:=u-qv}$  - ${\textstyle r:=u-qv}$  ${\textstyle u:=v}$  ${\textstyle r:=u-qv}$  $= u style$  :

자세한 내용은 의 Lagrange 알고리즘 섹션을 참조하십시오.

적용들

격자 감소 알고리즘 현대 수 이론적 적용의π{\displaystyle \pi}에 대한 꼭지 알고리즘의 발견에 포함한 많은 문화에서. 비록 짧은 기준을 결정하는 것이단 NP완전 문제는, 로렌스 리버모어 연구소 algorithm[2] 같은 알고리즘 대개 정치에서 짧은(반드시 shortest)기준을 발견할 수 있다.yno최악의 퍼포먼스를 보증하는 mial time.LLL은 공개 키 암호 시스템의 암호 분석에 널리 사용됩니다.

정수 관계를 찾는 데 사용되는 알고리즘의 일반적인 입력은 n × $n\times n$ $(\displaystyle$ n $\$ $times$ n) 요소(\displaystyle w $\displaystyle$ w $\$ $displaystyle$ $w$ w)로 구성된 마지막 열의 엔트리와 함께 $n\times n$ 된 $n\times n$ n × $n\times n$ n(\ $displaystyle$ n\times n) ID $n\times n$ $n$ 매트릭스로 구성됩니다.(0)을 참조할 수 있습니다.

거의 직교적인 기초를 계산하기 위한 LLL 알고리즘은 모든 고정 차원에서의 정수 프로그래밍이 다항식 ^[3]시간에 수행될 수 있음을 보여주기 위해 사용되었습니다.

알고리즘

다음 알고리즘은 격자 기반을 줄입니다. 이러한 알고리즘의 몇 가지 공개 구현도 나열되어 있습니다.

연도	알고리즘.	실행
1773	2D 격자의 Lagrange/Gauss 축소
1982	렌스트라-렌스트라-로바시 감소	NTL, fpll
1987	블록 코르키네-졸로타레프^[4]	NTL, fpll
1993	세이센^[5] 삭감	LLLplus

레퍼런스

^ Nguyen, Phong Q. (2009). "Hermite's Constant and Lattice Algorithms". The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19–69. doi:10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100.
^ Lenstra, A. K.; Lenstra, H. W. Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. hdl:1887/3810. MR 0682664. S2CID 5701340.
^ Lenstra, H.W. (1983). "Integer programming with a fixed number of variables". Math. Oper. Res. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10.1287/moor.8.4.538.
^ Hanrot, Guillaume; Stehlé, Damien (2008). "Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases". arXiv:0801.3331 [math.NT].
^ Seysen, Martin (September 1993). "Simultaneous reduction of a lattice basis and its reciprocal basis". Combinatorica. 13 (3): 363–376. doi:10.1007/BF01202355. S2CID 206791637.

[Nguyen_2009_pp._19–69-1] Nguyen, Phong Q. (2009). "Hermite's Constant and Lattice Algorithms". The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19–69. doi:10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100.

[2] Lenstra, A. K.; Lenstra, H. W. Jr.; Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. hdl:1887/3810. MR 0682664. S2CID 5701340.

[3] Lenstra, H.W. (1983). "Integer programming with a fixed number of variables". Math. Oper. Res. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10.1287/moor.8.4.538.

[4] Hanrot, Guillaume; Stehlé, Damien (2008). "Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases". arXiv:0801.3331 [math.NT].

[5] Seysen, Martin (September 1993). "Simultaneous reduction of a lattice basis and its reciprocal basis". Combinatorica. 13 (3): 363–376. doi:10.1007/BF01202355. S2CID 206791637.

[3]

[4]

[5]

Search

격자 축소

네임스페이스

더

목차

거의 직교

2차원

적용들

알고리즘

레퍼런스