输入:$ {\mathbb{Z}}\left[ {{x}} \right]$中$ f\left( x \right)$和$ g\left( x \right)$,次数分别为$ n$和$ m$,且$ n>m$; |
(1) 利用扩展欧几里得算法计算$ {\mathbb{Q}}[x]$上$ {r_i}^{'}\left( x \right)$, $ {s_i}^{'}\left( x \right)$, $ {t_i}^{'}\left( x \right)$,使得$ {r_i}^{'}\left( x \right) = {r_{i - 2}}^{'}\left( x \right) + {q_i}^{'}\left( x \right){r_{i - 1}}^{'}\left( x \right)$ 和${r_i}^{'}\left( x \right) = {s_i}^{'}\left( x \right)f\left( x \right) + $$ {t_i}^{'}\left( x \right)g\left( x \right)$成立,这里 $ i = 1,2, ··· ,l$; |
(2) 计算每一个$ {t_i}^{'}\left( x \right)$系数分母的最小公倍数$ {C_i}$, $ i = 1,2, ··· ,l$; |
(3) 令$ {r_i}\left( x \right) = {r_i}^{'}\left( x \right) \cdot {C_i}$为余式序列中第$ i$个余式, $ i = 1,2, ··· ,l$; |
出:$ {r_1}\left( x \right)$, $ {r_2}\left( x \right)$, ···, $ {r_l}\left( x \right)$ |

Citation: Yang ZHANG, Renzhang LIU, Dongdai LIN. Fast Triangularization of Ideal latttice Basis[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT190725

理想格上格基的快速三角化算法研究
-
关键词:
- 理想格
- / Hermite标准型
- / Smith标准型
- / 三角化
English
Fast Triangularization of Ideal latttice Basis
-
Key words:
- Ideal lattice
- / Hermite Normal Form (HNF)
- / Smith Normal Form (SNF)
- / Triangularization
-
-
[1]
FRUMKIN M A. Complexity questions in number theory[J]. Journal of Soviet Mathematics, 1985, 29(4): 1502–1517. doi: 10.1007/bf02104748
-
[2]
HUNG M S and ROM W O. An application of the Hermite normal form in integer programming[J]. Linear Algebra and its Applications, 1990, 140: 163–179. doi: 10.1016/0024-3795(90)90228-5
-
[3]
HAFNER J L and MCCURLEY K S. A rigorous subexponential algorithm for computation of class groups[J]. Journal of the American Mathematical Society, 1989, 2(4): 837–850. doi: 10.1090/S0894-0347-1989-1002631-0
-
[4]
HARTLEY B and HAWKES T O. Rings, Modules and Linear Algebra[M]. London: Chapman and Hall, 1970: 73.
-
[5]
MICCIANCIO D. Improving lattice based cryptosystems using the Hermite normal form[C]. International Conference on Cryptography and Lattices, Providence, 2001: 126–145. doi: 10.1007/3-540-44670-2_1.
-
[6]
LYUBASHEVSKY V and PREST T. Quadratic time, linear space algorithms for Gram-Schmidt orthogonalization and Gaussian sampling in structured lattices[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, 2015: 789–815. doi: 10.1007/978-3-662-46800-5_30.
-
[7]
HAFNER J L and MCCURLEY K S. Asymptotically fast triangulation of matrices over rings[C]. The 1st Annual ACM-SIAM Symposium on Discrete Algorithm, San Francisco, 1990: 197–200.
-
[8]
LE GALL F. Powers of tensors and fast matrix multiplication[C]. The 39th International Symposium on Symbolic and Algebraic Computation, Kobe, 2014: 296–303. doi: 10.1145/2608628.2608664.
-
[9]
STORJOHANN A and LABAHN G. Asymptotically fast computation of Hermite normal forms of integer matrices[C]. 1996 International Symposium on Symbolic and Algebraic Computation, Zurich, 1996: 259–266.
-
[10]
DING Jintai and LINDNER R. Identifying ideal lattices[EB/OL]. http://eprint.iacr.org/2007/322, 2007.
-
[11]
ZHANG Yang, LIU Renzhang, and LIN Dongdai. Improved key generation algorithm for Gentry’s fully homomorphic encryption scheme[C]. The 20th International Conference on Information Security and Cryptology, Seoul, 2018: 93–111. doi: 10.1007/978-3-319-78556-1_6.
-
[12]
VON ZUR GATHEN J and GARHARD J. Modern Computer Algebra[M]. 3rd ed. Cambridge: Cambridge University Press, 2013: 313–332.
-
[13]
刘仁章. 格算法及其密码学应用[D]. [博士论文], 中国科学院大学数学与系统科学研究院, 2016.
-
[1]
-
表 1 本原格向量序列
表 2 理想格上格基的三角化
输入:本原格向量序列,$ {r_0}\left( x \right)$, $ {r_1}\left( x \right)$, ···, $ {r_l}\left( x \right)$(向量形式为$ {{{r}}_{\bf 0}}$,
$ {{{r}}_{\bf 1}}$, ···, $ {{{r}}_{ l}}$)(1) 令$ {{T}} \leftarrow {0^{n \times n}}$ (2) 如果$ k \in {I_l},{{ T}_k}\left( x \right) = {r_l}\left( x \right){x^{n - k}},i \leftarrow l - 1$ (3) 如果$ k \in {I_i}$, a) 计算$ \phi $和ψ使得
$ \phi {\rm{lc}}\left( {{r_i}} \right) + \psi {\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right) = {\rm{gcd}}\left( {{\rm{lc}}\left( {{{{T}}_{n - {n_{i + 1}}}}} \right),{\rm{lc}}\left( {{r_i}} \right)} \right)$b) 令$ {{{T}}_{n - {n_i}}}\left( {{x}} \right) = \phi {r_i}\left( x \right) + \psi {{{T}}_{n - {n_{i + 1}}}}\left( x \right){x^{{\delta _i}}}$ c) 如果$ {\rm{lc}}\left( {{{{T}}_{n - {n_i}}}} \right) = 1$,则令$ {{{T}}_j}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - j}}$, $ j = 1,2, ··· ,n - {n_i}$,并结束循环 d) 否则$ {{{T}}_k}\left( x \right) = {{{T}}_{n - {n_i}}}\left( x \right){x^{n - {n_i} - k}}$, $ i \leftarrow i - 1$ e) 如果$ i>0$,到(3)开始循环,否则结束循环 输出:$ {{T}}$ -

计量
- PDF下载量: 6
- 文章访问数: 338
- HTML全文浏览量: 77