检索结果-内蒙古大学图书馆

Performance Evaluation of Lower Complexity Hybrid-Fix-and-Round-lll algorithm for MIMO System

KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS 2018年第6期12卷 2554-2580页

作者： Lv, Huazhang Network Technol Res Inst China Unicorn Innovat Ctr 5G Beijing Peoples R China

Lenstra-Lenstra-Lovasz (lll) is an effective receiving algorithm for Multiple-Input-Multiple-Output (MIMO) systems, which is believed can achieve full diversity in MIMO detection of fading channels. However, the lll algorithm features polynomial complexity and shows poor performance in terms of convergence. The reduction of algorithmic complexity and the acceleration of convergence are key problems in optimizing the lll algorithm. In this paper, a variant of the lll algorithm, the Hybrid-Fix-and-Round lll algorithm, which combines both fix and round measurements in the size reduction procedure, is proposed. By utilizing fix operation, the algorithmic procedure is altered and the size reduction procedure is skipped by the hybrid algorithm with significantly higher probability. As a consequence, the simulation results reveal that the Hybrid-Fix-and-Round-lll algorithm carries a faster rate of convergence compared to the original lll algorithm, and its algorithmic complexity is at most one order lower than original lll algorithm in real field. Comparing to other families of lll algorithm, Hybrid-Fix-and-Round-lll algorithm can make a better compromise in performance and algorithmic complexity.

关键词： lll algorithm lattice reduction algorithmic complexity size reduction MIMO system

来源：评论

学校读者我要写书评

暂无评论

Algebraic number fields and the lll algorithm

引用

JOURNAL OF SYMBOLIC COMPUTATION 2024年 121卷

作者： Uray, M. J. Eotvos Lorand Univ Fac Informat Dept Comp Algebra Pazmany Peter Setany 1-C H-1117 Budapest Hungary

In this paper we analyze the computational costs of various operations and algorithms in algebraic number fields using exact arithmetic. Let K be an algebraic number field. In the first half of the paper, we calculate the running time and the size of the output of many operations in K in terms of the size of the input and the parameters of K. We include some earlier results about these, but we go further than them, e.g. we also analyze some R-specific operations in K like less-than comparison. In the second half of the paper, we analyze two algorithms: the Bareiss algorithm, which is an integer-preserving version of the Gaussian elimination, and the lll algorithm, which is for lattice basis reduction. In both cases, we extend the algorithm from Zn to Kn, and give a polynomial upper bound on the running time when the computations in K are performed exactly (as opposed to floating-point approximations). (c) 2023 Elsevier Ltd. All rights reserved.

关键词： Algebraic number field lll algorithm Bareiss algorithm Exact computation Running time analysis

来源：评论

学校读者我要写书评

暂无评论

Deep lll on Module Lattices 27th

Deep LLL on Module Lattices

引用

27th International Conference on Information Security

作者： Zhou, Yang Cao, Heyang Wang, Mingsheng Univ Chinese Acad Sci Sch Cyber Secur Beijing Peoples R China Chinese Acad Sci Key Lab Cyberspace Secur Def Inst Informat Engn Beijing Peoples R China

ISBN: (纸本)9783031757631;9783031757648

The lll algorithm, renowned for its application to Euclidean lattices, plays a crucial role in lattice cryptanalysis by offering a standard method for refining lattice bases. With the increasing importance of module lattices-defined as modules over the ring of integers of a number field-in lattice cryptography, there is a compelling need to adapt the lll algorithm for module lattices. This paper presents a generalization of the Deep lll algorithm-a variant of lll proposed by Schnorr and Euchner [25], which relaxes the restriction on the insertion position-to module lattices. Deep lll has been widely used in BKZ reduction as a sub-procedure. Our algorithm is suitable as a sub-procedure in adapted BKZ reduction for module lattices. We implemented a proof-of-concept version of our algorithm, and compared to the lll algorithm on module lattices, our algorithm outperformed it in all of our experimental cases. Additionally, we introduced a simplification that avoids invoking the computation of the Module Hermite Form and corrected mistakes in the previous work.

关键词： lll algorithm Module lattices Lattice Reduction

来源：评论

学校读者我要写书评

暂无评论

An optimal bound for factoring unbalanced RSA moduli by solving Generalized Implicit Factorization Problem

引用

JOURNAL OF SUPERCOMPUTING 2025年第1期81卷 1-24页

作者： Zhang, Ran Bi, Jingguo Li, Lixiang Peng, Haipeng Beijing Univ Posts & Telecommun Sch Cyberspace Secur Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Informat Secur Ctr State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

