RNS-MODULO REDUCTION UPON A RESTRICTED BASE VALUE SET AND ITS APPLICABILITY TO RSA CRYPTOGRAPHY

For a module reduction scheme in RNS a set of restricted base values i s proposed. In RNS, additions and multiplications can be computed in p arallel, avoiding carry propagation delays. This advantage enables the implementation of scalable, parallel arithmetic units for computation s in very large finite fields. For such a long integer arithmetic unit certain selection criteria for the base value set have been worked ou t, targeted to optimise the module reduction operation on the RNS digi t level. As public key cryptography heavily depends on arithmetic in l arge finite fields, a parallelisable RSA variant is shown as a sample application. (C) 1998 Elsevier Science Ltd. All rights reserved.