Advances in coding theory and crytography

T. Shaska, W C Huffman, David Joyner, V Ustimenko, T. Shaska, W. C. Huffman9812707018, 9789812707017

In the new era of technology and advanced communications, coding theory and cryptography play a particularly significant role with a huge amount of research being done in both areas. This book presents some of that research, authored by prominent experts in the field. The book contains articles from a variety of topics most of which are from coding theory. Such topics include codes over order domains, Groebner representation of linear codes, Griesmer codes, optical orthogonal codes, lattices and theta functions related to codes, Goppa codes and Tschirnhausen modules, s-extremal codes, automorphisms of codes, etc. There are also papers in cryptography which include articles on extremal graph theory and its applications in cryptography, fast arithmetic on hyperelliptic curves via continued fraction expansions, etc. Researchers working in coding theory and cryptography will find this book an excellent source of information on recent research.

---

Table of contents :
CONTENTS……Page 10
Preface……Page 6
List of authors……Page 8
1. Introduction……Page 12
2. Codes from Order Domains……Page 14
3. Preliminaries on Inverse Systems……Page 15
4. The Key Equation and its Relation to the BMS Algorithm……Page 18
References……Page 26
1. Introduction……Page 28
2. M¨oller’s algorithm……Page 29
3. Gr¨obner representation of a linear code……Page 31
4. Reduced and border bases……Page 35
4.1. Binary codes……Page 37
5.1. Gradient decoding……Page 38
5.2. Permutation equivalent codes……Page 40
5.3. Gr¨obner codewords for binary codes……Page 41
References……Page 42
2. Codes and the Griesmer bound……Page 44
3. Codes and multisets……Page 45
3.1. Arcs……Page 46
3.2. Combinations……Page 47
4. Minihypers……Page 48
4.1. The Hamada bound……Page 49
4.2. Achievement of the Griesmer bound……Page 52
5. Divisibility……Page 53
6. Three-dimensional Griesmer codes……Page 54
6.2. Divisibility……Page 55
6.3. The [92, 3, 80]8 codes……Page 57
6.4. Duality……Page 58
References……Page 59
1. Introduction……Page 62
2. Preliminaries……Page 64
3. A construction from arcs in d-flats……Page 68
4. A construction from arcs of higher degree……Page 70
5. Affine constructions……Page 74
6. Conclusion……Page 78
References……Page 79
1. Introduction……Page 81
2. Preliminaries……Page 83
2.1. Theta functions over Fp……Page 84
3. Theta functions of codes over R……Page 85
3.1. A MacWilliams identity……Page 86
3.2. A generalization of the symmetric weight enumerator polynomial……Page 87
4.1. The case p = 2……Page 88
4.2. The case p > 2……Page 89
References……Page 90
Introduction……Page 92
1. Goppa Codes and rank-2 Vector Bundles……Page 94
2. The Klein Curve as Cover……Page 97
3. The Tschirnhausen Module of the Cover……Page 104
4.1. Adeles and pseudo-differentials……Page 106
4.2. Goppa codes and adeles……Page 107
References……Page 110
1. Introduction……Page 112
2. s-Extremal Additive F4 Codes……Page 113
3. s-Extremal Binary Codes……Page 120
References……Page 123
1. Introduction……Page 125
2. AG codes and GRS codes……Page 126
3. Automorphisms……Page 128
4. Examples……Page 132
5. Structure of the representations……Page 133
References……Page 135
1. Introduction……Page 137
2.1. Equivalence of linear codes……Page 138
2.2. Isomorphism of binary matrices……Page 139
2.3. The connection between equivalence of linear codes and isomorphism of binary matrices……Page 142
3.1. Orbits……Page 144
3.2. Partitions, ordered partitions……Page 145
3.3. Definition of invariants……Page 146
3.4. Properties of partitions induced by invariants……Page 148
3.5. Invariants of columns and rows……Page 150
4. Main algorithm……Page 155
4.1. Additional invariants……Page 159
References……Page 161
1. Introduction……Page 163
2. Background and terminology……Page 164
3. Binary codes of cubic graphs……Page 165
4. 3-PD-sets……Page 168
5. Discussion……Page 169
References……Page 170
1. Introduction……Page 171
2. Experimental Results……Page 173
3. Analysis of the Sum-Product Algorithm……Page 175
Bipartite Graphs……Page 176
The Sum-Product Algorithm……Page 177
4. Examples……Page 183
2 bits n checks……Page 185
4-Choose-2……Page 186
3-to-1 covers of the complete 2-bits-3-checks graph……Page 187
Degradation of performance with the coarse termination criterion……Page 189
References……Page 190
1. Introduction……Page 192
2.1. Binary relations and special colorings……Page 195
2.2. General symmetric algorithm……Page 196
2.3. Symbolic computations and public keys……Page 197
3. The incidence structures defined over commutative rings……Page 198
4. Symmetric encryption, algorithms related to graphs RF(n,K)……Page 201
4.1. The encryption algorithm……Page 202
4.2. Decryption procedure……Page 203
5. Public keys……Page 205
6. Other algebraic parallelotopic graphs……Page 206
7. Remarks on implementation……Page 208
References……Page 209
Fast arithmetic on hyperelliptic curves via continued fraction expansions M. J. Jacobson, Jr., R. Scheidler and A. Stein……Page 211
1. Introduction and Motivation……Page 212
2. Continued Fraction Expansions……Page 214
3. Hyperelliptic Curves……Page 217
3.3. Real Curves……Page 221
4. Reduced Ideals and Divisors……Page 222
4.3. Real Curves……Page 223
5. Reduction and Baby Steps……Page 224
6. Giant Steps and the Idea of NUCOMP……Page 229
6.3. Real Curves……Page 230
7. NUCOMP……Page 231
8. Giant Steps with NUCOMP……Page 235
9. NUCOMP Algorithms……Page 241
10. An Extra Reduced Divisor……Page 244
11. Numerical Results……Page 246
11.1. Binary Exponentiation……Page 247
11.2. Key Exchange……Page 249
12. Conclusions……Page 251
References……Page 253
1. Introduction……Page 255
2. Method of Computation……Page 256
Appendix. Tables……Page 259
References……Page 267