New Distance Concept and Graph Theory Approach for Certain Coding Techniques Design and Analysis
deletions, IEEE Transactions on Information Theory , vol. PP, no. 99, p. 1, 2017. 7. K. Ouahada, T. G. Swart, and H. C. Ferreira, Binary permutation sequences as subsets of levenshtein codes and higher order spectral nulls codes, in 2006 IEEE Information Theory Workshop - ITW ’06 Chengdu , pp. 535–539, Chengdu, China, Oct. 2006. 8. A. Viterbi and J. Omura, Principles of Digital Communication and Coding . McGraw-Hill Kogakusha LTD, Tokyo Japan, 1979. 9. A. J. H. Vinck and H. C. Ferreira, Permutation trellis codes, in in Proceedings of the
Linear Congruence Relation and Complete Residue Systems
Mathematics , 9(1):191-196, 2001. [13] Yoshinori Fujisawa and Yasushi Fuwa. The Euler's function. Formalized Mathematics , 6(4):549-551, 1997. [14] Krzysztof Hryniewiecki. Basic properties of real numbers. Formalized Mathematics , 1(1):35-40, 1990. [15] Andrzej Kondracki. The Chinese Remainder Theorem. Formalized Mathematics , 6(4):573-577, 1997. [16] Rafał Kwiatek. Factorial and Newton coefficients. Formalized Mathematics , 1(5):887-890, 1990
Modular Integer Arithmetic
Modular Integer Arithmetic
In this article we show the correctness of integer arithmetic based on Chinese Remainder theorem as described e.g. in [11]: Integers are transformed to finite sequences of modular integers, on which the arithmetic operations are performed. Retransformation of the results to the integers is then accomplished by means of the Chinese Remainder theorem. The method presented is a typical example for computing in homomorphic images.
Isomorphisms of Direct Products of Finite Cyclic Groups
Summary
In this article, we formalize that every finite cyclic group is isomorphic to a direct product of finite cyclic groups which orders are relative prime. This theorem is closely related to the Chinese Remainder theorem ([18]) and is a useful lemma to prove the basis theorem for finite abelian groups and the fundamental theorem of finite abelian groups. Moreover, we formalize some facts about the product of a finite sequence of abelian groups.
Extended Euclidean Algorithm and CRT Algorithm
Summary
In this article we formalize some number theoretical algorithms, Euclidean Algorithm and Extended Euclidean Algorithm [9]. Besides the a gcd b, Extended Euclidean Algorithm can calculate a pair of two integers (x, y) that holds ax + by = a gcd b. In addition, we formalize an algorithm that can compute a solution of the Chinese remainder theorem by using Extended Euclidean Algorithm. Our aim is to support the implementation of number theoretic tools. Our formalization of those algorithms is based on the source code of the NZMATH, a number theory oriented calculation system developed by Tokyo Metropolitan University [8].
Basic Properties of Primitive Root and Order Function
. Functions and their basic properties. Formalized Mathematics , 1( 1 ):55-65, 1990. [6] Czesław Bylinski. Some basic properties of sets. Formalized Mathematics , 1( 1 ):47-53, 1990. [7] Agata Darmochwał. Finite sets. Formalized Mathematics , 1( 1 ):165-167, 1990. [8] Zhang Dexin. Integer Theory . Science Publication, China, 1965. [9] Yoshinori Fujisawa and Yasushi Fuwa. The Euler’s function. Formalized Mathematics , 6( 4 ):549-551, 1997. [10] Yoshinori Fujisawa, Yasushi Fuwa, and Hidetaka
Gauss Lemma and Law of Quadratic Reciprocity
. Formalized Mathematics , 1(1):153-164, 1990. [10] Czesław Byliński. The sum and product of finite sequences of real numbers. Formalized Mathematics , 1(4):661-668, 1990. [11] Agata Darmochwał. Finite sets. Formalized Mathematics , 1(1):165-167, 1990. [12] Zhang Dexin. Integer Theory. Science Publication, China, 1965. [13] Yoshinori Fujisawa, Yasushi Fuwa, and Hidetaka Shimizu. Public-key cryptography and Pepin's test for the primality of Fermat numbers. Formalized
On Subnomials
, 131(2):300 – 308, 2011. doi: http://dx.doi.org/10.1016/j.jnt.2010.08.004 . [9] Andrzej Kondracki. The Chinese Remainder Theorem. Formalized Mathematics , 6( 4 ): 573–577, 1997. [10] Rafał Kwiatek. Factorial and Newton coefficients. Formalized Mathematics , 1( 5 ):887–890, 1990. [11] Rafał Kwiatek and Grzegorz Zwara. The divisibility of integers and integer relatively primes. Formalized Mathematics , 1( 5 ):829–832, 1990. [12] W.W. Sawyer. The Search for Pattern . Penguin Books Ltd, Harmondsworth, Middlessex, England, 1970. [13