Change search
ReferencesLink to record
Permanent link

Direct link
FACT- and SAT-solvers on different types of semiprimes
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]

This thesis is aimed to cover how boolean satisfiability solvers can be used on integer factorization problems and to compare them with already established integer factorization solvers. The integer factorization problem is believed to be hard and is used in modern day cryptoalgorithms such as RSA. This thesis is also aimed to explore how well different solvers can solve different types of semiprimes and if there is any notable difference between them. This report covers three different boolean satisfiability solvers as well as three of the integer factorization solvers. The results from the thesis show that boolean satisfiability solvers cannot be used as a replacement of already established integer factorization solvers. The thesis also shows that the type of semiprime does affect how fast the solvers are able to factorize the semiprime. The boolean satisfiability solvers had favorable results toward asymmetrical semiprimes and disfavorable results toward prime powers.

Abstract [sv]

Denna avhandlings mål är att undersöka hur lösare för booleska satisfierbarhetsproblemet kan användas för att lösa primtalsfaktoriseringsproblem och jämföra dem med redan etablerade lösare för primtalsfaktorisering. Primtalsfaktorisering tros vara svårt och används i flera moderna krypteringsalgoritmer som RSA. Denna avhandling undersöker även hur väl olika lösare kan lösa olika typer av semiprimtal och om det finns någon noterbar skillnad mellan dem. Rapporten täcker tre olika lösare för booleska satisfierbarhetsproblem och tre olika primtalsfaktoriseringslösare. Resultaten från denna avhandling visar att lösare för booleska satisfierbarhetsproblem inte kan används som ersättning för redan etablerade primtalsfaktoriseringslösare. Avhandlingen visar även att typen av semiprimtal påverkar hur snabbt lösarna faktoriserar semiprimtalet. Lösarna för boolesk satisfierbarhet visade fördelaktiga resultat mot asymmetriska semiprimtal och ofördelaktiga resultat mot primtalspotenser.

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

Open Access in DiVA

fulltext(857 kB)68 downloads
File information
File name FULLTEXT01.pdfFile size 857 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: 68 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: 141 hits
ReferencesLink to record
Permanent link

Direct link