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
Bitwise relations between n and φ(n): A novel approach at prime number factorization
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Cryptography plays a crucial role in today’s society. Given the influence, cryptographic algorithms need to be trustworthy. Cryptographic algorithms such as RSA relies on the problem of prime number factorization to provide its confidentiality. Hence finding a way to make it computationally feasible to find the prime factors of any integer would break RSA’s confidentiality.

The approach presented in this thesis explores the possibility of trying to construct φ(n) from n. This enables factorization of n into its two prime numbers p and q through the method presented in the original RSA paper. The construction of φ(n) from n is achieved by analyzing bitwise relations between the two.

While there are some limitations on p and q this thesis can in favorable circumstances construct about half of the bits in φ(n) from n. Moreover, based on the research a conjecture has been proposed which outlines further characteristics between n and φ(n).

Place, publisher, year, edition, pages
2018. , p. 17
Keywords [en]
bitwise relations, prime number factorization, Euler’s Totient function, RSA
National Category
Mathematics Computer and Information Sciences Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:bth-16655OAI: oai:DiVA.org:bth-16655DiVA, id: diva2:1228872
Subject / course
DV1478 Bachelor Thesis in Computer Science
Supervisors
Examiners
Available from: 2018-07-03 Created: 2018-06-28 Last updated: 2018-07-03Bibliographically approved

Open Access in DiVA

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

By organisation
Department of Computer Science and Engineering
MathematicsComputer and Information SciencesProbability Theory and Statistics

Search outside of DiVA

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