I. IntroductionII. Mesh Routing AlgorithmIII. ImplementationA. Loading and UnloadingThe nonzero entries of original matrix is stored in the memory with row number (R ) and column number (C ) where the value is nonzero in the original matrix. Further more, these numbers are converted to the coordinate representation corresponding to the mesh of size of m x m where the mesh routing is going to be done. R is already divided by m to get the quotient r and the remainder c which tells where this packet has to be routed to on the routing process. Similarly, C is already divided by m to get ri and ci which tells where the packet should be loaded to which cell during the loading phase. This is the loading address to the cell corresponding to the column number of the original matrix as each cell in the mesh stores entries of one column of original matrix. Together with this value is the status bit at the left, showing the validity of the packet.B. Mesh Routing OperationIV. methodology AND TESTINGV. ResultsVI. conclusionAbstract— Factorization of large numbers has been a constantsource of interest for mathematicians and cryptographers alike. Thecryptographic community bases its interest in this problem as thereare many cryptographic schemes which base their strength on thefactorization problem, the RSA cryptosystem being a very familiarexample. Number Field Sieve is the fastest running algorithm forfactoring large numbers especially greater than 110 decimal digits.One step of this process is the Matrix step wherein a large sparsematrix is multiplied with vectors. Efficient implementations of thisstep in hardware are an ongoing research area. Bernstein hasproposed the mesh based circuit to improve the asymptotic cost offactoring by the order of the square root of compute time ofsequential alogorithm especially in matrix step. Shamir-Tromer hasproposed Mesh-Routing method following the idea of Bernstein inmatrix step. Only theoretical performance estimation has beenmade about the mesh circuit. We implement the Mesh Routingmethod in hardware to do multiple matrix-vector multiplications inthe matrix step of the factoring to provide the concrete performancemeasures for the implementation in FPGA devices. To implementthe mesh routing, the details of routing algorithm are analyzed,designed and developed. The logic related to clockwise transpositionrouting is developed considering the different cases of compare-exchange between neighboring cells which consists of valid andinvalid packet combinations. The complete logic for each cell isdeveloped. The behaviors of cells depend on the status position ofthe cells and phase of the iterating cycle. The complete mesh isinstantiated from these cells. The simulation of Mesh Routingbetween cells has been done. The area resources for the circuit foreach cell and the complete mesh are obtained and the timingperformance of the circuit has been evaluated. Index Terms— Factorization, Mesh Circuit, Mesh Routing,Mesh Computation, Number Field SieveI. INTRODUCTIONactoring a large integer into prime factors is one ofthe challenging tasks in cryptanalysis both in termsof computational complexity and the practicalimplementation. The Number Field Sieve (NFS)introduced by Pollard J M in 1988, is the asymptoticallyfastest known algorithm for the factorization of largenumbers (110 digits or more). This method has recentlybeen very effectively used to factorize certain RSAnumbers, the latest being the RSA-576 number with 576bits (174 digits) in it [16]. FThe NFS algorithm consists of the following steps:1. Polynomial Selection2. Sieving3. Matrix Step4. Square Root stepThis project focuses on the Matrix step in the NFS. Thisstep involves the multiplication of a large sparse matrixwith vectors. This result is then used to identify if there isa linear dependence between the entries in the sparsematrix. For the Matrix step there are two proposedsolutions. The one which came earlier was the Meshsorting approach proposed by Bernstein [1]. LaterShamir-Tromer et al [2] proposed the Mesh Routingmethod to accomplish the same. We propose to implementthe Mesh Routing algorithm in hardware for the Matrixstep.It is important to implement the hardware solutions to theNFS, as when the load is high, (which would happen forlarger numbers and when a faster implementation isneeded) hardware implementations have a distinctadvantage. Bernstein’s solution to the Matrix step involves Meshsorting, using Schimmler’s mesh sorting method. TheMesh routing step proposed by Shamir-Tromer et al. usesthe clockwise transposition method to achieve the sameresult of matrix vector multiplication. This approach usesa single routing operation per multiplication incomparison to 3 sorting operations needed by the former.We chose the Mesh routing algorithm to implement theMatrix step to provide the concrete performance andresource measures for which only theoretical estimationshave been shown.II. MESH ROUTING ALGORITHMThe matrix step concerns with finding linear dependencesin the matrix A obtained from the sieving step. The linearHardware Implementation of Mesh Routing inNumber Field Sieve FactoringSashisu Bajracharya and Deapesh MisraECE 746Spring 200419483752634275841863920 01 0 00 0 009483752634275841863920 01 0 00 0 00dependencies are found using Block Weidmann algorithm[8][11][12] by doing multiple matrix-by-vectormultiplications of the form: Av, A2v, …. , Akv where v is a random vector and k  2D/K. D is thenumber of columns of matrix A, K is the blocking factorwhere either K=1 or K  32 (where different vectors vare handled simultaneously). Another random vector u isselected and the sequences uv , uAv, ……. uAkv is used to calculate the minimum polynomial f of A. Thelinear dependent vectors are found from the minimumpolynomial fMatrix vector multiplication is done using the Meshrouting circuit. From figure 1, we can see for the columnsin the matrix where the corresponding position inmultiplying vector has non-zero value Fig.