@MISC{RADIX_2.MIZ,
  AUTHOR = {Fuwa, Yasushi and Fujisawa, Yoshinori},
  TITLE = {High-Speed Algorithms for {RSA} Cryptograms},
  SECTION1 = {Some Useful Theorems},
  SECTION2 = {Properties of Addition Operation Using Radix-$2^k$ Signed-Digit Numbers},
  SECTION3 = {Definitions on the Relation Between a Finite Sequence of $k$-SD and 
a Finite Sequence of ${\Bbb N}$ and Some Properties about them},
  SECTION4 = {A High-Speed Algorithm of Calculation of $(a*b)$ mod $b$ 
  Based on Radix-$2^k$ Signed-Digit Numbers and its Correctness},
  SECTION5 = {A High-Speed Algorithm of Calculation of $(a^b)$ mod $b$ 
Based on a Radix-$2^k$ Signed-Digit Numbers and its Correctness},
  DAY = {01},
  MONTH = {February},
  YEAR = {2000},
  ADDRESS1 = {Shinshu University\\Nagano},
  ADDRESS2 = {Shinshu University\\Nagano},
  SUMMARY = {In this article, we propose a new high-speed processing method for encoding
and decoding the RSA cryptogram that is a kind of public-key cryptogram. This
cryptogram is not only used for encrypting data, but also for such purposes
as authentication. However, the encoding and decoding processes take a long
time because they require a great deal of calculations. As a result, this
cryptogram is not suited for practical use. Until now, we proposed a 
high-speed 
algorithm of addition using radix-$2^k$ signed-digit numbers and clarified
correctness of it (\cite{RADIX_1.ABS}).
  In this article, we defined two new operations for a high-speed coding and
encoding processes on public-key cryptograms based on radix-$2^k$ signed-digit
(SD) numbers. One is calculation of $(a*b)$ mod $c$ ($a,b,c$ are natural numbers).
Another one is calculation of $(a^b)$ mod $c$ ($a,b,c$ are natural numbers). 
Their
calculations are realized repetition of addition. We propose a high-speed
algorithm of their calculations using proposed addition algorithm and clarify
the correctness of them.
  In the first section, we prepared some useful theorems for natural numbers
and integers and so on. In the second section, we proved some properties of
addition operation using a radix-$2^k$ SD numbers. In the third section, we
defined some functions on the relation between a finite sequence of k-SD and
a finite sequence of ${\Bbb N}$ and proved some properties about them. In the fourth
section, algorithm of calculation of $(a*b)$ mod $c$ based on radix-$2^k$ SD numbers
is proposed and its correctness is clarified. In the last section, algorithm
of calculation of $(a^b)$ mod $c$ based on radix-$2^k$ SD numbers is proposed and
we clarified its correctness.}}

