A modified Euclidean algorithm and the VLSI implementation

The extended Euclidean algorithm is important in algebraic and symbolic computations, in error correcting codes, in code division multiple access and, in cryptology. We propose a modified algorithm and a recursive implementation. Both the time and space complexity of the implementation is better than conventional ones. The regular and modular construction implies that it can be implemented on VLSI chips. The implementation can be used in decoding BCH codes, RS codes and Goppa codes. A throughput of hundreds of megabits per second is achievable