| 摘要 |
PROBLEM TO BE SOLVED: To perform inverse element calculation regularly and efficiently without using division by holding a specific number of values which are found sequentially by a 1st arithmetic means while making them correspond in order from the least significant digit to the most significant digit of an inverse element. SOLUTION: Two mutually prime integers A and N are given as inputs and an inverse element X of the integer A modulo the integer N is given. However, 0<A<N and 0<X<N. Here, an agreement of N=q<s> , where (q) is a prime number or an integer which is relatively prime with the integer A and (s) is a natural number. Because of N=q<s> , (s) can be inputted as a parameter instead of inputting the value of the integer N in decimal or (q)-ary notation. Further, when (q) is implemented periodically, (q) need not be inputted to the device. Here, the integer A and inverse element X are in (q)-ary representation in the device at need. |
