chiark / gitweb /
math/group-parse.c (group-parse): Parse binary-group descriptions.
[catacomb] / math / rho.h
CommitLineData
f41f820e 1/* -*-c-*-
f41f820e 2 *
3 * Pollard's rho algorithm for discrete logs
4 *
5 * (c) 2000 Straylight/Edgeware
6 */
7
45c0fd36 8/*----- Licensing notice --------------------------------------------------*
f41f820e 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 *
f41f820e 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 *
f41f820e 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
f41f820e 28#ifndef CATACOMB_RHO_H
29#define CATACOMB_RHO_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/*----- Data structures ---------------------------------------------------*/
42
43/* --- The group operations table --- */
44
45typedef struct rho_ops {
46 void (*sqr)(void *x, void *c);
47 void (*mul)(void *x, void *y, void *c);
48 int (*eq)(void *x, void *y);
49 int (*split)(void *x);
50 void (*drop)(void *x);
51} rho_ops;
52
53/* --- The Pollard's rho context structure --- */
54
55typedef struct rho_ctx {
4e66da02 56 const rho_ops *ops; /* Group operations table */
f41f820e 57 void *c; /* Context for group operations */
58 void *g, *a; /* Generator and argument for log */
59 mp *n; /* Cyclic group order */
60} rho_ctx;
61
62/*----- Functions provided ------------------------------------------------*/
63
64/* --- @rho@ --- *
65 *
66 * Arguments: @rho_ctx *cc@ = pointer to the context structure
67 * @void *x, *y@ = two (equal) base values (try 1)
68 * @mp *a, *b@ = logs of %$x$% (see below)
69 *
70 * Returns: The discrete logarithm %$\log_g a$%, or null if the algorithm
71 * failed. (This is unlikely, though possible.)
72 *
73 * Use: Uses Pollard's rho algorithm to compute discrete logs in the
74 * group %$G$% generated by %$g$%.
75 *
76 * The algorithm works by finding a cycle in a pseudo-random
77 * walk. The function @ops->split@ should return an element
78 * from %$\{\,0, 1, 2\,\}$% according to its argument, in order
79 * to determine the walk. At each step in the walk, we know a
80 * group element %$x \in G$% together with its representation as
81 * a product of powers of %$g$% and $%a$% (i.e., we know that
82 * %$x = g^\alpha a^\beta$% for some %$\alpha$%, %$\beta$%).
83 *
84 * Locating a cycle gives us a collision
85 *
86 * %$g^{\alpha} a^{\beta} = g^{\alpha'} a^{\beta'}$%
87 *
88 * Taking logs of both sides (to base %$g$%) gives us that
89 *
90 * %$\log a\equiv\frac{\alpha-\alpha'}{\beta'-\beta}\bmod{n}$%
91 *
92 * Good initial values are %$x = y = 1$% (the multiplicative
93 * identity of %$G$%) and %$\alpha\equiv\beta\equiv0\bmod{n}$%.
94 * If that doesn't work then start choosing more `interesting'
95 * values.
96 *
97 * Note that the algorithm requires minimal space but
98 * %$O(\sqrt{n})$% time. Don't do this on large groups,
99 * particularly if you can find a decent factor base.
100 *
101 * Finally, note that this function will free the input values
102 * when it's finished with them. This probably isn't a great
103 * problem.
104 */
105
106extern mp *rho(rho_ctx */*cc*/, void */*x*/, void */*y*/,
107 mp */*a*/, mp */*b*/);
108
109/* --- @rho_prime@ --- *
110 *
111 * Arguments: @mp *g@ = generator for the group
112 * @mp *a@ = value to find the logarithm of
113 * @mp *n@ = order of the group
114 * @mp *p@ = prime size of the underlying prime field
115 *
116 * Returns: The discrete logarithm %$\log_g a$%.
117 *
118 * Use: Computes discrete logarithms in a subgroup of a prime field.
119 */
120
121extern mp *rho_prime(mp */*g*/, mp */*a*/, mp */*n*/, mp */*p*/);
122
123/*----- That's all, folks -------------------------------------------------*/
124
125#ifdef __cplusplus
126 }
127#endif
128
129#endif