A New Montgomery Algorithm Based on Binary Redundant Representations for Modular Exponentiation with Very Large Operand

The Montgomery algorithm used in modular exponentiation with very large operand is briefly introduced. A new Montgomery algorithm is presented for modular exponentiation computation with very large operand based on binary redundant representations. Computation of modular exponentiation with very large operand is furthermore speeded up by decreasing recursive steps and carry propagation in modular multiplication.It is shown by theoretical analysis that recursive stops are also decreased by 17.2% on average.