The number field sieve with three number fields
DOI:
CSTR:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The mathematical security of the RSA cryptosystem is based on the problem of factoring large integers. At present, the number field sieve is the most efficient algorithm known for factoring integers larger than 365 bits, while its time complexity is still sub-exponential. Integers larger than 1024 bits, which are widely used in RSA cryptosystem, cannot be factored by means of the number field sieve. So it is significant to study the number field sieve.Now, the general number field sieve often uses two number fields, while multiple number fields are seldom considered. The general number field sieve, through adaptation, can use three number fields, i.e. two algebraic number fields and one rational number field. Analysis shows that the time complexity of the modified number field sieve and the general number field sieve are at the same level. However, the modified number field sieve can combine more computation, so it can save more time in practice. Finally, the result is verified by two experiments.

    Reference
    Related
    Cited by
Get Citation
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 14,2011
  • Revised:
  • Adopted:
  • Online: August 28,2012
  • Published:
Article QR Code