Volume 15, 2003

University of Bialystok

Copyright (c) 2003 Association of Mizar Users

**Masaaki Niimura**- Shinshu University, Nagano
**Yasushi Fuwa**- Shinshu University, Nagano

- In RSA Cryptograms, many modulo calculations are used, but modulo calculation is based on many subtractions and it takes long time to calculate. In this article, we explain about a new modulo calculation algorithm using table. And we proof that upper 3 digits of Radix-$2^k$ SD numbers is enough to specify the answer. In the first section, we prepared some useful theorems for operations of Radix-$2^k$ SD Number. In the second section, we defined Upper 3 Digits of Radix-$2^k$ SD number and proved that property. In the third section, we proved some property about the minimum digits of Radix-$2^k$ SD number. In the fourth section, we identified the range of modulo arithmetic result and proved that the Upper 3 Digits indicate two possible answers. And in the last section, we defined a function to select true answer from the results of Upper 3 Digits.

- Some Useful Theorems
- Definitions of Upper 3 Digits of Radix-$2^k$ SD Number and Its Property
- Properties of Minimum Digits of Radix-$2^k$ SD Number
- Modulo Calculation Algorithm Using Upper 3 Digits of Radix-$2^k$ SD Number
- How to Identify the Range of Modulo Arithmetic Result

- [1]
Grzegorz Bancerek.
The fundamental properties of natural numbers.
*Journal of Formalized Mathematics*, 1, 1989. - [2]
Grzegorz Bancerek and Krzysztof Hryniewiecki.
Segments of natural numbers and finite sequences.
*Journal of Formalized Mathematics*, 1, 1989. - [3]
Czeslaw Bylinski.
Functions and their basic properties.
*Journal of Formalized Mathematics*, 1, 1989. - [4]
Yoshinori Fujisawa and Yasushi Fuwa.
Definitions of radix-$2^k$ signed-digit number and its adder algorithm.
*Journal of Formalized Mathematics*, 11, 1999. - [5]
Andrzej Kondracki.
The Chinese Remainder Theorem.
*Journal of Formalized Mathematics*, 9, 1997. - [6]
Masaaki Niimura and Yasushi Fuwa.
Magnitude relation properties of radix-$2^k$ sd number.
*Journal of Formalized Mathematics*, 15, 2003. - [7]
Takaya Nishiyama and Yasuho Mizuhara.
Binary arithmetics.
*Journal of Formalized Mathematics*, 5, 1993. - [8]
Andrzej Trybulec.
Tarski Grothendieck set theory.
*Journal of Formalized Mathematics*, Axiomatics, 1989. - [9]
Michal J. Trybulec.
Integers.
*Journal of Formalized Mathematics*, 2, 1990. - [10]
Zinaida Trybulec.
Properties of subsets.
*Journal of Formalized Mathematics*, 1, 1989. - [11]
Edmund Woronowicz.
Relations defined on sets.
*Journal of Formalized Mathematics*, 1, 1989.

[ Download a postscript version, MML identifier index, Mizar home page]