A Novel Approximation Algorithm for the Shortest Vector Problem

Document Type

Article

Publication Title

IEEE Access

Abstract

Finding the shortest vector in a lattice is a NP-hard problem. The best known approximation algorithm for this problem is LLL algorithm with the approximation factor of α {frac {n-1}{2}}$ , α \geq \frac {4}{3}$ , which is not a good approximation factor. This work proposes a new polynomial time approximation algorithm for the shortest lattice vector problem. The proposed method makes use of only integer arithmetic and does not require Gram-Schmidt orthogonal basis for generating reduced basis. The proposed method is able to obtain an approximation factor of {1}{(1-δ)} , where 0 leq δ lt 1.

First Page

141026

Last Page

141031

DOI

10.1109/ACCESS.2024.3469368

Publication Date

1-1-2024

This document is currently not available here.

Share

COinS