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