share/contrib/elliptic_curves/elliptic_curves.texi

   1 \input texinfo
   2
   3 @c -----------------------------------------------------------------------------
   4 @c NOTE: This template-standalone.texi shows how to create a texinfo file
   5 @c that yields a stand-alone elliptic_curves.info file.
   6 @c See template.texi for a texinfo file which is to be part of maxima.info.
   7
   8 @c NOTE: The content of this file was determined by tedious trial and error.
   9 @c My advice is to keep all elements of this template, from \input to @bye,
  10 @c otherwise you'll experience cryptic error messages, hair loss, etc.
  11
  12 @c makeinfo elliptic_curves.texi         to make .info
  13 @c texi2html elliptic_curves.texi        to make .html
  14 @c texi2pdf elliptic_curves.texi         to make .pdf
  15 @c -----------------------------------------------------------------------------
  16
  17 @setfilename elliptic_curves.info
  18 @settitle elliptic_curves
  19
  20 @ifinfo
  21 @macro var {expr}
  22 <\expr\>
  23 @end macro
  24 @end ifinfo
  25
  26 @dircategory Mathematics/Maxima
  27 @direntry
  28 * elliptic_curves: (maxima/elliptic_curves).           Maxima share package elliptic_curves: elliptic curves over prime fields.
  29 @end direntry
  30
  31 @node Top, Introduction to elliptic_curves, (dir), (dir)
  32 @top
  33 @menu
  34 * Introduction to elliptic_curves::
  35 * Definitions for elliptic_curves::
  36 * Function and variable index::
  37 @end menu
  38 @chapter elliptic_curves
  39
  40 @node Introduction to elliptic_curves, Definitions for elliptic_curves, Top, Top
  41 @section Introduction to elliptic_curves
  42
  43 @code{elliptic_curves} is a package for elliptic curves over prime fields
  44 and provides some basic functions like addition and multiplication of curve points
  45 given in affine coordinates. There are functions for computing point and group
  46 orders and the package also contains example curve parameters from SEC and BRAINPOOL.
  47
  48 The trace of Frobenius is computed via Shanks-Mestre or Schoof-Elkies-Atkin,
  49 where the database of precalculated modular polynomials is limited and the trace
  50 can only be computed up to 256 bit examples.
  51
  52 Example: Plot of an elliptic curve with balanced points.
  53
  54 @example
  55 (%i1) load("elliptic_curves")$
  56 (%i2) [p,a,b] : [13,-9,12]$
  57 (%i3) ec_set_curve(p,a,b)$
  58 (%i4) ord : p+1 - ec_trace();
  59 (%o4)                                  19
  60 (%i5) ec_point_p(pt : [5,1]);
  61 (%o5)                                 true
  62 (%i6) ec_point_order(pt,ord);
  63 (%o6)                                  19
  64 (%i7) ec_balanced : true$
  65 (%i8) L : makelist(ec_mult(i,pt), i,1,ord-1)$
  66 (%i9) plot2d([discrete, L],
  67         [style, points], [x,-7,7], [y,-7,7],
  68         [gnuplot_postamble,
  69           "set size square; set grid; set xtics 1; set ytics 1;"])$
  70 @c (%i9) plot2d([discrete, L], [gnuplot_term, dumb], [style, points])$
  71 @c
  72 @c                         y
  73 @c                           6 +-G-G----------------+
  74 @c                             |   +G +   G  + G +  |
  75 @c                             |          :         |
  76 @c                           4 |+         :        +|
  77 @c                             |      G   :         |
  78 @c                           2 |+         :G       +|
  79 @c                             |          :         |
  80 @c                             |          :      GG |
  81 @c                           0 |+..................+|
  82 @c                             |          :      GG |
  83 @c                             |          :         |
  84 @c                          -2 |+         :G       +|
  85 @c                             |      G   :         |
  86 @c                          -4 |+         :        +|
  87 @c                             |          :         |
  88 @c                             |   +G +   G  + G +  |
  89 @c                          -6 +-G-G----------------+
  90 @c                            -6  -4 -2   0  2   4  6
  91 @c                                       x
  92 @ifnotinfo
  93 @image{figures/ec_Z13,10cm}
  94 @end ifnotinfo
  95
  96 @end example
  97
  98 @code{elliptic_curves} contains some example parameters from SEC and BRAINPOOL.
  99
 100 Example: @code{secp112r2} has no prime order. The cofactor is 4: @code{ord = 4*n}.
 101
 102 @example
 103 (%i1) load("elliptic_curves")$
 104 (%i2) [[p,a,b],base_pt,n] : secp112r2$
 105 (%i3) ec_set_curve(p,a,b)$
 106 (%i4) ord : p+1 - ec_trace();
 107 (%o4)                   4451685225093714699870930859147564
 108 (%i5) ifactors(ord);
 109 (%o5)              [[2,2],[1112921306273428674967732714786891,1]]
 110 (%i6) n = ec_point_order(base_pt,ord);
 111 (%o6) 1112921306273428674967732714786891=1112921306273428674967732714786891
 112 @end example
 113
 114
 115 @node Definitions for elliptic_curves, Function and variable index, Introduction to elliptic_curves, Top
 116 @section Definitions for elliptic_curves
 117
 118 @c -----------------------------------------------------------------------------
 119 @c Maxima functions:
 120 @c ec_add, ec_log, ec_mult, ec_point_order, ec_point_p, ec_random,
 121 @c ec_set_curve, ec_trace, ec_twist_curve
 122 @c
 123 @c Option variables:
 124 @c ec_balanced, ec_sea_verbose
 125 @c -----------------------------------------------------------------------------
 126
 127 @deffn {Function} ec_add (@var{pt1}, @var{pt2})
 128
 129 Adds two points on the current elliptic curve.
 130 @code{ec_add} does not check if both points are indeed on the curve and will
 131 return erroneous results if they are not.
 132
 133 The following example also shows the point at infinity @code{ec_inf}.
 134
 135 @example
 136 (%i1) load("elliptic_curves")$
 137 (%i2) ec_set_curve(13,1,2)$
 138 (%i3) pt : [1,11]$
 139 (%i4) ec_add(pt,pt);
 140 (%o4)                              [12,0]
 141 (%i5) ec_add(pt,ec_inf);
 142 (%o5)                              [1,11]
 143 @end example
 144
 145 @end deffn
 146
 147 @c -----------------------------------------------------------------------------
 148
 149 @defvr {Variable} ec_balanced
 150 Default value: @code{false}
 151
 152 When @code{ec_balanced} is @code{true},
 153 a balanced modulus is applied when printing curve points.
 154 E.g. this allows to create a symmetric discrete plot.
 155
 156 @example
 157 (%i1) load("elliptic_curves")$
 158 (%i2) ec_balanced : true$
 159 (%i3) ec_set_curve(13,1,2)$
 160 (%i4) makelist(ec_mult(i, [1,11]), i,1,4);
 161 (%o4)                   [[1,-2],[-1,0],[1,2],ec_inf]
 162 @end example
 163
 164 @end defvr
 165
 166 @c -----------------------------------------------------------------------------
 167
 168 @deffn {Function} ec_log (@var{pt}, @var{gen})
 169
 170 Uses a simple baby-giant-algorithm to compute the discrete logarithm of @var{pt},
 171 i.e. it solves the equation @code{gen^x = pt} on the current elliptic curve.
 172 @var{gen} has to be a generator of the subgroup which contains @var{pt}.
 173 Otherwise @code{ec_log} returns @code{false}.
 174
 175 @code{ec_log} does not check if both points are indeed on the curve and will
 176 return erroneous results if they are not.
 177
 178 The algorithm is limited and prints an error if the characteristic exceeds
 179 an integer length of 36 bit.
 180
 181 @example
 182 (%i1) load("elliptic_curves")$
 183 (%i2) ec_set_curve(13,1,2)$
 184 (%i3) ord : p+1 - ec_trace();
 185 (%o3)                                12
 186 (%i4) gen : [2,5]$
 187 (%i5) makelist(ec_mult(i,gen), i,1,ec_point_order(gen,ord));
 188 (%o5)               [[2,5],[9,8],[12,0],[9,5],[2,8],ec_inf]
 189 (%i6) pt : [2,8]$
 190 (%i7) ec_log(pt,gen);
 191 (%o7)                                 5
 192 (%i8) pt : [1,2]$
 193 (%i9) ec_log(pt,gen);
 194 (%o9)                               false
 195 @end example
 196
 197 @end deffn
 198
 199 @c -----------------------------------------------------------------------------
 200
 201 @deffn {Function} ec_mult (@var{n}, @var{pt})
 202
 203 Returns @var{n} times the point @var{pt} of the elliptic curve, which was
 204 previously set by @code{ec_set_curve}. @code{ec_mult} does not check if the
 205 point is indeed on the curve and will return erroneous results if it is not.
 206
 207 @example
 208 (%i1) load("elliptic_curves")$
 209 (%i2) ec_set_curve(13,1,2)$
 210 (%i3) pt : [1,11]$
 211 (%i4) ec_mult(-1,pt);
 212 (%o4)                              [1,2]
 213 @end example
 214
 215 @end deffn
 216
 217 @c -----------------------------------------------------------------------------
 218
 219 @deffn {Function} ec_point_order (@var{pt}, @var{ord})
 220 @deffnx {Function} ec_point_order (@var{pt}, @var{ord}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]])
 221
 222 Computes the point order of @var{pt} on the current elliptic curve as a factor
 223 of the known group order @var{ord} of the curve.
 224
 225 If the factorization of @var{ord} is known, it can be passed as an optional argument.
 226
 227 @example
 228 (%i1) load("elliptic_curves")$
 229 (%i2) ec_set_curve(p:13, 1,2)$
 230 (%i3) ord : p+1 - ec_trace();
 231 (%o3)                                12
 232 (%i4) fs_ord : ifactors(ord);
 233 (%o4)                           [[2,2],[3,1]]
 234 (%i5) pt : [1,11]$
 235 (%i6) ec_point_order(pt,ord,fs_ord);
 236 (%o6)                                 4
 237 (%i7) ec_mult(4,pt);
 238 (%o7)                              ec_inf
 239 @end example
 240
 241 @end deffn
 242
 243 @c -----------------------------------------------------------------------------
 244
 245 @deffn {Function} ec_point_p (@var{pt})
 246
 247 Checks if @var{pt} is a point on the current elliptic curve, where the point at
 248 infinity @code{ec_inf} is regarded as a point on the curve.
 249
 250 @end deffn
 251
 252 @c -----------------------------------------------------------------------------
 253
 254 @deffn {Function} ec_random ()
 255
 256 Returns a non-infinite random point on the current elliptic curve.
 257
 258 @end deffn
 259
 260 @c -----------------------------------------------------------------------------
 261
 262 @defvr {Variable} ec_sea_verbose
 263 Default value: @code{false}
 264
 265 When @code{ec_sea_verbose} is @code{true} and the integer length of the
 266 characteristic @var{p} is larger than 56,
 267 @code{ec_trace} will print some information about the splitting type of the
 268 modular polynomial and the resulting possible traces.
 269
 270 @example
 271 (%i1) load("elliptic_curves")$
 272 (%i2) ec_sea_verbose : true$
 273 (%i3) apply(ec_set_curve, secp112r1[1])$
 274 (%i4) ec_trace();
 275 mod 2 : [2, [1]]
 276 atkin : [3, [1,2]]
 277 atkin : [5, [0]]
 278 elkies: [49, [47]]
 279 atkin : [11, [4,5,6,7]]
 280 atkin : [13, [0]]
 281 elkies: [17, [3]]
 282 atkin : [19, [2,4,6,9,10,13,15,17]]
 283 elkies: [23, [4]]
 284 atkin : [29, [10,19]]
 285 elkies: [31, [15]]
 286 elkies: [37, [2]]
 287 elkies: [41, [36]]
 288 atkin : [43, [1,4,6,7,8,10,14,17,18,20,23,25,26,29,33,35,36,37,39,42]]
 289 atkin : [47, [1,4,5,8,14,16,19,23,24,28,31,33,39,42,43,46]]
 290 (%o4)                        -4407293269000505
 291 @end example
 292
 293 @end defvr
 294
 295 @c -----------------------------------------------------------------------------
 296
 297 @deffn {Function} ec_set_curve (@var{p}, @var{a}, @var{b})
 298
 299 Defines an elliptic curve (@var{a},@var{b}),
 300 where @var{a} and @var{b} are elements of the prime field @code{F}@var{p} and
 301 correspond to the Weierstrass equation @code{y^2 = x^3 + @var{a}*x + @var{b}}.
 302 @var{a}, @var{b} and @var{p} are stored as global parameters and all elliptic
 303 curve functions refer to them.
 304
 305 @code{ec_set_curve} returns @code{true} if the curve is not singular and
 306 @code{false} otherwise. In this case no parameters are set.
 307
 308 The following example shows the definition of the curve @code{secp112r1} and the
 309 computation of its group order.
 310
 311 @example
 312 (%i1) load("elliptic_curves")$
 313 (%i2) p : 4451685225093714772084598273548427$
 314 (%i3) a : -3$
 315 (%i4) b : 2061118396808653202902996166388514$
 316 (%i5) ec_set_curve(p,a,b)$
 317 (%i6) ord : p + 1 - ec_trace();
 318 (%o6)                 4451685225093714776491891542548933
 319 @end example
 320
 321 @end deffn
 322
 323 @c -----------------------------------------------------------------------------
 324
 325 @deffn {Function} ec_trace ()
 326
 327 Returns the trace of Frobenius of the current elliptic curve.
 328 @code{ec_trace} uses the Shanks-Mestre algorithm for integer lengths up to 56 bit
 329 and the Schoof-Elkies-Atkin (SEA) algorithm otherwise. The database of modular
 330 polynomials is limited and @code{ec_trace} will not work for parameters much larger
 331 than 256 bit.
 332
 333 The following example uses the curve @code{secp128r1} from the file
 334 @code{curve_parameters.mac}.
 335
 336 @example
 337 (%i1) load("elliptic_curves")$
 338 (%i2) [p,a,b] : secp128r1[1]$
 339 (%i3) ec_set_curve(p,a,b)$
 340 (%i4) ord : p+1 - ec_trace();
 341 (%o4)              340282366762482138443322565580356624661
 342 (%i5) primep(ord);
 343 (%o5)                               true
 344 @end example
 345
 346 See also @code{ec_sea_verbose}.
 347
 348 @end deffn
 349
 350 @c -----------------------------------------------------------------------------
 351
 352 @deffn {Function} ec_twist_curve ()
 353
 354 Returns a list with a quadratic non-residue n of the given field and the
 355 parameters (a*n^2, b*n^3) of the twisted curve.
 356
 357 @example
 358 (%i1) load("elliptic_curves")$
 359 (%i2) ec_set_curve(p:13, 1,2)$
 360 (%i3) ord : p+1 - ec_trace();
 361 (%o3)                                12
 362 (%i4) [n,at,bt] : ec_twist_curve();
 363 (%o4)                              [2,4,3]
 364 (%i5) ec_set_curve(p, at,bt)$
 365 (%i6) ordt : p+1 - ec_trace();
 366 (%o6)                                16
 367 (%i7) is(ord + ordt = 2*p + 2);
 368 (%o7)                               true
 369 @end example
 370
 371 @end deffn
 372
 373 @c -----------------------------------------------------------------------------
 374
 375 @node Function and variable index,  , Definitions for elliptic_curves, Top
 376 @appendix Function and variable index
 377 @printindex fn
 378 @printindex vr
 379
 380 @bye