final_expo.c 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126
  1. /*
  2. * File: dclxvi-20130329/final_expo.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. #include <stdio.h>
  7. #include "final_expo.h"
  8. #include "fpe.h"
  9. extern const scalar_t bn_u;
  10. extern const scalar_t bn_v_scalar;
  11. extern const unsigned long bn_u_bitsize;
  12. static void fp12e_powv_special_square(fp12e_t rop, const fp12e_t op)
  13. {
  14. fp12e_t tmp0, tmp1, tmp2;
  15. //XXX Implement
  16. fp12e_special_square_finexp(tmp0,op);
  17. fp12e_special_square_finexp(tmp0,tmp0);
  18. fp12e_special_square_finexp(tmp0,tmp0); // t0 = op^8
  19. fp12e_special_square_finexp(tmp1,tmp0);
  20. fp12e_special_square_finexp(tmp1,tmp1);
  21. fp12e_special_square_finexp(tmp1,tmp1); // t1 = op^64
  22. fp12e_conjugate(tmp2, tmp0); // t2 = op^-8
  23. fp12e_mul(tmp2,tmp2,op); // t2 = op^-7
  24. fp12e_mul(tmp2,tmp2,tmp1); // tmp2 = op^57
  25. fp12e_special_square_finexp(tmp2,tmp2);
  26. fp12e_special_square_finexp(tmp2,tmp2);
  27. fp12e_special_square_finexp(tmp2,tmp2);
  28. fp12e_special_square_finexp(tmp2,tmp2);
  29. fp12e_special_square_finexp(tmp2,tmp2);
  30. fp12e_special_square_finexp(tmp2,tmp2);
  31. fp12e_special_square_finexp(tmp2,tmp2); // tmp2 = op^(2^7*57) = op^7296
  32. fp12e_mul(tmp2,tmp2,op); // tmp2 = op^7297
  33. fp12e_special_square_finexp(tmp2,tmp2);
  34. fp12e_special_square_finexp(tmp2,tmp2);
  35. fp12e_special_square_finexp(tmp2,tmp2);
  36. fp12e_special_square_finexp(tmp2,tmp2);
  37. fp12e_special_square_finexp(tmp2,tmp2);
  38. fp12e_special_square_finexp(tmp2,tmp2);
  39. fp12e_special_square_finexp(tmp2,tmp2);
  40. fp12e_special_square_finexp(tmp2,tmp2); // tmp2 = op^(7297*256) = op^1868032
  41. fp12e_mul(rop,tmp2,op); // rop = op^v
  42. }
  43. static void fp12e_powu_special_square(fp12e_t rop, const fp12e_t op)
  44. {
  45. fp12e_powv_special_square(rop, op);
  46. fp12e_powv_special_square(rop, rop);
  47. fp12e_powv_special_square(rop, rop);
  48. }
  49. void final_expo(fp12e_t rop)
  50. {
  51. /* This all has to change to support scalar_t instead of mpz_t */
  52. // First part: (p^6 - 1)
  53. fp12e_t dummy1, dummy2, fp, fp2, fp3, fu, fu2, fu3, fu2p, fu3p, y0, y1, y2, y3, y4, y5, y6, t0, t1;
  54. fp12e_set(dummy1, rop);
  55. // This is exactly the p^6-Frobenius action:
  56. fp6e_neg(rop->m_a, rop->m_a);
  57. fp12e_invert(dummy2, dummy1);
  58. fp12e_mul(rop, rop, dummy2);
  59. // After this point, rop has norm 1, so we can use
  60. // special squaring and exponentiation.
  61. // Second part: (p^2 + 1)
  62. fp12e_set(dummy1, rop);
  63. fp12e_frobenius_p2(rop, rop);
  64. fp12e_mul(rop, rop, dummy1);
  65. /* Hard part */
  66. fp12e_frobenius_p(fp, rop);
  67. fp12e_frobenius_p2(fp2, rop);
  68. fp12e_frobenius_p(fp3, fp2);
  69. fp12e_powu_special_square(fu, rop);
  70. fp12e_powu_special_square(fu2, fu);
  71. fp12e_powu_special_square(fu3, fu2);
  72. fp12e_frobenius_p(y3, fu);
  73. fp12e_frobenius_p(fu2p, fu2);
  74. fp12e_frobenius_p(fu3p, fu3);
  75. fp12e_frobenius_p2(y2,fu2);
  76. fp12e_mul(y0, fp, fp2);
  77. fp12e_mul(y0, y0, fp3);
  78. fp12e_conjugate(y1, rop);
  79. fp12e_conjugate(y5, fu2);
  80. fp12e_conjugate(y3, y3);
  81. fp12e_mul(y4, fu, fu2p);
  82. fp12e_conjugate(y4, y4);
  83. fp12e_mul(y6, fu3, fu3p);
  84. fp12e_conjugate(y6, y6);
  85. //t0 := fp12square(y6);
  86. fp12e_special_square_finexp(t0, y6);
  87. //t0 := t0*y4;
  88. fp12e_mul(t0, t0, y4);
  89. //t0 := t0*y5;
  90. fp12e_mul(t0, t0, y5);
  91. //t1 := y3*y5;
  92. fp12e_mul(t1, y3, y5);
  93. //t1 := t1*t0;
  94. fp12e_mul(t1, t1, t0);
  95. //t0 := t0*y2;
  96. fp12e_mul(t0, t0, y2);
  97. //t1 := t1^2;
  98. fp12e_special_square_finexp(t1, t1);
  99. //t1 := t1*t0;
  100. fp12e_mul(t1, t1, t0);
  101. //t1 := t1^2;
  102. fp12e_special_square_finexp(t1, t1);
  103. //t0 := t1*y1;
  104. fp12e_mul(t0, t1, y1);
  105. //t1 := t1*y0;
  106. fp12e_mul(t1, t1, y0);
  107. //t0 := t0^2;
  108. fp12e_special_square_finexp(t0, t0);
  109. //t0 := t0*t1;
  110. fp12e_mul(rop, t0, t1);
  111. }