From 50e735f9e5d220cdad7db690188b82a69ddcb39e Mon Sep 17 00:00:00 2001 From: Matt Caswell Date: Mon, 5 Jan 2015 11:30:03 +0000 Subject: Re-align some comments after running the reformat script. This should be a one off operation (subsequent invokation of the script should not move them) Reviewed-by: Tim Hudson --- crypto/bn/bn_add.c | 24 +++--- crypto/bn/bn_exp.c | 60 +++++++-------- crypto/bn/bn_gcd.c | 212 +++++++++++++++++++++++++-------------------------- crypto/bn/bn_mul.c | 90 +++++++++++----------- crypto/bn/bn_prime.c | 22 +++--- crypto/bn/bn_sqr.c | 22 +++--- crypto/bn/bn_sqrt.c | 70 ++++++++--------- 7 files changed, 250 insertions(+), 250 deletions(-) (limited to 'crypto/bn') diff --git a/crypto/bn/bn_add.c b/crypto/bn/bn_add.c index ccdcdd1d7c..f569a7efde 100644 --- a/crypto/bn/bn_add.c +++ b/crypto/bn/bn_add.c @@ -68,12 +68,12 @@ int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) bn_check_top(a); bn_check_top(b); - /*- - * a + b a+b - * a + -b a-b - * -a + b b-a - * -a + -b -(a+b) - */ + /*- + * a + b a+b + * a + -b a-b + * -a + b b-a + * -a + -b -(a+b) + */ if (a_neg ^ b->neg) { /* only one is negative */ if (a_neg) { @@ -260,12 +260,12 @@ int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) bn_check_top(a); bn_check_top(b); - /*- - * a - b a-b - * a - -b a+b - * -a - b -(a+b) - * -a - -b b-a - */ + /*- + * a - b a-b + * a - -b a+b + * -a - b -(a+b) + * -a - -b b-a + */ if (a->neg) { if (b->neg) { tmp = a; diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index eebcb96b55..28a9fd53bb 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -203,36 +203,36 @@ int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, bn_check_top(p); bn_check_top(m); - /*- - * For even modulus m = 2^k*m_odd, it might make sense to compute - * a^p mod m_odd and a^p mod 2^k separately (with Montgomery - * exponentiation for the odd part), using appropriate exponent - * reductions, and combine the results using the CRT. - * - * For now, we use Montgomery only if the modulus is odd; otherwise, - * exponentiation using the reciprocal-based quick remaindering - * algorithm is used. - * - * (Timing obtained with expspeed.c [computations a^p mod m - * where a, p, m are of the same length: 256, 512, 1024, 2048, - * 4096, 8192 bits], compared to the running time of the - * standard algorithm: - * - * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] - * 55 .. 77 % [UltraSparc processor, but - * debug-solaris-sparcv8-gcc conf.] - * - * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] - * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] - * - * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont - * at 2048 and more bits, but at 512 and 1024 bits, it was - * slower even than the standard algorithm! - * - * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] - * should be obtained when the new Montgomery reduction code - * has been integrated into OpenSSL.) - */ + /*- + * For even modulus m = 2^k*m_odd, it might make sense to compute + * a^p mod m_odd and a^p mod 2^k separately (with Montgomery + * exponentiation for the odd part), using appropriate exponent + * reductions, and combine the results using the CRT. + * + * For now, we use Montgomery only if the modulus is odd; otherwise, + * exponentiation using the reciprocal-based quick remaindering + * algorithm is used. + * + * (Timing obtained with expspeed.c [computations a^p mod m + * where a, p, m are of the same length: 256, 512, 1024, 2048, + * 4096, 8192 bits], compared to the running time of the + * standard algorithm: + * + * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] + * 55 .. 77 % [UltraSparc processor, but + * debug-solaris-sparcv8-gcc conf.] + * + * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] + * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] + * + * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont + * at 2048 and more bits, but at 512 and 1024 bits, it was + * slower even than the standard algorithm! + * + * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] + * should be obtained when the new Montgomery reduction code + * has been integrated into OpenSSL.) + */ #define MONT_MUL_MOD #define MONT_EXP_WORD diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c index 13432d09e7..9902e4eee9 100644 --- a/crypto/bn/bn_gcd.c +++ b/crypto/bn/bn_gcd.c @@ -283,13 +283,13 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, goto err; } sign = -1; - /*- - * From B = a mod |n|, A = |n| it follows that - * - * 0 <= B < A, - * -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|). - */ + /*- + * From B = a mod |n|, A = |n| it follows that + * + * 0 <= B < A, + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + */ if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) { /* @@ -301,12 +301,12 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, int shift; while (!BN_is_zero(B)) { - /*- - * 0 < B < |n|, - * 0 < A <= |n|, - * (1) -sign*X*a == B (mod |n|), - * (2) sign*Y*a == A (mod |n|) - */ + /*- + * 0 < B < |n|, + * 0 < A <= |n|, + * (1) -sign*X*a == B (mod |n|), + * (2) sign*Y*a == A (mod |n|) + */ /* * Now divide B by the maximum possible power of two in the @@ -352,18 +352,18 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, goto err; } - /*- - * We still have (1) and (2). - * Both A and B are odd. - * The following computations ensure that - * - * 0 <= B < |n|, - * 0 < A < |n|, - * (1) -sign*X*a == B (mod |n|), - * (2) sign*Y*a == A (mod |n|), - * - * and that either A or B is even in the next iteration. - */ + /*- + * We still have (1) and (2). + * Both A and B are odd. + * The following computations ensure that + * + * 0 <= B < |n|, + * 0 < A < |n|, + * (1) -sign*X*a == B (mod |n|), + * (2) sign*Y*a == A (mod |n|), + * + * and that either A or B is even in the next iteration. + */ if (BN_ucmp(B, A) >= 0) { /* -sign*(X + Y)*a == B - A (mod |n|) */ if (!BN_uadd(X, X, Y)) @@ -392,11 +392,11 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, while (!BN_is_zero(B)) { BIGNUM *tmp; - /*- - * 0 < B < A, - * (*) -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|) - */ + /*- + * 0 < B < A, + * (*) -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|) + */ /* (D, M) := (A/B, A%B) ... */ if (BN_num_bits(A) == BN_num_bits(B)) { @@ -443,12 +443,12 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, goto err; } - /*- - * Now - * A = D*B + M; - * thus we have - * (**) sign*Y*a == D*B + M (mod |n|). - */ + /*- + * Now + * A = D*B + M; + * thus we have + * (**) sign*Y*a == D*B + M (mod |n|). + */ tmp = A; /* keep the BIGNUM object, the value does not * matter */ @@ -458,25 +458,25 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, B = M; /* ... so we have 0 <= B < A again */ - /*- - * Since the former M is now B and the former B is now A, - * (**) translates into - * sign*Y*a == D*A + B (mod |n|), - * i.e. - * sign*Y*a - D*A == B (mod |n|). - * Similarly, (*) translates into - * -sign*X*a == A (mod |n|). - * - * Thus, - * sign*Y*a + D*sign*X*a == B (mod |n|), - * i.e. - * sign*(Y + D*X)*a == B (mod |n|). - * - * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at - * -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|). - * Note that X and Y stay non-negative all the time. - */ + /*- + * Since the former M is now B and the former B is now A, + * (**) translates into + * sign*Y*a == D*A + B (mod |n|), + * i.e. + * sign*Y*a - D*A == B (mod |n|). + * Similarly, (*) translates into + * -sign*X*a == A (mod |n|). + * + * Thus, + * sign*Y*a + D*sign*X*a == B (mod |n|), + * i.e. + * sign*(Y + D*X)*a == B (mod |n|). + * + * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + * Note that X and Y stay non-negative all the time. + */ /* * most of the time D is very small, so we can optimize tmp := @@ -513,13 +513,13 @@ BIGNUM *int_bn_mod_inverse(BIGNUM *in, } } - /*- - * The while loop (Euclid's algorithm) ends when - * A == gcd(a,n); - * we have - * sign*Y*a == A (mod |n|), - * where Y is non-negative. - */ + /*- + * The while loop (Euclid's algorithm) ends when + * A == gcd(a,n); + * we have + * sign*Y*a == A (mod |n|), + * where Y is non-negative. + */ if (sign < 0) { if (!BN_sub(Y, n, Y)) @@ -604,22 +604,22 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, goto err; } sign = -1; - /*- - * From B = a mod |n|, A = |n| it follows that - * - * 0 <= B < A, - * -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|). - */ + /*- + * From B = a mod |n|, A = |n| it follows that + * + * 0 <= B < A, + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + */ while (!BN_is_zero(B)) { BIGNUM *tmp; - /*- - * 0 < B < A, - * (*) -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|) - */ + /*- + * 0 < B < A, + * (*) -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|) + */ /* * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, @@ -632,12 +632,12 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, if (!BN_div(D, M, pA, B, ctx)) goto err; - /*- - * Now - * A = D*B + M; - * thus we have - * (**) sign*Y*a == D*B + M (mod |n|). - */ + /*- + * Now + * A = D*B + M; + * thus we have + * (**) sign*Y*a == D*B + M (mod |n|). + */ tmp = A; /* keep the BIGNUM object, the value does not * matter */ @@ -647,25 +647,25 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, B = M; /* ... so we have 0 <= B < A again */ - /*- - * Since the former M is now B and the former B is now A, - * (**) translates into - * sign*Y*a == D*A + B (mod |n|), - * i.e. - * sign*Y*a - D*A == B (mod |n|). - * Similarly, (*) translates into - * -sign*X*a == A (mod |n|). - * - * Thus, - * sign*Y*a + D*sign*X*a == B (mod |n|), - * i.e. - * sign*(Y + D*X)*a == B (mod |n|). - * - * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at - * -sign*X*a == B (mod |n|), - * sign*Y*a == A (mod |n|). - * Note that X and Y stay non-negative all the time. - */ + /*- + * Since the former M is now B and the former B is now A, + * (**) translates into + * sign*Y*a == D*A + B (mod |n|), + * i.e. + * sign*Y*a - D*A == B (mod |n|). + * Similarly, (*) translates into + * -sign*X*a == A (mod |n|). + * + * Thus, + * sign*Y*a + D*sign*X*a == B (mod |n|), + * i.e. + * sign*(Y + D*X)*a == B (mod |n|). + * + * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at + * -sign*X*a == B (mod |n|), + * sign*Y*a == A (mod |n|). + * Note that X and Y stay non-negative all the time. + */ if (!BN_mul(tmp, D, X, ctx)) goto err; @@ -679,13 +679,13 @@ static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, sign = -sign; } - /*- - * The while loop (Euclid's algorithm) ends when - * A == gcd(a,n); - * we have - * sign*Y*a == A (mod |n|), - * where Y is non-negative. - */ + /*- + * The while loop (Euclid's algorithm) ends when + * A == gcd(a,n); + * we have + * sign*Y*a == A (mod |n|), + * where Y is non-negative. + */ if (sign < 0) { if (!BN_sub(Y, n, Y)) diff --git a/crypto/bn/bn_mul.c b/crypto/bn/bn_mul.c index f681fa58b8..9b66e666b7 100644 --- a/crypto/bn/bn_mul.c +++ b/crypto/bn/bn_mul.c @@ -484,11 +484,11 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); } - /*- - * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - */ + /*- + * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + */ c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); @@ -499,12 +499,12 @@ void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); } - /*- - * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - * c1 holds the carry bits - */ + /*- + * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + * c1 holds the carry bits + */ c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); @@ -642,11 +642,11 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, } } - /*- - * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - */ + /*- + * t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + */ c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); @@ -657,12 +657,12 @@ void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); } - /*- - * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - * c1 holds the carry bits - */ + /*- + * t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + * c1 holds the carry bits + */ c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); @@ -774,13 +774,13 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, bn_mul_recursive(r, &(a[n]), &(b[n]), n, 0, 0, &(t[n2])); } - /*- - * s0 == low(al*bl) - * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) - * We know s0 and s1 so the only unknown is high(al*bl) - * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) - * high(al*bl) == s1 - (r[0]+l[0]+t[0]) - */ + /*- + * s0 == low(al*bl) + * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) + * We know s0 and s1 so the only unknown is high(al*bl) + * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) + * high(al*bl) == s1 - (r[0]+l[0]+t[0]) + */ if (l != NULL) { lp = &(t[n2 + n]); c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n)); @@ -805,22 +805,22 @@ void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, lp[i] = ((~mp[i]) + 1) & BN_MASK2; } - /*- - * s[0] = low(al*bl) - * t[3] = high(al*bl) - * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign - * r[10] = (a[1]*b[1]) - */ - /*- - * R[10] = al*bl - * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) - * R[32] = ah*bh - */ - /*- - * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) - * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) - * R[3]=r[1]+(carry/borrow) - */ + /*- + * s[0] = low(al*bl) + * t[3] = high(al*bl) + * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign + * r[10] = (a[1]*b[1]) + */ + /*- + * R[10] = al*bl + * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) + * R[32] = ah*bh + */ + /*- + * R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) + * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) + * R[3]=r[1]+(carry/borrow) + */ if (l != NULL) { lp = &(t[n2]); c1 = (int)(bn_add_words(lp, &(t[n2 + n]), &(l[0]), n)); diff --git a/crypto/bn/bn_prime.c b/crypto/bn/bn_prime.c index 39dc9b577c..b12295e84e 100644 --- a/crypto/bn/bn_prime.c +++ b/crypto/bn/bn_prime.c @@ -527,17 +527,17 @@ static int probable_prime(BIGNUM *rnd, int bits) if (is_single_word) { BN_ULONG rnd_word = BN_get_word(rnd); - /*- - * In the case that the candidate prime is a single word then - * we check that: - * 1) It's greater than primes[i] because we shouldn't reject - * 3 as being a prime number because it's a multiple of - * three. - * 2) That it's not a multiple of a known prime. We don't - * check that rnd-1 is also coprime to all the known - * primes because there aren't many small primes where - * that's true. - */ + /*- + * In the case that the candidate prime is a single word then + * we check that: + * 1) It's greater than primes[i] because we shouldn't reject + * 3 as being a prime number because it's a multiple of + * three. + * 2) That it's not a multiple of a known prime. We don't + * check that rnd-1 is also coprime to all the known + * primes because there aren't many small primes where + * that's true. + */ for (i = 1; i < NUMPRIMES && primes[i] < rnd_word; i++) { if ((mods[i] + delta) % primes[i] == 0) { delta += 2; diff --git a/crypto/bn/bn_sqr.c b/crypto/bn/bn_sqr.c index 30a7670ef0..f794c107bd 100644 --- a/crypto/bn/bn_sqr.c +++ b/crypto/bn/bn_sqr.c @@ -242,23 +242,23 @@ void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) bn_sqr_recursive(r, a, n, p); bn_sqr_recursive(&(r[n2]), &(a[n]), n, p); - /*- - * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero - * r[10] holds (a[0]*b[0]) - * r[32] holds (b[1]*b[1]) - */ + /*- + * t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero + * r[10] holds (a[0]*b[0]) + * r[32] holds (b[1]*b[1]) + */ c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); /* t[32] is negative */ c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); - /*- - * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) - * r[10] holds (a[0]*a[0]) - * r[32] holds (a[1]*a[1]) - * c1 holds the carry bits - */ + /*- + * t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) + * r[10] holds (a[0]*a[0]) + * r[32] holds (a[1]*a[1]) + * c1 holds the carry bits + */ c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); if (c1) { p = &(r[n + n2]); diff --git a/crypto/bn/bn_sqrt.c b/crypto/bn/bn_sqrt.c index 772c8080bb..1b259f31c6 100644 --- a/crypto/bn/bn_sqrt.c +++ b/crypto/bn/bn_sqrt.c @@ -132,14 +132,14 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) /* we'll set q later (if needed) */ if (e == 1) { - /*- - * The easy case: (|p|-1)/2 is odd, so 2 has an inverse - * modulo (|p|-1)/2, and square roots can be computed - * directly by modular exponentiation. - * We have - * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2), - * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1. - */ + /*- + * The easy case: (|p|-1)/2 is odd, so 2 has an inverse + * modulo (|p|-1)/2, and square roots can be computed + * directly by modular exponentiation. + * We have + * 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2), + * so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1. + */ if (!BN_rshift(q, p, 2)) goto end; q->neg = 0; @@ -277,24 +277,24 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) goto end; } - /*- - * Now we know that (if p is indeed prime) there is an integer - * k, 0 <= k < 2^e, such that - * - * a^q * y^k == 1 (mod p). - * - * As a^q is a square and y is not, k must be even. - * q+1 is even, too, so there is an element - * - * X := a^((q+1)/2) * y^(k/2), - * - * and it satisfies - * - * X^2 = a^q * a * y^k - * = a, - * - * so it is the square root that we are looking for. - */ + /*- + * Now we know that (if p is indeed prime) there is an integer + * k, 0 <= k < 2^e, such that + * + * a^q * y^k == 1 (mod p). + * + * As a^q is a square and y is not, k must be even. + * q+1 is even, too, so there is an element + * + * X := a^((q+1)/2) * y^(k/2), + * + * and it satisfies + * + * X^2 = a^q * a * y^k + * = a, + * + * so it is the square root that we are looking for. + */ /* t := (q-1)/2 (note that q is odd) */ if (!BN_rshift1(t, q)) @@ -333,15 +333,15 @@ BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) goto end; while (1) { - /*- - * Now b is a^q * y^k for some even k (0 <= k < 2^E - * where E refers to the original value of e, which we - * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). - * - * We have a*b = x^2, - * y^2^(e-1) = -1, - * b^2^(e-1) = 1. - */ + /*- + * Now b is a^q * y^k for some even k (0 <= k < 2^E + * where E refers to the original value of e, which we + * don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). + * + * We have a*b = x^2, + * y^2^(e-1) = -1, + * b^2^(e-1) = 1. + */ if (BN_is_one(b)) { if (!BN_copy(ret, x)) -- cgit v1.2.3