andre@0: /* This Source Code Form is subject to the terms of the Mozilla Public
andre@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
andre@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
andre@0: 
andre@0: #include "mpi.h"
andre@0: #include "mp_gf2m.h"
andre@0: #include "ecl-priv.h"
andre@0: #include "mpi-priv.h"
andre@0: #include <stdlib.h>
andre@0: 
andre@0: /* Allocate memory for a new GFMethod object. */
andre@0: GFMethod *
andre@0: GFMethod_new()
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	GFMethod *meth;
andre@0: 	meth = (GFMethod *) malloc(sizeof(GFMethod));
andre@0: 	if (meth == NULL)
andre@0: 		return NULL;
andre@0: 	meth->constructed = MP_YES;
andre@0: 	MP_DIGITS(&meth->irr) = 0;
andre@0: 	meth->extra_free = NULL;
andre@0: 	MP_CHECKOK(mp_init(&meth->irr));
andre@0: 
andre@0:   CLEANUP:
andre@0: 	if (res != MP_OKAY) {
andre@0: 		GFMethod_free(meth);
andre@0: 		return NULL;
andre@0: 	}
andre@0: 	return meth;
andre@0: }
andre@0: 
andre@0: /* Construct a generic GFMethod for arithmetic over prime fields with
andre@0:  * irreducible irr. */
andre@0: GFMethod *
andre@0: GFMethod_consGFp(const mp_int *irr)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	GFMethod *meth = NULL;
andre@0: 
andre@0: 	meth = GFMethod_new();
andre@0: 	if (meth == NULL)
andre@0: 		return NULL;
andre@0: 
andre@0: 	MP_CHECKOK(mp_copy(irr, &meth->irr));
andre@0: 	meth->irr_arr[0] = mpl_significant_bits(irr);
andre@0: 	meth->irr_arr[1] = meth->irr_arr[2] = meth->irr_arr[3] =
andre@0: 		meth->irr_arr[4] = 0;
andre@0: 	switch(MP_USED(&meth->irr)) {
andre@0: 	/* maybe we need 1 and 2 words here as well?*/
andre@0: 	case 3:
andre@0: 		meth->field_add = &ec_GFp_add_3;
andre@0: 		meth->field_sub = &ec_GFp_sub_3;
andre@0: 		break;
andre@0: 	case 4:
andre@0: 		meth->field_add = &ec_GFp_add_4;
andre@0: 		meth->field_sub = &ec_GFp_sub_4;
andre@0: 		break;
andre@0: 	case 5:
andre@0: 		meth->field_add = &ec_GFp_add_5;
andre@0: 		meth->field_sub = &ec_GFp_sub_5;
andre@0: 		break;
andre@0: 	case 6:
andre@0: 		meth->field_add = &ec_GFp_add_6;
andre@0: 		meth->field_sub = &ec_GFp_sub_6;
andre@0: 		break;
andre@0: 	default:
andre@0: 		meth->field_add = &ec_GFp_add;
andre@0: 		meth->field_sub = &ec_GFp_sub;
andre@0: 	}
andre@0: 	meth->field_neg = &ec_GFp_neg;
andre@0: 	meth->field_mod = &ec_GFp_mod;
andre@0: 	meth->field_mul = &ec_GFp_mul;
andre@0: 	meth->field_sqr = &ec_GFp_sqr;
andre@0: 	meth->field_div = &ec_GFp_div;
andre@0: 	meth->field_enc = NULL;
andre@0: 	meth->field_dec = NULL;
andre@0: 	meth->extra1 = NULL;
andre@0: 	meth->extra2 = NULL;
andre@0: 	meth->extra_free = NULL;
andre@0: 
andre@0:   CLEANUP:
andre@0: 	if (res != MP_OKAY) {
andre@0: 		GFMethod_free(meth);
andre@0: 		return NULL;
andre@0: 	}
andre@0: 	return meth;
andre@0: }
andre@0: 
andre@0: /* Construct a generic GFMethod for arithmetic over binary polynomial
andre@0:  * fields with irreducible irr that has array representation irr_arr (see
andre@0:  * ecl-priv.h for description of the representation).  If irr_arr is NULL, 
andre@0:  * then it is constructed from the bitstring representation. */
andre@0: GFMethod *
andre@0: GFMethod_consGF2m(const mp_int *irr, const unsigned int irr_arr[5])
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	int ret;
andre@0: 	GFMethod *meth = NULL;
andre@0: 
andre@0: 	meth = GFMethod_new();
andre@0: 	if (meth == NULL)
andre@0: 		return NULL;
andre@0: 
andre@0: 	MP_CHECKOK(mp_copy(irr, &meth->irr));
andre@0: 	if (irr_arr != NULL) {
andre@0: 		/* Irreducible polynomials are either trinomials or pentanomials. */
andre@0: 		meth->irr_arr[0] = irr_arr[0];
andre@0: 		meth->irr_arr[1] = irr_arr[1];
andre@0: 		meth->irr_arr[2] = irr_arr[2];
andre@0: 		if (irr_arr[2] > 0) {
andre@0: 			meth->irr_arr[3] = irr_arr[3];
andre@0: 			meth->irr_arr[4] = irr_arr[4];
andre@0: 		} else {
andre@0: 			meth->irr_arr[3] = meth->irr_arr[4] = 0;
andre@0: 		}
andre@0: 	} else {
andre@0: 		ret = mp_bpoly2arr(irr, meth->irr_arr, 5);
andre@0: 		/* Irreducible polynomials are either trinomials or pentanomials. */
andre@0: 		if ((ret != 5) && (ret != 3)) {
andre@0: 			res = MP_UNDEF;
andre@0: 			goto CLEANUP;
andre@0: 		}
andre@0: 	}
andre@0: 	meth->field_add = &ec_GF2m_add;
andre@0: 	meth->field_neg = &ec_GF2m_neg;
andre@0: 	meth->field_sub = &ec_GF2m_add;
andre@0: 	meth->field_mod = &ec_GF2m_mod;
andre@0: 	meth->field_mul = &ec_GF2m_mul;
andre@0: 	meth->field_sqr = &ec_GF2m_sqr;
andre@0: 	meth->field_div = &ec_GF2m_div;
andre@0: 	meth->field_enc = NULL;
andre@0: 	meth->field_dec = NULL;
andre@0: 	meth->extra1 = NULL;
andre@0: 	meth->extra2 = NULL;
andre@0: 	meth->extra_free = NULL;
andre@0: 
andre@0:   CLEANUP:
andre@0: 	if (res != MP_OKAY) {
andre@0: 		GFMethod_free(meth);
andre@0: 		return NULL;
andre@0: 	}
andre@0: 	return meth;
andre@0: }
andre@0: 
andre@0: /* Free the memory allocated (if any) to a GFMethod object. */
andre@0: void
andre@0: GFMethod_free(GFMethod *meth)
andre@0: {
andre@0: 	if (meth == NULL)
andre@0: 		return;
andre@0: 	if (meth->constructed == MP_NO)
andre@0: 		return;
andre@0: 	mp_clear(&meth->irr);
andre@0: 	if (meth->extra_free != NULL)
andre@0: 		meth->extra_free(meth);
andre@0: 	free(meth);
andre@0: }
andre@0: 
andre@0: /* Wrapper functions for generic prime field arithmetic. */
andre@0: 
andre@0: /* Add two field elements.  Assumes that 0 <= a, b < meth->irr */
andre@0: mp_err
andre@0: ec_GFp_add(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 		   const GFMethod *meth)
andre@0: {
andre@0: 	/* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a + b (mod p) */
andre@0: 	mp_err res;
andre@0: 
andre@0: 	if ((res = mp_add(a, b, r)) != MP_OKAY) {
andre@0: 		return res;
andre@0: 	}
andre@0: 	if (mp_cmp(r, &meth->irr) >= 0) {
andre@0: 		return mp_sub(r, &meth->irr, r);
andre@0: 	}
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* Negates a field element.  Assumes that 0 <= a < meth->irr */
andre@0: mp_err
andre@0: ec_GFp_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	/* PRE: 0 <= a < p = meth->irr POST: 0 <= r < p, r = -a (mod p) */
andre@0: 
andre@0: 	if (mp_cmp_z(a) == 0) {
andre@0: 		mp_zero(r);
andre@0: 		return MP_OKAY;
andre@0: 	}
andre@0: 	return mp_sub(&meth->irr, a, r);
andre@0: }
andre@0: 
andre@0: /* Subtracts two field elements.  Assumes that 0 <= a, b < meth->irr */
andre@0: mp_err
andre@0: ec_GFp_sub(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 		   const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 
andre@0: 	/* PRE: 0 <= a, b < p = meth->irr POST: 0 <= r < p, r = a - b (mod p) */
andre@0: 	res = mp_sub(a, b, r);
andre@0: 	if (res == MP_RANGE) {
andre@0: 		MP_CHECKOK(mp_sub(b, a, r));
andre@0: 		if (mp_cmp_z(r) < 0) {
andre@0: 			MP_CHECKOK(mp_add(r, &meth->irr, r));
andre@0: 		}
andre@0: 		MP_CHECKOK(ec_GFp_neg(r, r, meth));
andre@0: 	}
andre@0: 	if (mp_cmp_z(r) < 0) {
andre@0: 		MP_CHECKOK(mp_add(r, &meth->irr, r));
andre@0: 	}
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: /* 
andre@0:  * Inline adds for small curve lengths.
andre@0:  */
andre@0: /* 3 words */
andre@0: mp_err
andre@0: ec_GFp_add_3(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit a0 = 0, a1 = 0, a2 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0;
andre@0: 	mp_digit carry;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 3:
andre@0: 		a2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		a1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		a0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
andre@0: 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
andre@0: 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
andre@0: #else
andre@0: 	__asm__ (
andre@0:                 "xorq   %3,%3           \n\t"
andre@0:                 "addq   %4,%0           \n\t"
andre@0:                 "adcq   %5,%1           \n\t"
andre@0:                 "adcq   %6,%2           \n\t"
andre@0:                 "adcq   $0,%3           \n\t"
andre@0:                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(carry)
andre@0:                 : "r" (a0), "r" (a1), "r" (a2),
andre@0: 		  "0" (r0), "1" (r1), "2" (r2)
andre@0:                 : "%cc" );
andre@0: #endif
andre@0: 
andre@0: 	MP_CHECKOK(s_mp_pad(r, 3));
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 3;
andre@0: 
andre@0: 	/* Do quick 'subract' if we've gone over 
andre@0: 	 * (add the 2's complement of the curve field) */
andre@0: 	 a2 = MP_DIGIT(&meth->irr,2);
andre@0: 	if (carry ||  r2 >  a2 ||
andre@0: 		((r2 == a2) && mp_cmp(r,&meth->irr) != MP_LT)) {
andre@0: 		a1 = MP_DIGIT(&meth->irr,1);
andre@0: 		a0 = MP_DIGIT(&meth->irr,0);
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
andre@0: 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
andre@0: 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
andre@0: #else
andre@0: 		__asm__ (
andre@0: 			"subq   %3,%0           \n\t"
andre@0: 			"sbbq   %4,%1           \n\t"
andre@0: 			"sbbq   %5,%2           \n\t"
andre@0: 			: "=r"(r0), "=r"(r1), "=r"(r2)
andre@0: 			: "r" (a0), "r" (a1), "r" (a2),
andre@0: 			  "0" (r0), "1" (r1), "2" (r2)
andre@0: 			: "%cc" );
andre@0: #endif
andre@0: 		MP_DIGIT(r, 2) = r2;
andre@0: 		MP_DIGIT(r, 1) = r1;
andre@0: 		MP_DIGIT(r, 0) = r0;
andre@0: 	}
andre@0: 	
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 4 words */
andre@0: mp_err
andre@0: ec_GFp_add_4(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
andre@0: 	mp_digit carry;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 4:
andre@0: 		a3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		a2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		a1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		a0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
andre@0: 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
andre@0: 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
andre@0: 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
andre@0: #else
andre@0: 	__asm__ (
andre@0:                 "xorq   %4,%4           \n\t"
andre@0:                 "addq   %5,%0           \n\t"
andre@0:                 "adcq   %6,%1           \n\t"
andre@0:                 "adcq   %7,%2           \n\t"
andre@0:                 "adcq   %8,%3           \n\t"
andre@0:                 "adcq   $0,%4           \n\t"
andre@0:                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r"(carry)
andre@0:                 : "r" (a0), "r" (a1), "r" (a2), "r" (a3),
andre@0: 		  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
andre@0:                 : "%cc" );
andre@0: #endif
andre@0: 
andre@0: 	MP_CHECKOK(s_mp_pad(r, 4));
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 4;
andre@0: 
andre@0: 	/* Do quick 'subract' if we've gone over 
andre@0: 	 * (add the 2's complement of the curve field) */
andre@0: 	 a3 = MP_DIGIT(&meth->irr,3);
andre@0: 	if (carry ||  r3 >  a3 ||
andre@0: 		((r3 == a3) && mp_cmp(r,&meth->irr) != MP_LT)) {
andre@0: 		a2 = MP_DIGIT(&meth->irr,2);
andre@0: 		a1 = MP_DIGIT(&meth->irr,1);
andre@0: 		a0 = MP_DIGIT(&meth->irr,0);
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
andre@0: 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
andre@0: 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
andre@0: 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
andre@0: #else
andre@0: 		__asm__ (
andre@0: 			"subq   %4,%0           \n\t"
andre@0: 			"sbbq   %5,%1           \n\t"
andre@0: 			"sbbq   %6,%2           \n\t"
andre@0: 			"sbbq   %7,%3           \n\t"
andre@0: 			: "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
andre@0: 			: "r" (a0), "r" (a1), "r" (a2), "r" (a3),
andre@0: 			  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
andre@0: 			: "%cc" );
andre@0: #endif
andre@0: 		MP_DIGIT(r, 3) = r3;
andre@0: 		MP_DIGIT(r, 2) = r2;
andre@0: 		MP_DIGIT(r, 1) = r1;
andre@0: 		MP_DIGIT(r, 0) = r0;
andre@0: 	}
andre@0: 	
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 5 words */
andre@0: mp_err
andre@0: ec_GFp_add_5(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
andre@0: 	mp_digit carry;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 5:
andre@0: 		a4 = MP_DIGIT(a,4);
andre@0: 	case 4:
andre@0: 		a3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		a2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		a1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		a0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 5:
andre@0: 		r4 = MP_DIGIT(b,4);
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
andre@0: 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
andre@0: 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
andre@0: 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
andre@0: 	MP_ADD_CARRY(a4, r4, r4, carry, carry);
andre@0: 
andre@0: 	MP_CHECKOK(s_mp_pad(r, 5));
andre@0: 	MP_DIGIT(r, 4) = r4;
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 5;
andre@0: 
andre@0: 	/* Do quick 'subract' if we've gone over 
andre@0: 	 * (add the 2's complement of the curve field) */
andre@0: 	 a4 = MP_DIGIT(&meth->irr,4);
andre@0: 	if (carry ||  r4 >  a4 ||
andre@0: 		((r4 == a4) && mp_cmp(r,&meth->irr) != MP_LT)) {
andre@0: 		a3 = MP_DIGIT(&meth->irr,3);
andre@0: 		a2 = MP_DIGIT(&meth->irr,2);
andre@0: 		a1 = MP_DIGIT(&meth->irr,1);
andre@0: 		a0 = MP_DIGIT(&meth->irr,0);
andre@0: 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
andre@0: 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
andre@0: 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
andre@0: 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
andre@0: 		MP_SUB_BORROW(r4, a4, r4, carry, carry);
andre@0: 		MP_DIGIT(r, 4) = r4;
andre@0: 		MP_DIGIT(r, 3) = r3;
andre@0: 		MP_DIGIT(r, 2) = r2;
andre@0: 		MP_DIGIT(r, 1) = r1;
andre@0: 		MP_DIGIT(r, 0) = r0;
andre@0: 	}
andre@0: 	
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 6 words */
andre@0: mp_err
andre@0: ec_GFp_add_6(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit a0 = 0, a1 = 0, a2 = 0, a3 = 0, a4 = 0, a5 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
andre@0: 	mp_digit carry;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 6:
andre@0: 		a5 = MP_DIGIT(a,5);
andre@0: 	case 5:
andre@0: 		a4 = MP_DIGIT(a,4);
andre@0: 	case 4:
andre@0: 		a3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		a2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		a1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		a0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 6:
andre@0: 		r5 = MP_DIGIT(b,5);
andre@0: 	case 5:
andre@0: 		r4 = MP_DIGIT(b,4);
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: 	MP_ADD_CARRY(a0, r0, r0, 0,     carry);
andre@0: 	MP_ADD_CARRY(a1, r1, r1, carry, carry);
andre@0: 	MP_ADD_CARRY(a2, r2, r2, carry, carry);
andre@0: 	MP_ADD_CARRY(a3, r3, r3, carry, carry);
andre@0: 	MP_ADD_CARRY(a4, r4, r4, carry, carry);
andre@0: 	MP_ADD_CARRY(a5, r5, r5, carry, carry);
andre@0: 
andre@0: 	MP_CHECKOK(s_mp_pad(r, 6));
andre@0: 	MP_DIGIT(r, 5) = r5;
andre@0: 	MP_DIGIT(r, 4) = r4;
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 6;
andre@0: 
andre@0: 	/* Do quick 'subract' if we've gone over 
andre@0: 	 * (add the 2's complement of the curve field) */
andre@0: 	a5 = MP_DIGIT(&meth->irr,5);
andre@0: 	if (carry ||  r5 >  a5 ||
andre@0: 		((r5 == a5) && mp_cmp(r,&meth->irr) != MP_LT)) {
andre@0: 		a4 = MP_DIGIT(&meth->irr,4);
andre@0: 		a3 = MP_DIGIT(&meth->irr,3);
andre@0: 		a2 = MP_DIGIT(&meth->irr,2);
andre@0: 		a1 = MP_DIGIT(&meth->irr,1);
andre@0: 		a0 = MP_DIGIT(&meth->irr,0);
andre@0: 		MP_SUB_BORROW(r0, a0, r0, 0,     carry);
andre@0: 		MP_SUB_BORROW(r1, a1, r1, carry, carry);
andre@0: 		MP_SUB_BORROW(r2, a2, r2, carry, carry);
andre@0: 		MP_SUB_BORROW(r3, a3, r3, carry, carry);
andre@0: 		MP_SUB_BORROW(r4, a4, r4, carry, carry);
andre@0: 		MP_SUB_BORROW(r5, a5, r5, carry, carry);
andre@0: 		MP_DIGIT(r, 5) = r5;
andre@0: 		MP_DIGIT(r, 4) = r4;
andre@0: 		MP_DIGIT(r, 3) = r3;
andre@0: 		MP_DIGIT(r, 2) = r2;
andre@0: 		MP_DIGIT(r, 1) = r1;
andre@0: 		MP_DIGIT(r, 0) = r0;
andre@0: 	}
andre@0: 	
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /*
andre@0:  * The following subraction functions do in-line subractions based
andre@0:  * on our curve size.
andre@0:  *
andre@0:  * ... 3 words
andre@0:  */
andre@0: mp_err
andre@0: ec_GFp_sub_3(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit b0 = 0, b1 = 0, b2 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0;
andre@0: 	mp_digit borrow;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 3:
andre@0: 		b2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		b1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		b0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
andre@0: 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
andre@0: #else
andre@0: 	__asm__ (
andre@0:                 "xorq   %3,%3           \n\t"
andre@0:                 "subq   %4,%0           \n\t"
andre@0:                 "sbbq   %5,%1           \n\t"
andre@0:                 "sbbq   %6,%2           \n\t"
andre@0:                 "adcq   $0,%3           \n\t"
andre@0:                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r" (borrow)
andre@0:                 : "r" (b0), "r" (b1), "r" (b2), 
andre@0: 		  "0" (r0), "1" (r1), "2" (r2)
andre@0:                 : "%cc" );
andre@0: #endif
andre@0: 
andre@0: 	/* Do quick 'add' if we've gone under 0
andre@0: 	 * (subtract the 2's complement of the curve field) */
andre@0: 	if (borrow) {
andre@0: 	 	b2 = MP_DIGIT(&meth->irr,2);
andre@0: 		b1 = MP_DIGIT(&meth->irr,1);
andre@0: 		b0 = MP_DIGIT(&meth->irr,0);
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
andre@0: 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
andre@0: #else
andre@0: 		__asm__ (
andre@0: 			"addq   %3,%0           \n\t"
andre@0: 			"adcq   %4,%1           \n\t"
andre@0: 			"adcq   %5,%2           \n\t"
andre@0: 			: "=r"(r0), "=r"(r1), "=r"(r2)
andre@0: 			: "r" (b0), "r" (b1), "r" (b2),
andre@0:   			  "0" (r0), "1" (r1), "2" (r2)
andre@0: 			: "%cc" );
andre@0: #endif
andre@0: 	}
andre@0: 
andre@0: #ifdef MPI_AMD64_ADD
andre@0: 	/* compiler fakeout? */
andre@0: 	if ((r2 == b0) && (r1 == b0) && (r0 == b0)) { 
andre@0: 		MP_CHECKOK(s_mp_pad(r, 4));
andre@0: 	} 
andre@0: #endif
andre@0: 	MP_CHECKOK(s_mp_pad(r, 3));
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 3;
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 4 words */
andre@0: mp_err
andre@0: ec_GFp_sub_4(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0;
andre@0: 	mp_digit borrow;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 4:
andre@0: 		b3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		b2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		b1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		b0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
andre@0: 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
andre@0: #else
andre@0: 	__asm__ (
andre@0:                 "xorq   %4,%4           \n\t"
andre@0:                 "subq   %5,%0           \n\t"
andre@0:                 "sbbq   %6,%1           \n\t"
andre@0:                 "sbbq   %7,%2           \n\t"
andre@0:                 "sbbq   %8,%3           \n\t"
andre@0:                 "adcq   $0,%4           \n\t"
andre@0:                 : "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3), "=r" (borrow)
andre@0:                 : "r" (b0), "r" (b1), "r" (b2), "r" (b3),
andre@0: 		  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
andre@0:                 : "%cc" );
andre@0: #endif
andre@0: 
andre@0: 	/* Do quick 'add' if we've gone under 0
andre@0: 	 * (subtract the 2's complement of the curve field) */
andre@0: 	if (borrow) {
andre@0: 	 	b3 = MP_DIGIT(&meth->irr,3);
andre@0: 	 	b2 = MP_DIGIT(&meth->irr,2);
andre@0: 		b1 = MP_DIGIT(&meth->irr,1);
andre@0: 		b0 = MP_DIGIT(&meth->irr,0);
andre@0: #ifndef MPI_AMD64_ADD
andre@0: 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
andre@0: 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
andre@0: #else
andre@0: 		__asm__ (
andre@0: 			"addq   %4,%0           \n\t"
andre@0: 			"adcq   %5,%1           \n\t"
andre@0: 			"adcq   %6,%2           \n\t"
andre@0: 			"adcq   %7,%3           \n\t"
andre@0: 			: "=r"(r0), "=r"(r1), "=r"(r2), "=r"(r3)
andre@0: 			: "r" (b0), "r" (b1), "r" (b2), "r" (b3),
andre@0:   			  "0" (r0), "1" (r1), "2" (r2), "3" (r3)
andre@0: 			: "%cc" );
andre@0: #endif
andre@0: 	}
andre@0: #ifdef MPI_AMD64_ADD
andre@0: 	/* compiler fakeout? */
andre@0: 	if ((r3 == b0) && (r1 == b0) && (r0 == b0)) { 
andre@0: 		MP_CHECKOK(s_mp_pad(r, 4));
andre@0: 	} 
andre@0: #endif
andre@0: 	MP_CHECKOK(s_mp_pad(r, 4));
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 4;
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 5 words */
andre@0: mp_err
andre@0: ec_GFp_sub_5(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0;
andre@0: 	mp_digit borrow;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 5:
andre@0: 		r4 = MP_DIGIT(a,4);
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 5:
andre@0: 		b4 = MP_DIGIT(b,4);
andre@0: 	case 4:
andre@0: 		b3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		b2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		b1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		b0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
andre@0: 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
andre@0: 
andre@0: 	/* Do quick 'add' if we've gone under 0
andre@0: 	 * (subtract the 2's complement of the curve field) */
andre@0: 	if (borrow) {
andre@0: 	 	b4 = MP_DIGIT(&meth->irr,4);
andre@0: 	 	b3 = MP_DIGIT(&meth->irr,3);
andre@0: 	 	b2 = MP_DIGIT(&meth->irr,2);
andre@0: 		b1 = MP_DIGIT(&meth->irr,1);
andre@0: 		b0 = MP_DIGIT(&meth->irr,0);
andre@0: 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
andre@0: 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
andre@0: 	}
andre@0: 	MP_CHECKOK(s_mp_pad(r, 5));
andre@0: 	MP_DIGIT(r, 4) = r4;
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 5;
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: /* 6 words */
andre@0: mp_err
andre@0: ec_GFp_sub_6(const mp_int *a, const mp_int *b, mp_int *r, 
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_digit b0 = 0, b1 = 0, b2 = 0, b3 = 0, b4 = 0, b5 = 0;
andre@0: 	mp_digit r0 = 0, r1 = 0, r2 = 0, r3 = 0, r4 = 0, r5 = 0;
andre@0: 	mp_digit borrow;
andre@0: 
andre@0: 	switch(MP_USED(a)) {
andre@0: 	case 6:
andre@0: 		r5 = MP_DIGIT(a,5);
andre@0: 	case 5:
andre@0: 		r4 = MP_DIGIT(a,4);
andre@0: 	case 4:
andre@0: 		r3 = MP_DIGIT(a,3);
andre@0: 	case 3:
andre@0: 		r2 = MP_DIGIT(a,2);
andre@0: 	case 2:
andre@0: 		r1 = MP_DIGIT(a,1);
andre@0: 	case 1:
andre@0: 		r0 = MP_DIGIT(a,0);
andre@0: 	}
andre@0: 	switch(MP_USED(b)) {
andre@0: 	case 6:
andre@0: 		b5 = MP_DIGIT(b,5);
andre@0: 	case 5:
andre@0: 		b4 = MP_DIGIT(b,4);
andre@0: 	case 4:
andre@0: 		b3 = MP_DIGIT(b,3);
andre@0: 	case 3:
andre@0: 		b2 = MP_DIGIT(b,2);
andre@0: 	case 2:
andre@0: 		b1 = MP_DIGIT(b,1);
andre@0: 	case 1:
andre@0: 		b0 = MP_DIGIT(b,0);
andre@0: 	}
andre@0: 
andre@0: 	MP_SUB_BORROW(r0, b0, r0, 0,     borrow);
andre@0: 	MP_SUB_BORROW(r1, b1, r1, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r2, b2, r2, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r3, b3, r3, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r4, b4, r4, borrow, borrow);
andre@0: 	MP_SUB_BORROW(r5, b5, r5, borrow, borrow);
andre@0: 
andre@0: 	/* Do quick 'add' if we've gone under 0
andre@0: 	 * (subtract the 2's complement of the curve field) */
andre@0: 	if (borrow) {
andre@0: 	 	b5 = MP_DIGIT(&meth->irr,5);
andre@0: 	 	b4 = MP_DIGIT(&meth->irr,4);
andre@0: 	 	b3 = MP_DIGIT(&meth->irr,3);
andre@0: 	 	b2 = MP_DIGIT(&meth->irr,2);
andre@0: 		b1 = MP_DIGIT(&meth->irr,1);
andre@0: 		b0 = MP_DIGIT(&meth->irr,0);
andre@0: 		MP_ADD_CARRY(b0, r0, r0, 0,      borrow);
andre@0: 		MP_ADD_CARRY(b1, r1, r1, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b2, r2, r2, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b3, r3, r3, borrow, borrow);
andre@0: 		MP_ADD_CARRY(b4, r4, r4, borrow, borrow);
andre@0: 	}
andre@0: 
andre@0: 	MP_CHECKOK(s_mp_pad(r, 6));
andre@0: 	MP_DIGIT(r, 5) = r5;
andre@0: 	MP_DIGIT(r, 4) = r4;
andre@0: 	MP_DIGIT(r, 3) = r3;
andre@0: 	MP_DIGIT(r, 2) = r2;
andre@0: 	MP_DIGIT(r, 1) = r1;
andre@0: 	MP_DIGIT(r, 0) = r0;
andre@0: 	MP_SIGN(r) = MP_ZPOS;
andre@0: 	MP_USED(r) = 6;
andre@0: 	s_mp_clamp(r);
andre@0: 
andre@0:   CLEANUP:
andre@0: 	return res;
andre@0: }
andre@0: 
andre@0: 
andre@0: /* Reduces an integer to a field element. */
andre@0: mp_err
andre@0: ec_GFp_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	return mp_mod(a, &meth->irr, r);
andre@0: }
andre@0: 
andre@0: /* Multiplies two field elements. */
andre@0: mp_err
andre@0: ec_GFp_mul(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 		   const GFMethod *meth)
andre@0: {
andre@0: 	return mp_mulmod(a, b, &meth->irr, r);
andre@0: }
andre@0: 
andre@0: /* Squares a field element. */
andre@0: mp_err
andre@0: ec_GFp_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	return mp_sqrmod(a, &meth->irr, r);
andre@0: }
andre@0: 
andre@0: /* Divides two field elements. If a is NULL, then returns the inverse of
andre@0:  * b. */
andre@0: mp_err
andre@0: ec_GFp_div(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 		   const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_int t;
andre@0: 
andre@0: 	/* If a is NULL, then return the inverse of b, otherwise return a/b. */
andre@0: 	if (a == NULL) {
andre@0: 		return mp_invmod(b, &meth->irr, r);
andre@0: 	} else {
andre@0: 		/* MPI doesn't support divmod, so we implement it using invmod and 
andre@0: 		 * mulmod. */
andre@0: 		MP_CHECKOK(mp_init(&t));
andre@0: 		MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
andre@0: 		MP_CHECKOK(mp_mulmod(a, &t, &meth->irr, r));
andre@0: 	  CLEANUP:
andre@0: 		mp_clear(&t);
andre@0: 		return res;
andre@0: 	}
andre@0: }
andre@0: 
andre@0: /* Wrapper functions for generic binary polynomial field arithmetic. */
andre@0: 
andre@0: /* Adds two field elements. */
andre@0: mp_err
andre@0: ec_GF2m_add(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	return mp_badd(a, b, r);
andre@0: }
andre@0: 
andre@0: /* Negates a field element. Note that for binary polynomial fields, the
andre@0:  * negation of a field element is the field element itself. */
andre@0: mp_err
andre@0: ec_GF2m_neg(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	if (a == r) {
andre@0: 		return MP_OKAY;
andre@0: 	} else {
andre@0: 		return mp_copy(a, r);
andre@0: 	}
andre@0: }
andre@0: 
andre@0: /* Reduces a binary polynomial to a field element. */
andre@0: mp_err
andre@0: ec_GF2m_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	return mp_bmod(a, meth->irr_arr, r);
andre@0: }
andre@0: 
andre@0: /* Multiplies two field elements. */
andre@0: mp_err
andre@0: ec_GF2m_mul(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	return mp_bmulmod(a, b, meth->irr_arr, r);
andre@0: }
andre@0: 
andre@0: /* Squares a field element. */
andre@0: mp_err
andre@0: ec_GF2m_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
andre@0: {
andre@0: 	return mp_bsqrmod(a, meth->irr_arr, r);
andre@0: }
andre@0: 
andre@0: /* Divides two field elements. If a is NULL, then returns the inverse of
andre@0:  * b. */
andre@0: mp_err
andre@0: ec_GF2m_div(const mp_int *a, const mp_int *b, mp_int *r,
andre@0: 			const GFMethod *meth)
andre@0: {
andre@0: 	mp_err res = MP_OKAY;
andre@0: 	mp_int t;
andre@0: 
andre@0: 	/* If a is NULL, then return the inverse of b, otherwise return a/b. */
andre@0: 	if (a == NULL) {
andre@0: 		/* The GF(2^m) portion of MPI doesn't support invmod, so we
andre@0: 		 * compute 1/b. */
andre@0: 		MP_CHECKOK(mp_init(&t));
andre@0: 		MP_CHECKOK(mp_set_int(&t, 1));
andre@0: 		MP_CHECKOK(mp_bdivmod(&t, b, &meth->irr, meth->irr_arr, r));
andre@0: 	  CLEANUP:
andre@0: 		mp_clear(&t);
andre@0: 		return res;
andre@0: 	} else {
andre@0: 		return mp_bdivmod(a, b, &meth->irr, meth->irr_arr, r);
andre@0: 	}
andre@0: }