Square and multiply computes a large power by scanning the exponent's binary digits. Each digit causes a squaring; set digits additionally cause a multiplication. For polynomials, every multiplication is reduced modulo a chosen prime polynomial, making the method practical for field-extension arithmetic. section 9.0 section 9.1
For an exponent k whose most significant bit is set:
- Initialize the result with the base, representing the leading 1 bit. section 9.1 section 9.2
- Read the remaining bits from most significant toward least significant. section 9.1
- Square the current result for every bit. section 9.6
- If the bit is 1, multiply the square by the original base; if it is 0, skip that multiplication. section 9.1 section 9.2
- Reduce each product modulo the irreducible polynomial through the polynomial multiplication routine. section 9.2
Computing x^5 modulo x^2 + x + 3 over mod 43
The exponent 5 is binary 101. Start with x. Squaring gives x^2, which reduces to -x - 3; the middle bit is 0, so multiplication is skipped. Squaring again gives 5x + 6. The final bit is 1, so multiplying by x and reducing yields x + 28. section 9.1
Figure 9.1 Polynomial square and multiply algorithm, which will be used in chapter 12 to compute square roots
The flow diagram helps trace initialization, repeated squaring, conditional multiplication, and the final result. section 9.1
Listing 9.1 Square and multiply
void poly_sqm(POLY *x2, POLY x, POLY a, int flag)
{
POLY tmp;
poly_init(&tmp);
poly_mul(&tmp, x, x); #1
if(flag)
poly_mul(x2, tmp, a); #2
else
poly_copy(x2, tmp); #3
poly_clear(&tmp);
}
The single-stage routine separates temporary squaring from the flag-controlled multiplication and cleanup. section 9.2
Listing 9.2 Polynomial exponentiation
void poly_pow(POLY *h, POLY g, mpz_t k)
{
int bitcnt, bit;
POLY a;
poly_init(&a);
poly_copy(&a, g); #1
bitcnt = mpz_sizeinbase(k, 2) - 2; #2
while(bitcnt >= 0)
{
bit = mpz_tstbit(k, bitcnt); #3
poly_sqm(&a, a, g, bit); #3
bitcnt--; #3
}
poly_copy(h, a); #4
poly_clear(&a);
}
The general routine initializes the result, counts exponent bits with mpz_sizeinbase(), tests bits with mpz_tstbit(), loops, and copies the result. section 9.2
