HARDWARE IMPLEMENTATIONS FOR SYSTOLIC COMPUTATION OF THE JACOBI SYMBOL
Kiran K Vedantam · OhioLink ETD Center (Ohio Library and Information Network) · 2006
⎛ b for integers a and is an important step in a number of cryptographic processes.This thesis presents various algorithms for computing the Jacobi symbol and hardware implementations of two such algorithms.Both the algorithms are systolic and thus each can be implemented as an array of identical cells.The first algorithm for unsigned numbers is slower but also easier to implement in hardware than the second algorithm for signed numbers.The systolic nature of the algorithm is responsible for the space and time efficiency of the implementation.The simple and regular architecture lends itself very well to VLSI implementation and also makes it scalable.We wrote a VHDL description of both the algorithms.The description was used to obtain semi custom layout estimates and to implement the algorithms on Alte a ra devices.Both the algorithms were also tested through simulation and on Altera devices.