Paper 2016/937

A Comparative S-Index in Factoring RSA Modulus via Lucas Sequences

Nur Azman Abu, Shekh Faisal Abdul-Latip, and Muhammad Rezal Kamel Ariffin

Abstract

General Lucas sequences are practically useful in cryptography. In the past quarter century, factoring large RSA modulo into its primes is one of the most important and most challenging problems in computational number theory. A factoring technique on RSA modulo is mainly hindered by the strong prime properties. The success of factoring few large RSA modulo within the last few decades has been due to computing prowess overcoming one strong prime of RSA modulo. In this paper, some useful properties of Lucas sequences shall be explored in factoring RSA modulo. This paper introduces the S-index formation in solving quadratic equation modulo N. The S-index pattern is very useful in designing an algorithm to factor RSA modulo. At any instance in the factoring algorithm, the accumulative result stands independently. In effect, there is no clear direction to maneuver whether to go left or right. The S-index will add another comparative tool to better maneuver in a factoring process. On one hand, it shall remain a theoretical challenge to overcome the strong prime properties. On the other hand, it shall remain a computational challenge to achieve a running time within polynomial time to factor RSA modulo. This paper will propose an avenue to do both using general Lucas sequences.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CRYPTOLOGY 2016 Conference Proceeding
Keywords
Cryptanalysisfactoringpublic-key cryptographyRSA
Contact author(s)
nura @ utem edu my
History
2016-09-29: received
Short URL
https://ia.cr/2016/937
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/937,
      author = {Nur Azman Abu and Shekh Faisal Abdul-Latip and Muhammad Rezal Kamel Ariffin},
      title = {A Comparative S-Index in Factoring RSA Modulus via Lucas Sequences},
      howpublished = {Cryptology ePrint Archive, Paper 2016/937},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/937}},
      url = {https://eprint.iacr.org/2016/937}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.