Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166565OAI: oai:DiVA.org:kth-166565DiVA: diva2:811317
Supervisors
Examiners
Available from: 2015-05-12 Created: 2015-05-11 Last updated: 2015-05-12Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 125 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

urn-nbn

Altmetric score

urn-nbn
Total: 278 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf