PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Integer Factorization – Cryptology Meets Number Theory

Autorzy
Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Integer factorization is one of the oldest mathematical problems. Initially, the interest in factorization was motivated by curiosity about be­haviour of prime numbers, which are the basic building blocks of all other integers. Early factorization algorithms were not very efficient. However, this dramatically has changed after the invention of the well-known RSA public-key cryptosystem. The reason for this was simple. Finding an efficient fac­toring algorithm is equivalent to breaking RSA. The work overviews development of integer factoring algorithms. It starts from the classical sieve of Eratosthenes, covers the Fermat algorithm and explains the quadratic sieve, which is a good representative of modern fac­toring algorithms. The progress in factoring is illustrated by examples of RSA challenge moduli, which have been factorized by groups of mathemati­cians and cryptographers. Shor's quantum factorization algorithm with poly­nomial complexity is described and the impact on public-key encryption is discussed.
Rocznik
Tom
Strony
7--20
Opis fizyczny
Bibliogr. 15 poz., tab.
Twórcy
  • CSIRO, Sydney, Australia, Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland
Bibliografia
  • [1] Crandall, R., Pomerance, C., 2001, Prime Numbers: A Computational Perspective, Springer.
  • [2] Dattani, N.S., Bryans, N., 2014, Quantum Factorization of 56153 with only 4 Qubits, Quantum Physics, arXiv:1411.6758,
  • [3] Hirvensalo, M., 2001, Quantum Computing, Natural Computing Series, Springer.
  • [4] Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H., Timofeev, A., Zimmermann, P., 2010, Factorization of a 768-bit RSA Modulus, CRYPTO’10 Proceedings of the 30th Annual Conference on Advances in Cryptology, August 15–19, Santa Barbara, CA, USA, pp. 333–350.
  • [5] Knuth, D., 1997, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 3rd ed., Addison-Wesley, Boston, MA, USA.
  • [6] Lehmer, D.H., Powers, R.E., 1931, On Factoring Large Numbers, Bull. Amer. Math. Soc., vol. 37, no. 10, pp. 770–776.
  • [7] Manasse, M., Lenstra, A.K., 1999, RSA Honor Roll, http://www.ontko.com/pub/rayo/primes/hr_ rsa.txt (20.08.2018).
  • [8] Martin-López, E., Laing, A., Lawson, T., Alvarez, R., Zhou, Xiao-Qi, O’Brien, J.L., 2012, Experimental Realization of Shor’s Quantum Factoring Algorithm using Qubit Recycling, Nature Photonics, vol. 6, no. 11.
  • [9] NIST, 2018, Post-Quantum Cryptography, https://csrc.nist.gov/Projects/Post-Quantum-Cryptography, (20.08.2018).
  • [10] Pieprzyk, J., Hardjono, T., Seberry, J., 2003, Fundamentals of Computer Security, Springer.
  • [11] Pomerance, C., 1996, A Tale of Two Sieves, Notices Amer. Math. Soc, vol. 43, pp.1473–1485.
  • [12] Rivest, R., Shamir, A., Adleman, L., 1978, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol. 21, no. 2, pp. 120–126.
  • [13] Shor, P.W., 1997, Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing 26.5, pp. 1484–1509.
  • [14] Vandersypen, L.M.K., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H., Chuang, I.L., Experimental Realization of Shor’s Quantum Factoring Algorithm using Nuclear Magnetic Resonance, Nature, vol. 414 no. 6866, pp.883–887.
  • [15] Wagstaff, S.S. Jr., 2013, The Joy of Factoring, American Mathematical Society, Providence, RI, USA.
Uwagi
Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-8548bbb2-f663-4442-87e9-388029d533e6
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.