Introduction
My name is Arjun Verma. I am a first year computer science undergraduate student at IIIT-Delhi. This year I've applied to Google Summer of Code with the mentoring organisation lmonade . I've decided to go with the project "Implementation of LLL Algorithm in FLINT" and also certain implementations including the LLL with removals and ULLL, a version of LLL with better hopefully with a decent performance. This would be a tough research problem. The mentors for this project are William Hart and Frederik Johansson.
Description of LLL algorithm and it's uses
Linear Algebra has been used in developing open source mathematical softwares. There is so much use of linear algebra here. It involves Gram-Schmidt orthogonalization process and LLL-reduced basis. The LLL algorithm guarantees with high probability that it finds a short vector in polynomial time. However the vector is not always the shortest vector in the lattice, but it frequently comes close and often finds the shortest solution or a good enough solution. It is a polynomial time best effort algorithm for solving an NP-complete problem. LLL is very very useful for breaking knapsack cryptographic systems.
Reason I liked this project
It involves linear algebra. It has applications in diverse fields, as I've mentioned above.
About the Project
The project is mainly focused on the following points
1. delta-epsilon LLL
2. heuristic LLL
3. LLL with removal
4. ULLL.
In my proposal, it also includes an Objective and Deliverables section where I describe how I plan to approach this task. To prepare separate modules d_mat and mpf_mat (possibly d_vec and mpf_vec as well), and an fmpq_mat implementation of the naive algorithm will be made separately (in the fmpq_mat module). As the LLL implementation in FLINT 1.6 and current FLINT series are not compatible with it,hence the project aims to build a structured module. My proposal has a detailed timeline where I provide a schedule with dates and important milestones.
My name is Arjun Verma. I am a first year computer science undergraduate student at IIIT-Delhi. This year I've applied to Google Summer of Code with the mentoring organisation lmonade . I've decided to go with the project "Implementation of LLL Algorithm in FLINT" and also certain implementations including the LLL with removals and ULLL, a version of LLL with better hopefully with a decent performance. This would be a tough research problem. The mentors for this project are William Hart and Frederik Johansson.
Description of LLL algorithm and it's uses
Linear Algebra has been used in developing open source mathematical softwares. There is so much use of linear algebra here. It involves Gram-Schmidt orthogonalization process and LLL-reduced basis. The LLL algorithm guarantees with high probability that it finds a short vector in polynomial time. However the vector is not always the shortest vector in the lattice, but it frequently comes close and often finds the shortest solution or a good enough solution. It is a polynomial time best effort algorithm for solving an NP-complete problem. LLL is very very useful for breaking knapsack cryptographic systems.
Reason I liked this project
It involves linear algebra. It has applications in diverse fields, as I've mentioned above.
About the Project
The project is mainly focused on the following points
1. delta-epsilon LLL
2. heuristic LLL
3. LLL with removal
4. ULLL.
In my proposal, it also includes an Objective and Deliverables section where I describe how I plan to approach this task. To prepare separate modules d_mat and mpf_mat (possibly d_vec and mpf_vec as well), and an fmpq_mat implementation of the naive algorithm will be made separately (in the fmpq_mat module). As the LLL implementation in FLINT 1.6 and current FLINT series are not compatible with it,hence the project aims to build a structured module. My proposal has a detailed timeline where I provide a schedule with dates and important milestones.
"and also" should not be bold
ReplyDelete"and many times finds" should be replaced by "and often finds" (could be "quite often" "in many cases" "frequently" instead of "often")
"About The Project": "The" should be small, paragraph below needs formatting
And what is ULLL?
Thankyou for pointing out the mistakes. This is the first time I wrote a blog.
DeleteULLL- It is a version of LLL with better complexity in terms of the size of the entries.
Actually, the shortest vector problem is unlikely to be NP-complete; since it is in coNP the only way that could happen is if NP=coNP.
ReplyDelete