.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
随机整数格是格基密码学和算法数论的基础。2016年引入了一种新的随机整数格模型，不受任何Hermite标准形（HNF）的限制。同时观察到，此类格处于简单HNF形式的概率约为44%。本文通过引入(n,k)-简单随机整数格的概念，弥合了一般随机整数格与处于简单HNF形式的格之间的差距，其中HNF的前k个对角线元素被固定为1。我们推导了此类格的渐近计数公式，并计算了它们在所有整数格中的密度。此外，基于拒绝采样和逆采样方法提出了(n,k)-简单随机整数格的生成算法，分析表明其期望运行时间为O(n²)。这项工作为构建具有可控HNF形式的带结构随机格提供了理论基础和实践工具。
Keyword:
(n,k)-simple
HNF
random integer lattice
rejection sampling method
