chiark / gitweb /
Merge branch 'mdw/rsvr'
[catacomb] / math / gf.h
CommitLineData
ceb3f0c0 1/* -*-c-*-
ceb3f0c0 2 *
3 * Arithmetic on binary polynomials
4 *
5 * (c) 2004 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
ceb3f0c0 9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
45c0fd36 16 *
ceb3f0c0 17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
45c0fd36 21 *
ceb3f0c0 22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
ceb3f0c0 28#ifndef CATACOMB_GF_H
29#define CATACOMB_GF_H
30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Header files ------------------------------------------------------*/
36
37#ifndef CATACOMB_MP_H
38# include "mp.h"
39#endif
40
41#ifndef CATACOMB_GFX_H
42# include "gfx.h"
43#endif
44
45/*----- Functions provided ------------------------------------------------*/
46
47/* --- @gf_add@ --- *
48 *
49 * Arguments: @mp *d@ = destination
50 * @mp *a, *b@ = sources
51 *
52 * Returns: Result, @a@ added to @b@.
53 */
54
55extern mp *gf_add(mp */*d*/, mp */*a*/, mp */*b*/);
56#define gf_sub gf_add
57
58/* --- @gf_mul@ --- *
59 *
60 * Arguments: @mp *d@ = destination
61 * @mp *a, *b@ = sources
62 *
63 * Returns: Result, @a@ multiplied by @b@.
64 */
65
66extern mp *gf_mul(mp */*d*/, mp */*a*/, mp */*b*/);
67
68/* --- @gf_sqr@ --- *
69 *
70 * Arguments: @mp *d@ = destination
71 * @mp *a@ = source
72 *
73 * Returns: Result, @a@ squared.
74 */
75
76extern mp *gf_sqr(mp */*d*/, mp */*a*/);
77
78/* --- @gf_div@ --- *
79 *
80 * Arguments: @mp **qq, **rr@ = destination, quotient and remainder
81 * @mp *a, *b@ = sources
82 *
83 * Use: Calculates the quotient and remainder when @a@ is divided by
84 * @b@. The destinations @*qq@ and @*rr@ must be distinct.
85 * Either of @qq@ or @rr@ may be null to indicate that the
86 * result is irrelevant. (Discarding both results is silly.)
87 * There is a performance advantage if @a == *rr@.
88 */
89
90extern void gf_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
91
f4535c64 92/* --- @gf_exp@ --- *
93 *
94 * Arguments: @mp *d@ = fake destination
95 * @mp *a@ = base
96 * @mp *e@ = exponent
97 *
98 * Returns: Result, %$a^e$%.
99 */
100
101extern mp *gf_exp(mp */*d*/, mp */*a*/, mp */*e*/);
102
432c4e18 103/* --- @gf_irreduciblep@ --- *
104 *
105 * Arguments: @mp *f@ = a polynomial
106 *
107 * Returns: Nonzero if the polynomial is irreducible; otherwise zero.
108 */
109
110extern int gf_irreduciblep(mp */*f*/);
111
ceb3f0c0 112/* --- @gf_gcd@ --- *
113 *
114 * Arguments: @mp **gcd, **xx, **yy@ = where to write the results
115 * @mp *a, *b@ = sources (must be nonzero)
116 *
117 *
118 * Returns: ---
119 *
120 * Use: Calculates @gcd(a, b)@, and two numbers @x@ and @y@ such that
121 * @ax + by = gcd(a, b)@. This is useful for computing modular
122 * inverses.
123 */
124
125extern void gf_gcd(mp **/*gcd*/, mp **/*xx*/, mp **/*yy*/,
126 mp */*a*/, mp */*b*/);
127
b817bfc6 128/* -- @gf_modinv@ --- *
129 *
130 * Arguments: @mp *d@ = destination
131 * @mp *x@ = argument
132 * @mp *p@ = modulus
133 *
134 * Returns: The inverse %$x^{-1} \bmod p$%.
135 *
136 * Use: Computes a modular inverse, the catch being that the
137 * arguments and results are binary polynomials. An assertion
138 * fails if %$p$% has no inverse.
139 */
140
141extern mp *gf_modinv(mp */*d*/, mp */*x*/, mp */*p*/);
142
ceb3f0c0 143/*----- That's all, folks -------------------------------------------------*/
144
145#ifdef __cplusplus
146 }
147#endif
148
149#endif