Two Binary Algorithms for Calculating the Jacobi Symbol and a Fast Systolic Implementation in Hardware

Efficiently computing the Jacobi symbol J(a,b) for integers a and b is an important step in a number of cryptographic processes. We present two algorithms for computing J(a,b) which can easily be implemented in hardware and which are efficient with respect to time and space. The first algorithm we describe is slower but also easier to implement in hardware than the second. The algorithms are systolic and thus each can be implemented as an array of identical cells. We have developed VHDL descriptions of these algorithms, and we provide here example code for the process statements which are central to the implementation of each algorithm. Each algorithm has been tested on an Altera Cyclone EP1C6Q240 device and simulated on an Altera Stratix-II EP2S15F484C3 device.