English

• 1. [1]

     FRUMKIN M A. Complexity questions in number theory[J]. Journal of Soviet Mathematics, 1985, 29(4): 1502–1517. doi: 10.1007/bf02104748

  2. [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. [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. [4]

     HARTLEY B and HAWKES T O. Rings, Modules and Linear Algebra[M]. London: Chapman and Hall, 1970: 73.

  5. [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. [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. [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. [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. [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. [10]

      DING Jintai and LINDNER R. Identifying ideal lattices[EB/OL]. http://eprint.iacr.org/2007/322, 2007.

  11. [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. [12]

      VON ZUR GATHEN J and GARHARD J. Modern Computer Algebra[M]. 3rd ed. Cambridge: Cambridge University Press, 2013: 313–332.

  13. [13]

      刘仁章. 格算法及其密码学应用[D]. [博士论文], 中国科学院大学数学与系统科学研究院, 2016.
      

• 1. [1]

     王立辉, 闫守礼, 李清. 一种轻量级数据加密标准循环掩码实现方案. 电子与信息学报, 2020, 41(0): 1-8.

  2. [2]

     王延峰, 张桢桢, 王盼如, 孙军伟. 基于DNA链置换的两位格雷码减法器分子电路设计. 电子与信息学报, 2020, 42(0): 1-9.

  3. [3]

     刘文斌, 吴倩, 杜玉改, 方刚, 石晓龙, 许鹏. 基于个性化网络标志物的药物推荐方法研究. 电子与信息学报, 2020, 42(6): 1340-1347.

  4. [4]

     杨书新, 梁文, 朱凯丽. 基于三级邻居的复杂网络节点影响力度量方法. 电子与信息学报, 2020, 42(5): 1140-1148.

  5. [5]

     王年, 胡旭阳, 朱凡, 唐俊. 基于视图感知的单视图三维重建算法. 电子与信息学报, 2020, 42(0): 1-8.

  6. [6]

     刘新, 阎焜, 杨光耀, 叶盛波, 张群英, 方广有. UWB-MIMO穿墙雷达三维成像与运动补偿算法研究. 电子与信息学报, 2020, 41(0): 1-8.

  7. [7]

     段永强, 王振占, 张升伟. 风云三号(D)气象卫星微波湿温度计系统建模和仿真. 电子与信息学报, 2020, 42(6): 1549-1556.

  8. [8]

     孙军伟, 李智, 王延峰. 基于DNA链置换的三级联组合分子逻辑电路设计. 电子与信息学报, 2020, 42(6): 1401-1409.

• 表 1  本原格向量序列

  输入：$ {\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)$

  下载: 导出CSV

  表 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),\right.$ 　　　　　　$\left.{\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}}$

  下载: 导出CSV
•