The Application And Parallel Study Of The Lanczos Algorithm In The Number Field Sieve

It is well known that the security of the RSA cryptosystem is based on the diffi-culty of integer factorization. The General Number Field Sieve (GNFS) is one of themost appropriate algorithms to solve this problem of digit length over130. Solvinglarge sparse linear equations is a very crucial step. With the increase of the RSA mod-ulus, the scale of the data related to crack this problem is also growing larger andlarger. The Lanczos algorithm, owing to its superiority in dealing with extensive data,becomes more and more important nowadays.Firstly, the relevant theories of the Number Field Sieve are clearly and directlyexplained. Secondly, the specific principles of Lanczos and Block Lanczos for solvingequations are descripted in detail. Thirdly, it comes the most important part of the the-sis. For some special input, the Block Lanczos algorithm may suddenly fail. And thedefect is exactly caused by the random initialization phase. Besides, the input ofBlock Lanczos must be symmetric. So a general matrix must conduct the symmetry toreduce the time complexity of algorithm. According to natures of the condition for-mula and the input matrix, a kind of initialization algorithm is designed. It is that thecondition formula is validated row by row and then the full matrix is constructed. Alsobased on the nature of the positive definite matrix, another algorithm may be proposed.Performance of improvement algorithms is studied from three aspects. They are com-parisons of the success rate of running programs, the number of final solutions andrunning time of the initialization phase. Experimental results and theoretical analysisare basically consistent. Results of the improved algorithm meet expectations to someextent. Meanwhile, the final symmetric form used in the algorithm is determined byresearch and analysis of two forms and their advantages and disadvantages. Finally,the structure of sieving matrix is fully analyzed and found that the distribution followscertain regularity. Then by combination of the best data storage formats, the CSRform is used for dense part and the SLE form for the sparse part. Thus, a hybrid datastorage format is creatively designed, which makes the Block Lanczos parallel algo-rithms more efficient and flexible.