High speed modular divider based on GCD algorithm over GF(2~m)
Gui Liang Feng · Journal of Communications · 2008
With an in-depth analysis,improvement was done on the architecture and the determinant standard of the tra-ditional GCD algorithm to build a novel algorithm.It reduces the comparisons from 4 to 3 in each iteration.Moreover,it’s iteration number is no longer fixed 2m but the upper bound of the sum of the length of the denominator and m.Hence the efficiency is fundamentally increased.Furthermore,based on A.Zadeh’s ideology,the new algorithm was extended to radix 4 and 8 respectively,such that the number decreased 50% and 34% comparing with the original one,thereby greatly reducing the computing time.Experiments with MATLAB proved the efficiency of our new algorithms.