The boolean satisfiability problem SAT is one of the fundamental and open
tasks in present-day information science. This problem is NP-complete. It means that
all N P problems can be reduced to SAT in polynomial time. Interestingly, among NP
problems, there are many closely related to cryptology, for example: factorization of
numbers – important for RSA, breaking keys of symmetric ciphers, finding collisions of
hash functions and many others. The discovery of the polynomial algorithm for SAT
would result in resolving one of Millennium Prize Problems: P vs. N P. This objective
seems to be hard to achieve – it’s unknown if it is even possible. With slightly lower
aspirations, we can design heuristic or random algorithms for SAT. Therefore, the main
goal of our study is to present a project of parallel SAT Solver based on WalkSAT algorithm, including its implementation using the OpenCL programming environment and a
computer equipped with NVIDIA Tesla graphics cards. With the rapid development of
GPU technology and FPGAs, as well as portability of solutions created in OpenCL, the
direction of such works becomes interesting because of computational efficiency gained,
as well as solution prototyping rate.
REFERENCES(30)
1.
T. Eibach, E. Pilz, and G. Volkel ¨ , Attacking Bivium Using SAT Solvers, University of Ulm, Institute of Theoretical Computer Science http://www.uni-ulm.de/fileadmi... uni ulm/iui.inst.190 /Mitarbeiter/eibach/Attacking-Bivium-Using-SAT-Solvers.pdf, 01.02.2014.
S. Anthony, 7nm, 5nm, 3nm: The new materials and transistors that will take us to the limits of Moores law, http://www.extremetech.com/com...- -new-materials-and-transistors-that-will-take-us-to-the-limits-of-moores-law, 24.04.2014.
C. F. Madigan, S. Malik, M. W. Moskewicz, L. Zhang, Y. Zhao, Chaff: Engineering an Efficient SAT Solver, 39th Design Automation Conference (DAC 2001), ACM, 2001.
H. H. Hoos, D. A. D. Tompkins, Novelty+ and Adaptive Novelty+, https://cs.uwaterloo.ca/ dtompkin/papers/satcomp04-novp.pdf, University of British Columbia, 2004.
G. V. Bard, Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis, Rozprawa doktorska, 2007.
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.