The integer factorization problem, concerning the product of two primes N = pq, has been a focal point for researchers since its rise to prominence with the RSA algorithm, a renowned public key scheme. It is well known that the integer factorization problem can be solved by the Number Field Sieve (NFS) algorithm in sub-exponential time, this challenge may also find resolution in polynomial time under certain conditions for the primes. In this paper, we revisit the problem of factoring RSA moduli with the implicit hint, where the implicit hint is the shared bits of primes. As for k RSA moduli, we present a novel implicit factorization approach applicable when the unknown multiples ap of the prime factors p share a certain number of most significant bits (MSBs) or least significant bits (LSBs). By drawing inspiration from addressing the Approximate Common Divisor Problem (ACDP), we transform this problem into solving the small roots of k-1 trivariate polynomials. To compute these small roots, we employ Coppersmith's method to construct a lattice basis for the modular polynomials. We modify the lattice basis by introducing new variables, achieving an optimal bound in the MSB and LSB cases. Our attack breaks the RSA system and improves upon all previous attacks on such variants when the amount of the shared bits is sufficiently large. Concluding our paper, we meticulously validate the theoretical analysis results, with experimental data confirming the full practical feasibility of our attack on such an RSA variant system.

关键词： RSA system Generalized Implicit Factorization Problem Coppersmith's method lll algorithm

来源：评论

学校读者我要写书评

暂无评论

On the largest value of the solutions of Erdős' last equation

引用

INTERNATIONAL JOURNAL OF NUMBER THEORY 2025年第0期

作者： Luca, Florian Pink, Istvan Sandor, Csaba Stellenbosch Univ Math Div Stellenbosch South Africa Univ Debrecen Inst Math POB 400 H-4002 Debrecen Hungary Univ Salzburg Hellbrunnerstr 34 A-I5020 Salzburg Austria Budapest Univ Technol & Econ Inst Math Dept Stochast Muegyetem Rkp 3 H-1111 Budapest Hungary HUN REN Alfred Renyi Inst Math Realtanoda Utca 13-15 H-1053 Budapest Hungary MTA HUN REN RI Lendulet Momentum Arithmet Combinat Realtanoda Utca 13-15 H-1053 Budapest Hungary

Let n be a positive integer. The Diophantine equation n(x(1) + x(2) + & ctdot;+ x(n)) = x(1)x(2 )& mldr;x(n), 1 infinity as n ->infinity and determine all tuples (n, x(1), & mldr;, x(n)) with x(n) <=... 详细信息

Let n be a positive integer. The Diophantine equation n(x(1) + x(2) + & ctdot;+ x(n)) = x(1)x(2 )& mldr;x(n), 1 <= x(1) <= x(2) <= & ctdot;<= x(n) is called Erd & odblac;s' last equation. We prove that x(n) ->infinity as n ->infinity and determine all tuples (n, x(1), & mldr;, x(n)) with x(n) <= 10.

关键词： Erd & odblac s's last equation Baker's method lll algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Diophantine equation Fn^x + Fk^x = Fm^y

引用

RAMANUJAN JOURNAL 2025年第2期67卷 1-37页

作者： Berczes, Attila Hajdu, Lajos Luca, Florian Pink, Istvan Univ Debrecen Inst Math POB 400 H-4002 Debrecen Hungary HUN REN Equat Funct Curves & their Applicat Res Gr Debrecen Hungary Stellenbosch Univ Math Div Stellenbosch South Africa Univ Salzburg Hellbrunner str 34-I A-5020 Salzburg Austria

In this paper, we find all solutions of the Diophantine equation F-n(x) + F-k(x) = F-m(y), where {F-m}(m >= 0 )is the Fibonacci sequence.

关键词： Fibonacci numbers Exponential Diophantine equations Baker's method lll algorithm

来源：评论

学校读者我要写书评

暂无评论

Storage efficient algorithm for Hermite Normal Form using lll

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2021年 613卷 183-200页

作者： Cho, Gook Hwa Lee, Hyang-Sook Lim, Seongan Kim, Yoonjeong Ewha Womans Univ Inst Math Sci Seoul South Korea Ewha Womans Univ Dept Math Seoul South Korea DuDu Informat Tech Inc Seoul South Korea

Computing HNF has a long history, but designing a storage efficient algorithm is a challenging issue for matrices of large sizes. One of the main challenges in the design of storage efficient HNF algorithm is to control the rank and the size of the intermediate input. In our proposed algorithm, we use a multiple extended gcd algorithm and show that the rank of the intermediate input matrix decreases as the number of iteration increases. The determinant of the intermediate input matrix of our algorithm is a factor of the determinant d of the input matrix and thus size reduction modulo d can be done in the computations of our algorithm. By using a lattice reduction algorithm and a proven quality of lll reduced basis, we prove that the storage of the intermediate input matrix B-k of our algorithm is less than (n - k + 1)(n - k + 1)(n-k)/4 + log(2) d) in bits. Therefore, it is expected that a smaller storage for kth iteration is required as k closes to n. We compare the intermediate computations of our algorithm to MW-type algorithm which has an optimal asymptotic space requirement. Our experimental example and results on intermediate size suggest that the intermediate storage of our HNF algorithm is comparable to MW-type algorithm and well controlled by the intermediate input size. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Lattice Hermite Normal Form lll algorithm

