摘要 |
Fast modulo computation with reduced RAM size. Modern cryptographical communications often require modulo operations. A method of computing Y modulo X (= modulo (Y,X); for short: Y mod X), where 2<n-1> </= X </= 2<n>-1 and 0 </= Y </= 2<L>-1, has been published in "A new-modulo computation algorithm", D. Naccache, H. M'Silti, RAIRO-OR, (3) 1990. Value n denotes the length of X in bits and L represents the maximal size of Y accepted by the computation. But in small cryptographical devices (e.g. smart-cards) RAM memory is not available in big quantities. A special implementation of this computation allows an efficient calculation of such modulo functions. Thereby a RAM (12) size of only about three times the size of X is required for computing R = Y mod X. Also no divisions are required from a microcontroller or microprocessor (11) if X and a constant number K are stored on a retrievable medium, e.g. a ROM (13). Invention can be used for smart-cards. <IMAGE> |