Modulo reduction of large integers using classical andBarrett algorithmsThe widely claimed poor performance of public key cryptosystems in portable software usually results in faster, but non-portable assembly language implementations.A way out is to develop portable software that approaches the speed of an assembly language implementation as closely as possible.A basic operation in public key cryptosystems is the modularreduction of large numbers. An efficient implementation of thisoperation is the key to high performance.Three well-known algorithms are considered and evaluated withrespect to their software performance:(1) Classical algorithm(2) Barrett’s algorithm(3) Montgomery algorithmBarrett modular reduction algorithm:Input: positive integers x=(x 2k-1……x1x0 ) b,m=(m k-1……m1m0 ) b,and u=[b 2k/m ]Output: r=x mod m(1)qi= [ x/b k-1 ], q2= q1 * u, q3= q2/ b k+1 (2)r1=s mod b k+1 m r2=q3 * m mod b k+1r=r1-r2(3)If r<0 then r=r+ b k+1(4)While r>=m do: r=r-m;(5)Return(r)Tables and Graphs:K Time(µsec)2 56504 64718 686616 766432 884764 10887128 71658256 26140512 661961024 2047832048 695505Execution times for the reduction of 2k-digit numbers modulo k-digit modulus m for the Barrett Algorithm02000004000006000008000002 4 8 16 32 64 128 256 512 1024 2048kt(usec)4. Conclusion:A theoretical and practical comparison has been made of 2 algorithms for the reduction of large numbers. It has been shown that in a good portable implementation the two algorithms are quite close to each other in performance. The classical algorithm is thebest choice for single modular reductions. Modular exponentiation based on Barrett’s algorithm is superior to the others for small
View Full Document
Unlocking...