来源：评论

学校读者我要写书评

暂无评论

A Novel Hybrid Fix-lll Lattice Reduction algorithm for MIMO Detection System

引用

IEEJ TRANSACTIONS ON ELECTRICAL AND ELECTRONIC ENGINEERING 2017年第3期12卷 372-378页

作者： Lv, Huazhang Li, Jianping Commun Univ China Sch Informat Engn 1 Dongjie Dingfuzhuang Chaoyang Dist Beijing Peoples R China

Lenstra-Lenstra-Lovasz (lll) is an effective lattice reduction algorithm for multiple-input multiple-output (MIMO) systems, which was considered to achieve full diversity in the MIMO fading channel. In the lll algorithm, size reduction is performed for pairs of consecutive basis vectors, and the concern of numerical stability is raised. However, the whole complexity of the lll algorithm is of polynomial order, and its characteristics of the convergence perform poor in MIMO system. In this paper, a variant version, named the novel hybrid algorithm, which combines both fix measurement and round measurement, is proposed. By modifying the iteration criterion and choosing proper values of the parameters, the algorithm has a large probability to skip the size reduction and cause a faster convergence, It means in one algorithm iteration the lll potential can be reduced as much as possible. Also, the performance bound derived by the proximity factor shows that the hybrid lll has a minor performance loss compared to the lll algorithm. As a direct consequence, in simulation results, the hybrid lll algorithm can make a better compromise between the rate of convergence, complexity of the algorithm, and algorithmic performance. (c) 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.

关键词： lll algorithm lll potential lattice reduction algorithm complexity MIMO system

来源：评论

学校读者我要写书评

暂无评论

Explicit Relation between Low-Dimensional lll-Reduced Bases and Shortest Vectors

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2019年第9期E102A卷 1091-1100页

作者： Matsuda, Kotaro Takayasu, Atsushi Takagi, Tsuyoshi Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138654 Japan Natl Inst Adv Ind Sci & Technol Tokyo 1350064 Japan

The Shortest Vector Problem (SVP) is one of the most important lattice problems in computer science and cryptography. The lll lattice basis reduction algorithm runs in polynomial time and can compute an lll-reduced basis that provably contains an approximate solution to the SVP. On the other hand, the lll algorithm in practice tends to solve low-dimensional exact SVPs with high probability, i.e., >99.9%. Filling this theoretical-practical gap would lead to an understanding of the computational hardness of the SVP. In this paper, we try to fill the gap in 3, 4 and 5 dimensions and obtain two results. First, we prove that given a 3, 4 or 5-dimensional lll-reduced basis, the shortest vector is one of the basis vectors or it is a limited integer linear combination of the basis vectors. In particular, we construct explicit representations of the shortest vector by using the lll-reduced basis. Our analysis yields a necessary and sufficient condition for checking whether the output of the lll algorithm contains the shortest vector or not. Second, we estimate the failure probability that a 3-dimensional random lll-reduced basis does not contain the shortest vector. The upper bound seems rather tight by comparison with a Monte Carlo simulation.

关键词： lattice shortest vector problem lll algorithm lattice-based cryptography

来源：评论

学校读者我要写书评

暂无评论

Potlll: a polynomial time version of lll with deep insertions

引用

DESIGNS CODES AND CRYPTOGRAPHY 2014年第2期73卷 355-368页

作者： Fontein, Felix Schneider, Michael Wagner, Urs Univ Zurich Zurich Switzerland Tech Univ Darmstadt Darmstadt Germany

Lattice reduction algorithms have numerous applications in number theory, algebra, as well as in cryptanalysis. The most famous algorithm for lattice reduction is the lll algorithm. In polynomial time it computes a reduced basis with provable output quality. One early improvement of the lll algorithm was lll with deep insertions (Deeplll). The output of this version of lll has higher quality in practice but the running time seems to explode. Weaker variants of Deeplll, where the insertions are restricted to blocks, behave nicely in practice concerning the running time. However no proof of polynomial running time is known. In this paper Potlll, a new variant of Deeplll with provably polynomial running time, is presented. We compare the practical behavior of the new algorithm to classical lll, BKZ as well as blockwise variants of Deeplll regarding both the output quality and running time.

关键词： Lattice reduction lll algorithm Deep insertion

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：