Change search
ReferencesLink to record
Permanent link

Direct link
Factoring integers with parallel SAT solvers
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2015 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Factoring integers is a well known problem that at present cannot be solved in polynomial time. Therefore, other approaches for solving factorization problems are of interest. One such approach is to reduce factorization to SAT and solve it with a dedicated SAT solver. In this study, parallel SAT solvers are examined in this context and evaluated in terms of speedup, efficiency and effectiveness versus sequential SAT solvers. The methodology used was an experimental approach where different parallel and sequential solvers were benchmarked on different reductions from integer factorization to SAT. The benchmarks concluded that parallel SAT solvers are not better suited for solving factorization problems than sequential solvers. The performance boosts achieved by the fastest parallel solver barely corresponded to the extra amount of available parallel resources over the fastest sequential solver.

Abstract [sv]

Att faktorisera heltal är ett välkänt problem som för närvarande inte kan lösas i polynomisk tid. Därför är andra tillvägagångssätt för att lösa faktorisering av intresse. Ett sådant tillvägagångssätt är att reducera faktorisering till SAT och sedan lösa problemet med en dedikerad SAT-lösare. I denna studie undersöks parallella SAT-lösare i detta sammanhang och utvärderas i förhållande till uppsnabbning, effektivitet och ändamålsenlighet jämfört med sekventiella SAT-lösare. Den metod som användes var en experimentell sådan där olika parallella och sekventiella lösare jämfördes på olika reduktioner från heltalsfaktorisering till SAT. Genom testerna erhölls slutsatsen att parallella SAT-lösare inte är bättre lämpade för att lösa heltalsfaktorisering än sekventiella lösare. Prestandavinsterna som uppnåddes av den snabbaste parallella lösaren motsvarade knappt den extra mängd parallella resurser som denna hade över den snabbaste sekventiella lösaren.

Place, publisher, year, edition, pages
National Category
Computer Science
URN: urn:nbn:se:kth:diva-166436OAI: diva2:811047
Available from: 2015-05-12 Created: 2015-05-10 Last updated: 2015-05-12Bibliographically approved

Open Access in DiVA

fulltext(731 kB)231 downloads
File information
File name FULLTEXT01.pdfFile size 731 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 231 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 338 hits
ReferencesLink to record
Permanent link

Direct link