TY - GEN
T1 - A parallel GNFS algorithm with the improved Linbox montgomery block Lanczos method for integer factorization
AU - Yang, Laurence Tianruo
AU - Xu, Li
AU - Park, Jong Hyuk
PY - 2008
Y1 - 2008
N2 - RSA algorithm is a very popular public key cryptosystem which has been widely used in industries. Its security relies on the dijficulty of factoring large integers. The general number field sieve (GNFS) is so far the best known algorithm for factoring large integers over 110 digits. The Montgomery's block Lanczos method from. Linbox [9] is for solving large and sparse linear systems over finite fields and it can be integrated into GNFS algorithm. This paper introduces an improved Montgomery block Lanczos method, based on the version developed in Linbox. integrated with our previously developed parallel GNFS algorithm. This method has a better performance comparing with the original one, can find more solutions or dependencies than the original one with less time complexities. Implementation details and experimental results will be provided as well in the paper as well.
AB - RSA algorithm is a very popular public key cryptosystem which has been widely used in industries. Its security relies on the dijficulty of factoring large integers. The general number field sieve (GNFS) is so far the best known algorithm for factoring large integers over 110 digits. The Montgomery's block Lanczos method from. Linbox [9] is for solving large and sparse linear systems over finite fields and it can be integrated into GNFS algorithm. This paper introduces an improved Montgomery block Lanczos method, based on the version developed in Linbox. integrated with our previously developed parallel GNFS algorithm. This method has a better performance comparing with the original one, can find more solutions or dependencies than the original one with less time complexities. Implementation details and experimental results will be provided as well in the paper as well.
UR - https://www.scopus.com/pages/publications/51349086305
U2 - 10.1109/ISA.2008.113
DO - 10.1109/ISA.2008.113
M3 - Conference contribution
AN - SCOPUS:51349086305
SN - 9780769531267
T3 - Proceedings of the 2nd International Conference on Information Security and Assurance, ISA 2008
SP - 403
EP - 409
BT - Proceedings of the 2nd International Conference on Information Security and Assurance, ISA 2008
T2 - 2nd International Conference on Information Security and Assurance, ISA 2008
Y2 - 24 April 2008 through 26 April 2008
ER -