Publication

Abstract : The security of well-known cryptographic system RSA is dependent on hardness of factoring large integers. In cryptanalysis of RSA and also other symmetric encryption algorithm, one gets a sparse system of linear equations which needs to be solved for a few solution vectors. The linear system (or matrix) coming from RSA is special. It is very large and extremely sparse, means each equation involves very few variables. The well-known Gaussian elimination technique is not suitable for handling such a large matrix. The matrix should be reduced first to a smaller one one but still sparse, in order to avoid problems such as memory crash. Thus, a small improvement in the methods for reducing the matrix will have a significant impact on the total running time for factoring integers. This paper addresses the problem of reducing a given sparse matrix and possible solutions for an efficient implementation.