memory requirements, which limits their practical applicability. When the memory resources are constrained, a brute-force search is the only known way of solving the LPN problem. In this paper, we propose a new parallel implementation, called Parallel-LPN, of an enhanced algorithm to solve the LPN problem. We implemented the Parallel-LPN in C and MPI (Message Passing Interface), and it was tested on a cluster system, where we obtained a quasi-linear speedup of approximately 90%. We also proposed a new algorithm by using combinatorial objects that enhances the ParallelLPN performance and its serial version.