Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Factorization patterns in 3-SAT: Analysis of clause ordering for reductions of the integer factorization problem
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]

Dividing a large integer into factors is a well-known difficult problem that is heavily used in modern cryptography. One approach to achieve faster factorizations is to reduce the Integer factorization problem to another difficult problem, for example the Boolean satisfiability problem.

Many studies have been done on the optimization of algorithms that can solve the Boolean satisfiability problem effectively and multiple programs have been created for the purpose of achieving efficiency. This study focuses on one of these programs, MiniSAT, with the objective of finding patterns in the input that result in faster runtimes for solving reduced instances of the Integer factorization problem.

The method used for finding these patterns was to create different reductions from the Integer factorization problem to the Boolean satisfiability problem and then solving the reduced instances using MiniSAT. The order of the clauses in the boolean formulas were changed in order to analyze which order yields the best results. In total, seven orderings were tested for factorizing four products using three different reductions.

Our conclusions are that none of the patterns lead to better results for every test case. Not changing the order of the clauses will achieve consistent results, however there are cases when shuffles with variance could be preferable.

Abstract [sv]

Uppdelning av ett stort heltal i faktorer är ett välkänt svårt problem som vardagligen används i modern kryptografi för att kryptera data. Ett visst sätt att uppnå snabbare tider av faktoriseringen går ut på att reducera instanser av faktoriseringsproblemet till ett annat svårt problem, till exempel satisfierbarhetsproblemet.

Många studier har gjorts med avseende på optimeringar av algoritmer som löser satisfierbarhetsproblemet, och flera program har skapats i syftet att lösa problemet mer effektivt. Denna studie fokuserar på ett av dessa program, MiniSAT, med målet att hitta mönster i indatan som resulterar i snabbare lösningstider för reducerade instanser av faktoriseringsproblemet.

Metoden som används för att hitta dessa mönster var att skapa olika reduktioner från faktoriseringsproblemet till satisfierbarhetsproblemet och sedan lösa de reducerade probleminstanserna med MiniSAT. Ordningen av klausulerna i de booleanska formlerna ändrades och resultaten för varje ordning analyserades. Totalt testades sju olika sorteringar för att faktorisera fyra produkter med tre olika reduktioner.

Våra slutsatser är att inget specifikt mönster ger det bästa resultat för varje testfall. Att inte ändra ordningen på klausulerna ger konsistenta resultat, men det finns fall då en ordning som har varierande resultat kan vara att föredra.

Place, publisher, year, edition, pages
2015.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-166431OAI: oai:DiVA.org:kth-166431DiVA: diva2:811035
Supervisors
Examiners
Available from: 2015-05-28 Created: 2015-05-09 Last updated: 2015-05-28Bibliographically approved

Open Access in DiVA

fulltext(643 kB)308 downloads
File information
File name FULLTEXT01.pdfFile size 643 kBChecksum SHA-512
05bbf97a6fea56951738bde218b8a7b9dfa3130ae4db2040eae85e635075c9702a0801f126fb50a18e95d2c2be606cf9043aae77f8cca93552480969b869b8fc
Type fulltextMimetype application/pdf

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 308 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: 68 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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