src/.svn/text-base/testcurve.C.svn-base

   1 /* Test */
   2 /* Note that because we have a static g2hcurve member s_hcurve in the
   3 divisor class and this memeber may result in chaos when we swith moduli,
   4 we require that there is only one modulus per process
   5 */
   6
   7 #include <g2hec_nsfieldtype.h>
   8 #include <assert.h>
   9 #include <g2hec_Genus2_ops.h>
  10 #include <g2hec_nsdebug.h>
  11
  12 #undef MAX_STRING_LEN
  13 #define MAX_STRING_LEN 300
  14
  15 NS_G2_CLIENT
  16
  17 static void compare(const divisor& div, const divisor& divc, string ops);
  18
  19 int main()
  20 {
  21   /* Set PRNG seed */
  22   SetSeed(to_ZZ(19800729));
  23
  24   char p[MAX_STRING_LEN], exp[MAX_STRING_LEN];
  25
  26   cout << "Please choose your modulus p (up to "
  27 << MAX_STRING_LEN << " decimal digits):" << endl;
  28   cout << "p = ";
  29   cin.getline(p, MAX_STRING_LEN);
  30
  31   ZZ n; // For scalar multiplication
  32
  33    field_t::init(to_ZZ(p)); // define GF(p)
  34
  35    poly_t f, h, u, v;
  36
  37    g2hcurve curve;
  38
  39    divisor div, divc, div1, div2;
  40
  41    random(f, 6);
  42    SetCoeff(f, 5, 1); // Make monic of degree 5
  43
  44    random(h, 3);
  45
  46    cout << endl;
  47
  48    /*****************************************\
  49       Test curve
  50    \*****************************************/
  51    cout << "The underlying finite field is GF(" << p << ")." << endl;
  52
  53    cout << "\t*** Test g2hcurve ***" << endl;
  54
  55    /* Valid curve 1 generated by g2hcurve::random() */
  56    cout << "- Valid curve 1 -" << endl;
  57
  58    /* Test g2hcurve::random */
  59
  60    cout << "\t*** Test random curve ***" << endl;
  61
  62    curve.random();
  63
  64    assert(curve.is_valid_curve());
  65    cout << "Checking valid curve...OK" << endl;
  66
  67 #if DEBUG_LEVEL > 1
  68    /* Valid curve */
  69    cout << curve << endl;
  70
  71    /* Test g2hcurve::operator<< */
  72    cout << curve << endl;
  73 #endif
  74
  75    /* Another valid curve with h(x) = 0. Assume char is not 2 */
  76    cout << "- Valid curve 2 - " << endl;
  77
  78    do {
  79      random(f, 6); // deg(f) < 6
  80      SetCoeff(f, 5, 1); // f5 = 1;
  81    } while (!DetIrredTest(f));
  82
  83    curve.set_f(f);
  84
  85    clear(h); // h = 0
  86    curve.set_h(h);
  87    curve.update();
  88
  89    assert(curve.is_valid_curve());
  90    cout << "Checking valid curve (h = 0)...OK" << endl;
  91
  92 #if DEBUG_LEVEL > 1
  93    cout << curve << endl;
  94 #endif
  95
  96    /* Test invalid curve: not genus 2 */
  97    cout << "- Invalid curve 1: not genus 2 -" << endl;
  98
  99    NTL_NNS random(f, 5); // degree < 5
 100    MakeMonic(f);
 101    curve.set_f(f);
 102    curve.update();
 103
 104    assert(!curve.is_valid_curve());
 105    cout << "Checking invalid curve: not genus 2...OK" << endl;
 106
 107 #if DEBUG_LEVEL > 1
 108    cout << curve << endl;
 109 #endif
 110
 111    /* Test invalid curve: singular */
 112    cout << "- Invalid curve 2: singular -" << endl;
 113
 114    set(f);
 115    SetCoeff(f, 2, 1);
 116    SetCoeff(f, 1, 2); // f = x^2 + 2x + 1 = (x + 1)^2
 117    clear(h); // h = 0
 118
 119    curve.set_f(f);
 120    curve.set_h(h);
 121    curve.update();
 122
 123    assert(!curve.is_valid_curve());
 124    cout << "Checking invalid curve: singular...OK" << endl;
 125
 126 #if DEBUG_LEVEL > 1
 127    cout << curve << endl;
 128 #endif
 129
 130    /* Test invalid curve: f(x) not monic */
 131    cout << "- Invalid curve 3: f(x) not monic -" << endl;
 132
 133    SetCoeff(f, 5, 2);
 134
 135    curve.set_f(f);
 136    curve.update();
 137
 138    assert(!curve.is_valid_curve());
 139    cout << "Checking invalid curve: non-monic f(x)...OK" << endl;
 140
 141 #if DEBUG_LEVEL > 1
 142    cout << curve << endl;
 143 #endif
 144
 145    /*****************************************\
 146       Test divisor basics
 147    \*****************************************/
 148
 149    cout << "\t*** Test divisor routines ***" << endl;
 150
 151    curve.random(); // Set curve valid
 152
 153    /* Valid divisor generated by divisor::random() */
 154    cout << "\t*** Test random divisor ***" << endl;
 155
 156    div.set_curve(curve); // Set to valid curve
 157
 158    div.update();
 159
 160    div.random();
 161
 162    assert(div.is_valid_divisor());
 163    cout << "Checking random divisor...OK" << endl;
 164
 165 #if DEBUG_LEVEL > 1
 166    cout << div << endl;
 167 #endif
 168
 169    cout << "\t*** Test invalid divisor ***" << endl;
 170
 171    cout << "- Invalid divisor 1: invalid curve -" << endl;
 172
 173    /* Invalid divisor: invalid curve is a checked runtime error */
 174    cout <<
 175 "Invalid curve is a checked runtime error for all divisor arithmetic ops"
 176         << endl << endl;
 177
 178    /* Invalid divisor: invalid upoly */
 179
 180    cout << "- Invalid divisor 2: invalid upoly -" << endl;
 181
 182    SetCoeff(u, genus + 1, 1);  // deg(u) = 3
 183    div.set_upoly(u);
 184    div.update();
 185
 186    assert(!div.is_valid_divisor());
 187    cout << "Checking invalid divisor: invalid u(x)...OK" << endl;
 188
 189 #if DEBUG_LEVEL > 1
 190    cout << div << endl;
 191 #endif
 192
 193
 194    /* Invliad divisor: invalid vpoly */
 195    cout << "- Invalid divisor 3: invalid vpoly -" << endl;
 196
 197
 198    // Test divisor::set_unit, divisor::is_unit()
 199    cout << "    - Unit divisor -" << endl;
 200
 201    div.set_unit();
 202
 203    assert(div.is_unit());
 204    cout << "Checking unit divisor...OK" << endl;
 205
 206 #if DEBUG_LEVEL > 1
 207    cout << div << endl;
 208 #endif
 209
 210    /* Invalid vpoly */
 211    div.random();  // Valid divisor
 212
 213    cout << "    - vpoly is set to invalid -" << endl;
 214
 215    random(v, genus + 1);
 216    SetCoeff(v, 2, 1); // deg(v) = 1
 217    div.set_vpoly(v);
 218    div.update();
 219
 220    assert(!div.is_valid_divisor());
 221    cout << "Checking invalid divisor: invalid v(x)...OK" << endl;
 222
 223 #if DEBUG_LEVEL > 1
 224    cout << div << endl;
 225 #endif
 226
 227    /*****************************************\
 228       Test divisor arithmetic
 229    \*****************************************/
 230
 231    /* Test divisor arithmeitc:
 232       divisor addition, doubling and scalar multiplication are tested.
 233       Results return from add() and add_cantor() are compared to test
 234       correctness. Some results can also be compared to the results
 235       generated by the CAS MAGMA */
 236
 237    cout << "\t*** Test divisor arithmetic operations ***" << endl;
 238
 239    /* Test Divisor negation */
 240    cout << "\t*** Test negation ***" << endl;
 241    div1.random();
 242    dnegate(div2, div1);
 243
 244    assert(div2.is_valid_divisor());
 245    cout << "Checking divisor negation...OK" << endl;
 246
 247 #if DEBUG_LEVEL > 1
 248    cout << "div1: " << endl;
 249    cout << div1 << endl;
 250
 251    cout << "div2 = -div1:" << endl;
 252    cout << div2 << endl;
 253 #endif
 254
 255    div = div1 + div2;
 256
 257    assert(div.is_unit());
 258    cout << "This test should return a unit divisor...OK" << endl;
 259
 260 #if DEBUG_LEVEL > 1
 261    cout << "div1 + div2: " << endl;
 262    cout << div << endl;
 263 #endif
 264
 265    /* Test divisor addition */
 266    cout << "\t*** Test addition ***" << endl;
 267
 268    /* deg 2 + deg 2 */
 269    cout << "- Addition: deg 2 + deg 2 -" << endl;
 270
 271    div1.random();
 272
 273    do {
 274      div2.random();
 275    } while (div1 == div2); // Choose diffrent div2
 276
 277 #if DEBUG_LEVEL > 1
 278    cout << "Random div1: " << endl;
 279    cout << div1 << endl;
 280    cout << "Random div2: " << endl;
 281    cout << div2 << endl;
 282 #endif
 283
 284    if (add_cantor(divc, div1, div2))
 285      cout << "divc = div1 + div2: add_cantor()" << endl;
 286
 287 #if (DEBUG_LEVEL > 1)
 288    cout << "divc : " << endl;
 289    cout << divc << endl;
 290 #endif
 291
 292    if (add(div, div1, div2))
 293      cout << "div = div1 + div2: add()" << endl;
 294
 295    compare(div, divc, "Addtion(2+2)");
 296
 297    /* deg 2 + deg 1 */
 298    cout << "- Addition: deg 2 + deg 1 -" << endl;
 299
 300    div1.random(); // degree 2
 301    div2.random(DEGREE_1);// degree 1
 302
 303 #if DEBUG_LEVEL > 1
 304    cout << "Random div1: " << endl;
 305    cout << div1 << endl;
 306    cout << "Random div2: " << endl;
 307    cout << div2 << endl;
 308 #endif
 309
 310    if (add_cantor(divc, div1, div2))
 311      cout << "divc = div1 + div2: add_cantor()" << endl;
 312
 313    if (add(div, div1, div2))
 314      cout << "div = div1 + div2: add()" << endl;
 315
 316    cout << endl;
 317
 318    compare(div, divc, "Addition(2+1)");
 319
 320    /* deg 1 + deg 1 */
 321    cout << "- Addition: deg 1 + deg 1 -" << endl;
 322
 323    div1.random(DEGREE_1);
 324    do {
 325      div2.random(DEGREE_1);
 326    } while (div1 == div2);
 327
 328 #if DEBUG_LEVEL > 1
 329    cout << "Random div1: " << endl;
 330    cout << div1 << endl;
 331    cout << "Random div2: " << endl;
 332    cout << div2 << endl;
 333 #endif
 334
 335    if (add_cantor(divc, div1, div2))
 336      cout << "divc = div1 + div2: add_cantor()" << endl;
 337
 338    if (add(div, div1, div2))
 339      cout << "div = div1 + div2: add()" << endl;
 340    compare(div, divc, "Addition(1+1)");
 341
 342    /* deg 2 + unit */
 343    cout << "- Addition: deg 2 + unit divisor -" << endl;
 344
 345    div1.random();
 346    div2.set_unit();
 347
 348 #if DEBUG_LEVEL > 1
 349    cout << "Random div1: " << endl;
 350    cout << div1 << endl;
 351    cout << "Unit div2: " << endl;
 352    cout << div2 << endl;
 353 #endif
 354
 355    if (add_cantor(divc, div1, div2))
 356      cout << "divc = div1 + div2: add_cantor()" << endl;
 357
 358    if (add(div, div1, div2))
 359      cout << "div = div1 + div2: add()" << endl;
 360
 361    compare(div, divc, "Addtion(2+0)");
 362
 363    assert(div==div1);
 364    cout << "Checking adding unit divisor...OK" << endl;
 365
 366    /* unit + unit */
 367    cout << "- Addition: unit divisor + unit divisor -" << endl;
 368
 369    div1.set_unit();
 370    div2.set_unit();
 371
 372 #if DEBUG_LEVEL > 1
 373    cout << "Unit div1 & div2: " << endl;
 374    cout << div1 << endl;
 375 #endif
 376
 377    if (add_cantor(divc, div1, div2))
 378      cout << "divc = div1 + div2: add_cantor()" << endl;
 379
 380    if (add(div, div1, div2))
 381      cout << "div = div1 + div2: add()" << endl;
 382
 383    compare(div, divc, "Addition(0+0)");
 384
 385    assert(div==div1);
 386    cout << "Result should be unit...OK" << endl;
 387
 388    /* Test commutativity */
 389    div.random();
 390    div1.random();
 391    div2.random();
 392
 393    cout << "\t*** Test commutativity and associativity ***" << endl;
 394    assert( (div + div1) == (div1 + div));
 395
 396    cout << "...Commutativity holds" << endl;
 397
 398    cout << "\t*** Test associativity ***" << endl;
 399    assert( ((div + div1) + div2) == (div + (div1 + div2)) );
 400
 401    cout << "...Associativity holds" << endl;
 402
 403    /* Test divisor doubling */
 404    cout << "\t*** Test doubling ***" << endl;
 405
 406    /* [2]* deg_2 */
 407    cout << "- Doubling: deg 2 -" << endl;
 408
 409    div1.random();
 410
 411 #if DEBUG_LEVEL > 1
 412    cout << "Random div1: " << endl;
 413    cout << div1 << endl;
 414 #endif
 415
 416    if (add_cantor(divc, div1, div1))
 417      cout << "divc = [2]*div1: add_cantor()" << endl;
 418
 419    if (add(div, div1, div1))
 420      cout << "div =[2]*div1: add()" << endl;
 421
 422    compare(div, divc, "Doubling([2]*2)");
 423
 424    /* [2]* deg_1 */
 425    cout << "- Doubling: deg 1 -" << endl;
 426
 427    div1.random(DEGREE_1);
 428
 429 #if DEBUG_LEVEL > 1
 430    cout << "Random div1: " << endl;
 431    cout << div1 << endl;
 432 #endif
 433
 434    if (add_cantor(divc, div1, div1))
 435      cout << "divc = [2]*div1: add_cantor()" << endl;
 436
 437    if (add(div, div1, div1))
 438      cout << "div =[2]*div1: add()" << endl;
 439
 440    compare(div, divc, "Doubling([2]*1)");
 441
 442    /* Test divisor subtraction */
 443    cout << "\t*** Test subtraction ***" << endl;
 444
 445    div1.random();
 446    div2.random();
 447
 448    div = div1 - div2;
 449
 450 #if DEBUG_LEVEL > 1
 451    cout << "Random div1: " << endl;
 452    cout << div1 << endl;
 453
 454    cout << "Random div2: " << endl;
 455    cout << div2 << endl;
 456
 457    cout << "div1 - div2: " << endl;
 458    cout << div << endl;
 459 #endif
 460
 461    assert(div.is_valid_divisor());
 462    cout << "Checking subtraction...OK" << endl;
 463
 464    /* Test scalar multiplication */
 465    cout << "\t*** Test scalar multiplication ***" << endl;
 466
 467   do {
 468    div.random();
 469
 470    assert(div.is_valid_divisor());
 471    cout << "Random base divisor generated" << endl;
 472
 473    cout << "Please choose exponent n (up to " << MAX_STRING_LEN
 474 << " decimal digits.  Input '.' to break): " << endl;
 475
 476    cin.getline(exp, MAX_STRING_LEN);
 477
 478    if (exp[0] == '.') break;
 479
 480    n = to_ZZ(exp);
 481
 482    cout << "Exponent n = " << n << endl;
 483
 484 #if DEBUG_LEVEL > 2
 485    cout << "div: " << endl;
 486    cout << div << endl;
 487 #endif
 488
 489    /* Operator* */
 490
 491    scalar_mul(div1, div, n, NULL);
 492
 493    assert(div1.is_valid_divisor());
 494    cout << "Checking scalar multiplication: square and multiply...OK" << endl;
 495
 496 #if DEBUG_LEVEL > 1
 497    cout << "[" << n << "]*div: SAM " << endl;
 498    cout << div1 << endl;
 499 #endif
 500
 501    scalar_mul(div2, div, n, NAF);
 502    assert(div2.is_valid_divisor());
 503    cout << "Checking scalar multiplication: non-adjacent form...OK" << endl;
 504
 505 #if DEBUG_LEVEL > 1
 506    cout << "[" << n << "]*div: NAF " << endl;
 507    cout << div2 << endl;
 508 #endif
 509
 510    scalar_mul(divc, div, n,  ML);
 511    assert(divc.is_valid_divisor());
 512    cout << "Checking scalar multiplication: Montgomery's ladder...OK" << endl;
 513
 514 #if DEBUG_LEVEL > 1
 515    cout << "[" << n << "]*div: ML " << endl;
 516    cout << divc << endl;
 517 #endif
 518
 519    assert(div1 == div2 && div2 == divc);
 520    cout << "Outcomes of three method should agree...OK" << endl;
 521
 522    /* Test operator* */
 523    cout << "- Test operator* -" << endl;
 524    assert( (divc == n*div) && (divc == div*n));
 525    cout << "Checking operator*...OK" << endl;
 526
 527   } while (1);
 528
 529    cout << "**************************************" << endl;
 530    cout << "  Test completed. Everything seems OK" << endl;
 531    cout << "**************************************" << endl;
 532
 533    return 0;
 534 }
 535
 536
 537 static void compare(const divisor& div, const divisor& divc, string ops)
 538 {
 539    if (divc == div ) {
 540      cout << ops << " results agree: div equals divc" << endl;
 541 #if DEBUG_LEVEL > 1
 542      cout << div << endl << endl;
 543 #endif
 544    } else {
 545      cout << ops << " arithemetic wrong" << endl;
 546      assert(0);
 547    }
 548
 549 }