group.c 2.1 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
  1. #include "group.h"
  2. const char* p_str =
  3. "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  4. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  5. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  6. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  7. "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
  8. "505CAF";
  9. mpz_t p, q;
  10. const uint64_t gg = 11510609;
  11. void group_init()
  12. {
  13. mpz_init_set_str(p, p_str, 0);
  14. mpz_init(q);
  15. mpz_sub_ui(q, p, 1);
  16. mpz_divexact_ui(q, q, 2);
  17. }
  18. void group_clear()
  19. {
  20. mpz_clears(p, q, NULL);
  21. }
  22. void powmp_ui(mpz_t x, const mpz_t base, uint64_t exp)
  23. {
  24. mpz_t y;
  25. mpz_init_set_ui(y, 1);
  26. mpz_set(x, base);
  27. while (exp > 1) {
  28. if (exp & 1) mpz_mul_modp(y, x, y);
  29. mpz_mul_modp(x, x, x);
  30. exp >>= 1;
  31. }
  32. mpz_mul_modp(x, x, y);
  33. mpz_clear(y);
  34. }
  35. void mul_modp(mpz_t rop, mpz_t op1, mpz_t op2)
  36. {
  37. mp_limb_t z2[24+2];
  38. mp_limb_t z0[24+2];
  39. mp_limb_t z1[24+12]= {0};
  40. mp_limb_t z1f[12+1];
  41. mp_limb_t z1s[12+1];
  42. mp_limb_t z3[24];
  43. const mp_limb_t *op1_hi = PTR(op1) + 12;
  44. const mp_limb_t *op2_hi = PTR(op2) + 12;
  45. const mp_limb_t *op1_lo = PTR(op1);
  46. const mp_limb_t *op2_lo = PTR(op2);
  47. const mp_limb_t *z1_hi = z1 + 12;
  48. const mp_limb_t *z1_lo = z1;
  49. mp_limb_t carry;
  50. /* make all operands of the same width */
  51. _mpz_realloc(rop, 24);
  52. _mpz_realloc(op1, 24);
  53. _mpz_realloc(op2, 24);
  54. SIZ(rop) = SIZ(op1) = SIZ(op2) = 24;
  55. mpn_mul_n(z2, op1_hi, op2_hi, 12);
  56. z2[24] = z2[25] = 0;
  57. mpn_mul_n(z0, op1_lo, op2_lo, 12);
  58. z0[24] = z0[25] = 0;
  59. carry = mpn_add_n(z1f, op1_lo, op1_hi, 12);
  60. z1f[12] = carry;
  61. carry = mpn_add_n(z1s, op2_lo, op2_hi, 12);
  62. z1s[12] = carry;
  63. mpn_mul_n(z1, z1f, z1s, 12+1);
  64. mpn_sub_n(z1, z1, z2, 24+2);
  65. mpn_sub_n(z1, z1, z0, 24+2);
  66. mpn_add_n(z3, z2, z1_hi, 24);
  67. carry = mpn_mul_1(PTR(rop), z3, 24, gg);
  68. carry += mpn_add_n(PTR(rop), PTR(rop), z0, 24);
  69. carry += mpn_add_n(PTR(rop)+12, PTR(rop)+12, z1_lo, 12);
  70. mpn_add_1(PTR(rop), PTR(rop), 24, carry*gg);
  71. MPN_NORMALIZE(PTR(rop), SIZ(rop));
  72. }