1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%%  trace_list.tex      Documentation
4%%
5%%  This file contains the documentation of the class trace_list.
6%%
7%%  Copyright   (c)   1998   by  LiDIA Group
8%%
9%%  Authors: Volker Mueller
10%%
11
12%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13
14\NAME
15
16\code{trace_list} \dotfill class for storing a list of \code{trace_mod}s
17
18
19%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20
21\ABSTRACT
22
23The class \code{trace_list} is used for storing information on the trace of the Frobenius
24endomorphism computed with the class \code{eco_prime} and stored in instances of the class
25\code{trace_mod}.  Moreover \code{trace_list} offers a Babystep Giantstep algorithm to find a
26candidate for the group order.
27
28
29%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
30
31\DESCRIPTION
32
33\code{trace_list} is a class for storing the information computed with the class
34\code{eco_prime}.  These information is stored in several instances of the class
35\code{trace_mod}.  Moreover there exist function to decide when enough information has been
36computed to start a combination step and to determine a candidate for the group order with a
37Babystep Giantstep type algorithm.
38
39The class stores a list of \code{trace_mod} which contain information about traces modulo
40primes.  In this list only these \code{trace_mod}s are stored, which do not contain the exact
41value of the trace modulo the corresponding prime $l$.  In addition to this list an instance of
42\code{trace_list} contains two variables $C_3$ and $M_3$, which hold integers such that the
43trace of Frobenius is congruent to $C_3$ modulo $M_3$.  Moreover some variable stores the size
44of the Hasse interval for the actual computation.
45
46After the combination step two more moduli are set.  The variables $M_1$, $M_2$ hold the moduli
47used for the Babystep, Giantstep list, respectively.  A description of the combination step can
48be found in the master thesis of Markus Maurer \cite{Maurer_Thesis:1994}.
49
50
51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
52
53\CONS
54
55\begin{fcode}{ct}{trace_list}{}
56  constructs an uninitialized instance.
57\end{fcode}
58
59\begin{fcode}{ct}{trace_list}{const bigint & $q$}
60  constructs an instance for a point computation over a field with $q$ elements, i.e. the size
61  of the Hasse interval is $4 \sqrt{q}$ in this case.
62\end{fcode}
63
64\begin{fcode}{dt}{~trace_list}{}
65\end{fcode}
66
67
68%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
69
70\ASGN
71
72Let $t$ be an instance of \code{trace_list}.
73
74\begin{fcode}{void}{$t$.clear}{}
75  deletes all internal data, except the size of the Hasse interval.
76\end{fcode}
77
78\begin{fcode}{void}{$t$.set_curve}{const elliptic_curve< gf_element > & $e$}
79  Initializes with curve $e$.
80\end{fcode}
81
82\begin{fcode}{static void}{set_info_mode}{int $i$ = 0}
83  set the internal info variable to $i$.  If this variable is not zero, then some information is
84  printed during the Babystep Giantstep algorithm; otherwise no output is done.  The default
85  value for the info variable is zero.
86\end{fcode}
87
88
89%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
90
91\ACCS
92
93Let $t$ be an instance of \code{trace_list}.
94
95\begin{cfcode}{bigint}{$t$.get_M1}{}
96  returns the modulus for the Babystep list.
97\end{cfcode}
98
99\begin{cfcode}{bigint}{$t$.get_M2}{}
100  returns the modulus for the Giantstep list.
101\end{cfcode}
102
103\begin{cfcode}{bigint}{$t$.get_M3}{}
104  returns the modulus for which we know the trace of Frobenius exact.
105\end{cfcode}
106
107\begin{cfcode}{bigint}{$t$.get_C3}{}
108  returns the trace of Frobenius modulo $C_3$.
109\end{cfcode}
110
111\begin{cfcode}{const sort_vector< trace_mod >}{$t$.get_list}{}
112  returns the list of \code{trace_mod}s stored internally.
113\end{cfcode}
114
115\begin{fcode}{bigint}{$t$.number_of_combinations}{}
116  returns the total number of possibilities which have to be checked.  If the product of the
117  three moduli is not bigger than the size of Hasse's interval, then $-1$ is returned.
118\end{fcode}
119
120
121%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
122
123\HIGH
124
125Let $t$ be an instance of \code{trace_list}.
126
127\begin{fcode}{bool}{$t$.append}{const trace_mod & $m$}
128  appends $m$ to the \code{trace_list} $t$.  Then it checks whether the number of possible
129  values is smaller than some predefined value and the product of all internal moduli is big
130  enough.  If these two conditions are fulfilled, then \TRUE is returned, otherwise \FALSE is
131  returned.
132\end{fcode}
133
134\begin{fcode}{bool}{$t$.split_baby_giant}{sort_vector< bigint > & $b$,
135    sort_vector< bigint > & $g$}%
136  sets $b$ to the list of Babystep indices, $g$ to the list of Giantstep indices and returns
137  \TRUE, if the number of possible candidates is smaller than some predefined bound.  Otherwise
138  both vectors are emptied and \FALSE is returned.
139\end{fcode}
140
141\begin{fcode}{bigint}{bg_algorithm}{const point< ff_element > & $P$,
142    sort_vector< bigint > & $b$, sort_vector< bigint > & $g$, const bigint & $q$}%
143  uses the two lists for a Babystep Giantstep algorithm to find a multiple of the order of the
144  point $P$ in the Hasse interval.  This value is returned.
145\end{fcode}
146
147\begin{fcode}{bigint}{bg_search_for_order}{}
148  Generates a random point $P$ and uses the trace information for a Babystep Giantstep algorithm
149  to find a multiple of the order of the point $P$ in the Hasse interval.  This value is
150  returned.
151\end{fcode}
152
153\begin{fcode}{bigint}{simple_search_for_order}{}
154  Generates a random point $P$, computes all possible traces, and checks for each trace
155  candidate, whether the corresping group order candidate is a multiple of the order of the
156  point $P$ in the Hasse interval.  This value is returned.
157\end{fcode}
158
159\begin{fcode}{bool}{baby_giant_lists_correct}{const bigint & $n$}
160  Uses the group order $n$ to verify, that the baby step and the giant step list is correct, in
161  the sense, that the correct trace can be found in the lists.
162\end{fcode}
163
164
165%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
166
167\IO
168
169The \code{istream} operator \code{>>} and the \code{ostream} operator \code{<<} are
170overloaded.
171
172
173%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
174
175\SEEALSO
176
177\SEE{eco_prime}, \SEE{trace_mod}.
178
179
180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
181
182\NOTES
183
184The Elliptic Curve Counting Package will change in future releases.  Then
185probably the interface of the class \code{trace_list} will also change.
186
187
188%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
189
190\AUTHOR
191
192Markus Maurer, Volker M\"uller.
193