2
0

bn_kron.c 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
  1. /*
  2. * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the OpenSSL license (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include "internal/cryptlib.h"
  10. #include "bn_lcl.h"
  11. /* least significant word */
  12. #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
  13. /* Returns -2 for errors because both -1 and 0 are valid results. */
  14. int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  15. {
  16. int i;
  17. int ret = -2; /* avoid 'uninitialized' warning */
  18. int err = 0;
  19. BIGNUM *A, *B, *tmp;
  20. /*-
  21. * In 'tab', only odd-indexed entries are relevant:
  22. * For any odd BIGNUM n,
  23. * tab[BN_lsw(n) & 7]
  24. * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
  25. * Note that the sign of n does not matter.
  26. */
  27. static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 };
  28. bn_check_top(a);
  29. bn_check_top(b);
  30. BN_CTX_start(ctx);
  31. A = BN_CTX_get(ctx);
  32. B = BN_CTX_get(ctx);
  33. if (B == NULL)
  34. goto end;
  35. err = !BN_copy(A, a);
  36. if (err)
  37. goto end;
  38. err = !BN_copy(B, b);
  39. if (err)
  40. goto end;
  41. /*
  42. * Kronecker symbol, implemented according to Henri Cohen,
  43. * "A Course in Computational Algebraic Number Theory"
  44. * (algorithm 1.4.10).
  45. */
  46. /* Cohen's step 1: */
  47. if (BN_is_zero(B)) {
  48. ret = BN_abs_is_word(A, 1);
  49. goto end;
  50. }
  51. /* Cohen's step 2: */
  52. if (!BN_is_odd(A) && !BN_is_odd(B)) {
  53. ret = 0;
  54. goto end;
  55. }
  56. /* now B is non-zero */
  57. i = 0;
  58. while (!BN_is_bit_set(B, i))
  59. i++;
  60. err = !BN_rshift(B, B, i);
  61. if (err)
  62. goto end;
  63. if (i & 1) {
  64. /* i is odd */
  65. /* (thus B was even, thus A must be odd!) */
  66. /* set 'ret' to $(-1)^{(A^2-1)/8}$ */
  67. ret = tab[BN_lsw(A) & 7];
  68. } else {
  69. /* i is even */
  70. ret = 1;
  71. }
  72. if (B->neg) {
  73. B->neg = 0;
  74. if (A->neg)
  75. ret = -ret;
  76. }
  77. /*
  78. * now B is positive and odd, so what remains to be done is to compute
  79. * the Jacobi symbol (A/B) and multiply it by 'ret'
  80. */
  81. while (1) {
  82. /* Cohen's step 3: */
  83. /* B is positive and odd */
  84. if (BN_is_zero(A)) {
  85. ret = BN_is_one(B) ? ret : 0;
  86. goto end;
  87. }
  88. /* now A is non-zero */
  89. i = 0;
  90. while (!BN_is_bit_set(A, i))
  91. i++;
  92. err = !BN_rshift(A, A, i);
  93. if (err)
  94. goto end;
  95. if (i & 1) {
  96. /* i is odd */
  97. /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */
  98. ret = ret * tab[BN_lsw(B) & 7];
  99. }
  100. /* Cohen's step 4: */
  101. /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */
  102. if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
  103. ret = -ret;
  104. /* (A, B) := (B mod |A|, |A|) */
  105. err = !BN_nnmod(B, B, A, ctx);
  106. if (err)
  107. goto end;
  108. tmp = A;
  109. A = B;
  110. B = tmp;
  111. tmp->neg = 0;
  112. }
  113. end:
  114. BN_CTX_end(ctx);
  115. if (err)
  116. return -2;
  117. else
  118. return ret;
  119. }