<commit_before>/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (C) 2007, 2008, 2009 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * RELIC is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with RELIC. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of arithmetic in a quadratic extension over a prime field.
 *
 * @version $Id$
 * @ingroup fp2
 */

#include "relic_core.h"
#include "relic_conf.h"
#include "relic_fp.h"
#include "relic_pp.h"
#include "relic_util.h"

/*============================================================================*/
/* Private definitions                                                        */
/*============================================================================*/

/**
 * Constant used to compute the Frobenius map in higher extensions.
 */
fp2_st const_frb;

/*============================================================================*/
/* Public definitions                                                         */
/*============================================================================*/

void fp2_const_init() {
#if ALLOC == STATIC
	fp2_new(const_frb);
#endif
}

void fp2_const_clean() {
#if ALLOC == STATIC
	fp2_free(const_frb);
#endif
}

void fp2_const_calc() {
	bn_t e;
	fp2_t t;

	bn_null(e);
	fp2_null(t);

	TRY {
		bn_new(e);
		fp2_new(t);
		fp2_zero(t);
		fp_set_dig(t[0], 1);
		fp2_mul_nor(t, t);
		e->used = FP_DIGS;
		dv_copy(e->dp, fp_prime_get(), FP_DIGS);
		bn_sub_dig(e, e, 1);
		bn_div_dig(e, e, 6);
		fp2_exp(t, t, e);
		fp_copy(const_frb[0], t[0]);
		fp_copy(const_frb[1], t[1]);
	} CATCH_ANY {
		THROW(ERR_CAUGHT);
	} FINALLY {
		bn_free(e);
		fp2_free(t);
	}
}

void fp2_const_get(fp2_t f) {
	fp_copy(f[0], const_frb[0]);
	fp_copy(f[1], const_frb[1]);
}

void fp2_copy(fp2_t c, fp2_t a) {
	fp_copy(c[0], a[0]);
	fp_copy(c[1], a[1]);
}

void fp2_neg(fp2_t c, fp2_t a) {
	fp_neg(c[0], a[0]);
	fp_neg(c[1], a[1]);
}

void fp2_zero(fp2_t a) {
	fp_zero(a[0]);
	fp_zero(a[1]);
}

int fp2_is_zero(fp2_t a) {
	return fp_is_zero(a[0]) && fp_is_zero(a[1]);
}

void fp2_rand(fp2_t a) {
	fp_rand(a[0]);
	fp_rand(a[1]);
}

void fp2_print(fp2_t a) {
	fp_print(a[0]);
	fp_print(a[1]);
}

int fp2_cmp(fp2_t a, fp2_t b) {
	return (fp_cmp(a[0], b[0]) == CMP_EQ) && (fp_cmp(a[1], b[1]) == CMP_EQ) ? CMP_EQ
			: CMP_NE;
}

void fp2_add(fp2_t c, fp2_t a, fp2_t b) {
	fp_add(c[0], a[0], b[0]);
	fp_add(c[1], a[1], b[1]);
}

void fp2_sub(fp2_t c, fp2_t a, fp2_t b) {
	fp_sub(c[0], a[0], b[0]);
	fp_sub(c[1], a[1], b[1]);
}

void fp2_dbl(fp2_t c, fp2_t a) {
	/* 2 * (a0 + a1 * u) = 2 * a0 + 2 * a1 * u. */
	fp_dbl(c[0], a[0]);
	fp_dbl(c[1], a[1]);
}

void fp2_mul(fp2_t c, fp2_t a, fp2_t b) {
	fp_t t0, t1, t2;

	fp_null(t0);
	fp_null(t1);
	fp_null(t2);

	TRY {

		fp_new(t0);
		fp_new(t1);
		fp_new(t2);

		/* Karatsuba algorithm. */
		fp_mul(t0, a[0], b[0]);
		fp_mul(t1, a[1], b[1]);
		fp_add(t2, a[0], a[1]);
		fp_add(c[1], b[0], b[1]);
		fp_mul(c[1], c[1], t2);
		fp_sub(c[1], c[1], t0);
		fp_sub(c[1], c[1], t1);
		fp_sub(c[0], t0, t1);

		if (fp_prime_get_qnr() == -2) {
			fp_sub(c[0], c[0], t1);
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
		fp_free(t1);
		fp_free(t2);
	}
}

void fp2_mul_art(fp2_t c, fp2_t a) {
	fp_t t0;

	fp_null(t0);

	TRY {
		fp_new(t0);

		/* (a0 + a1 * u) * u = a1 * u^2 + a0 * u. */
		fp_copy(t0, a[0]);
		fp_neg(c[0], a[1]);
		if (fp_prime_get_qnr() == -2) {
			fp_dbl(c[0], c[0]);
		}
		fp_copy(c[1], t0);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
	}
}

void fp2_mul_nor(fp2_t c, fp2_t a) {
	fp2_t t0;

	fp2_null(t0);

	TRY {
		fp2_new(t0);

		switch (fp_prime_get_mod8()) {
			case 5:
				/* If p = 5 mod 8, x^2 - sqrt(sqrt(-2)) is irreducible. */
				fp2_mul_art(c, a);
				break;
			case 3:
				/* If p = 3 mod 8, x^2 - sqrt(1 + sqrt(-1)) is irreducible. */
				fp2_mul_art(t0, a);
				fp2_add(c, t0, a);
				break;
			case 7:
				/* If p = 7 mod 8 and p = 2,3 mod 5, x^2 - sqrt(2 + sqrt(-1)) is
				 * irreducible. */
				fp2_mul_art(t0, a);
				fp2_add(t0, t0, a);
				fp2_add(c, t0, a);
				break;
			default:
				THROW(ERR_INVALID);
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp2_free(t0);
	}
}

void fp2_sqr(fp2_t c, fp2_t a) {
	fp_t t0, t1;

	fp_null(t0);
	fp_null(t1);

	TRY {
		fp_new(t0);
		fp_new(t1);

		/* t0 = (a0 + a1). */
		fp_add(t0, a[0], a[1]);

		if (fp_prime_get_qnr() == -1) {
			/* t1 = (a0 - a1). */
			fp_sub(t1, a[0], a[1]);
		} else {
			/* t1 = (a0 - 2 * a1). */
			if (fp_prime_get_qnr() == -2) {
				fp_dbl(t1, a[1]);
				fp_sub(t1, a[0], t1);
			}
		}

		/* c_1 = a0 * a1. */
		fp_mul(c[1], a[0], a[1]);

		/* c_0 = a0^2 + b_0^2 * u^2. */
		fp_mul(c[0], t0, t1);
		if (fp_prime_get_qnr() == -2) {
			fp_add(c[0], c[0], c[1]);
		}

		/* c_1 = 2 * a0 * a1. */
		fp_dbl(c[1], c[1]);
		/* c = c_0 + c_1 * u. */
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
		fp_free(t1);
	}
}

void fp2_inv(fp2_t c, fp2_t a) {
	fp_t t0, t1;

	fp_null(t0);
	fp_null(t1);

	TRY {
		fp_new(t0);
		fp_new(t1);

		/* t0 = a0^2, t1 = a1^2. */
		fp_sqr(t0, a[0]);
		fp_sqr(t1, a[1]);

		if (fp_prime_get_qnr() == -2) {
			fp_dbl(t1, t1);
		}

		/* t1 = 1/(a0^2 + a1^2). */
		fp_add(t0, t0, t1);
		fp_inv(t1, t0);

		/* c_0 = a0/(a0^2 + a1^2). */
		fp_mul(c[0], a[0], t1);
		/* c_1 = - a1/(a0^2 + a1^2). */
		fp_mul(c[1], a[1], t1);
		fp_neg(c[1], c[1]);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
		fp_free(t1);
	}
}

void fp2_frb(fp2_t c, fp2_t a) {
	/* (a0 + a1 * u)^p = a0 - a1 * u. */
	fp_copy(c[0], a[0]);
	fp_neg(c[1], a[1]);
}

void fp2_exp(fp2_t c, fp2_t a, bn_t b) {
	fp2_t t;

	fp2_null(t);

	TRY {
		fp2_new(t);

		fp2_copy(t, a);

		for (int i = bn_bits(b) - 2; i >= 0; i--) {
			fp2_sqr(t, t);
			if (bn_test_bit(b, i)) {
				fp2_mul(t, t, a);
			}
		}
		fp2_copy(c, t);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp2_free(t);
	}
}
<commit_msg>Implemented lazy reduction in fp2_mul.<commit_after>/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (C) 2007, 2008, 2009 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * RELIC is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with RELIC. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of arithmetic in a quadratic extension over a prime field.
 *
 * @version $Id$
 * @ingroup fp2
 */

#include "relic_core.h"
#include "relic_conf.h"
#include "relic_fp.h"
#include "relic_fp_low.h"
#include "relic_pp.h"
#include "relic_util.h"

/*============================================================================*/
/* Private definitions                                                        */
/*============================================================================*/

/**
 * Constant used to compute the Frobenius map in higher extensions.
 */
fp2_st const_frb;

/*============================================================================*/
/* Public definitions                                                         */
/*============================================================================*/

void fp2_const_init() {
#if ALLOC == STATIC
	fp2_new(const_frb);
#endif
}

void fp2_const_clean() {
#if ALLOC == STATIC
	fp2_free(const_frb);
#endif
}

void fp2_const_calc() {
	bn_t e;
	fp2_t t;

	bn_null(e);
	fp2_null(t);

	TRY {
		bn_new(e);
		fp2_new(t);
		fp2_zero(t);
		fp_set_dig(t[0], 1);
		fp2_mul_nor(t, t);
		e->used = FP_DIGS;
		dv_copy(e->dp, fp_prime_get(), FP_DIGS);
		bn_sub_dig(e, e, 1);
		bn_div_dig(e, e, 6);
		fp2_exp(t, t, e);
		fp_copy(const_frb[0], t[0]);
		fp_copy(const_frb[1], t[1]);
	} CATCH_ANY {
		THROW(ERR_CAUGHT);
	} FINALLY {
		bn_free(e);
		fp2_free(t);
	}
}

void fp2_const_get(fp2_t f) {
	fp_copy(f[0], const_frb[0]);
	fp_copy(f[1], const_frb[1]);
}

void fp2_copy(fp2_t c, fp2_t a) {
	fp_copy(c[0], a[0]);
	fp_copy(c[1], a[1]);
}

void fp2_neg(fp2_t c, fp2_t a) {
	fp_neg(c[0], a[0]);
	fp_neg(c[1], a[1]);
}

void fp2_zero(fp2_t a) {
	fp_zero(a[0]);
	fp_zero(a[1]);
}

int fp2_is_zero(fp2_t a) {
	return fp_is_zero(a[0]) && fp_is_zero(a[1]);
}

void fp2_rand(fp2_t a) {
	fp_rand(a[0]);
	fp_rand(a[1]);
}

void fp2_print(fp2_t a) {
	fp_print(a[0]);
	fp_print(a[1]);
}

int fp2_cmp(fp2_t a, fp2_t b) {
	return (fp_cmp(a[0], b[0]) == CMP_EQ) && (fp_cmp(a[1], b[1]) == CMP_EQ) ? CMP_EQ
			: CMP_NE;
}

void fp2_add(fp2_t c, fp2_t a, fp2_t b) {
	fp_add(c[0], a[0], b[0]);
	fp_add(c[1], a[1], b[1]);
}

void fp2_sub(fp2_t c, fp2_t a, fp2_t b) {
	fp_sub(c[0], a[0], b[0]);
	fp_sub(c[1], a[1], b[1]);
}

void fp2_dbl(fp2_t c, fp2_t a) {
	/* 2 * (a0 + a1 * u) = 2 * a0 + 2 * a1 * u. */
	fp_dbl(c[0], a[0]);
	fp_dbl(c[1], a[1]);
}

void fp2_mul(fp2_t c, fp2_t a, fp2_t b) {
	dv_t t0, t1, t2;
	fp_t t;
	dig_t c0, c1;

	dv_null(t0);
	dv_null(t1);
	dv_null(t2);
	fp_null(t);

	TRY {

		dv_new(t0);
		dv_new(t1);
		dv_new(t2);
		fp_new(t);

		/* Karatsuba algorithm. */

		/* t0 = a0 * b0, t1 = a1 * b1. */
		fp_muln_low(t0, a[0], b[0]);
		fp_muln_low(t1, a[1], b[1]);

		/* t2 = (a0 * a1) + (b0 * b1). */
		c0 = fp_addn_low(t2, t0, t1);
		fp_addn_low(t2 + FP_DIGS, t0 + FP_DIGS, t1 + FP_DIGS);
		c0 = fp_add1_low(t2 + FP_DIGS, t2 + FP_DIGS, c0);

		/* t1 = u^2 * (a1 * b1). */
		if (fp_prime_get_qnr() == -2) {
			c0 = fp_lsh1_low(t1, t1);
			fp_lsh1_low(t1 + FP_DIGS, t1 + FP_DIGS);
			t1[FP_DIGS] ^= c0;
		}
		/* t0 = (a0 * a1) + u^2 * (a1 * b1). */
		c0 = fp_subn_low(t0, t0, t1);
		c1 = fp_subn_low(t0 + FP_DIGS, t0 + FP_DIGS, t1 + FP_DIGS);
		fp_sub1_low(t0 + FP_DIGS, t0 + FP_DIGS, c0);
		if (c1) {
			fp_addn_low(t0 + FP_DIGS, t0 + FP_DIGS, fp_prime_get());
		}

		dv_zero(t1, 2 * FP_DIGS);

		/* t1 = a0 + a1, c1 = b0 + b1. */
		fp_add(t, a[0], a[1]);
		fp_add(c[1], b[0], b[1]);
		/* t1 = (a0 + a1) * (b0 + b1). */
		fp_muln_low(t1, t, c[1]);

		/* c0 = t0 mod p. */
		fp_rdc(c[0], t0);

		c0 = fp_subn_low(t1, t1, t2);
		c1 = fp_subn_low(t1 + FP_DIGS, t1 + FP_DIGS, t2 + FP_DIGS);
		fp_sub1_low(t1 + FP_DIGS, t1 + FP_DIGS, c0);
		if (c1) {
			fp_addn_low(t1 + FP_DIGS, t1 + FP_DIGS, fp_prime_get());
		}

		/* c1 = t1 mod p. */
		fp_rdc(c[1], t1);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		dv_free(t0);
		dv_free(t1);
		dv_free(t2);
	}
}

void fp2_mul_art(fp2_t c, fp2_t a) {
	fp_t t0;

	fp_null(t0);

	TRY {
		fp_new(t0);

		/* (a0 + a1 * u) * u = a1 * u^2 + a0 * u. */
		fp_copy(t0, a[0]);
		fp_neg(c[0], a[1]);
		if (fp_prime_get_qnr() == -2) {
			fp_dbl(c[0], c[0]);
		}
		fp_copy(c[1], t0);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
	}
}

void fp2_mul_nor(fp2_t c, fp2_t a) {
	fp2_t t0;

	fp2_null(t0);

	TRY {
		fp2_new(t0);

		switch (fp_prime_get_mod8()) {
			case 5:
				/* If p = 5 mod 8, x^2 - sqrt(sqrt(-2)) is irreducible. */
				fp2_mul_art(c, a);
				break;
			case 3:
				/* If p = 3 mod 8, x^2 - sqrt(1 + sqrt(-1)) is irreducible. */
				fp2_mul_art(t0, a);
				fp2_add(c, t0, a);
				break;
			case 7:
				/* If p = 7 mod 8 and p = 2,3 mod 5, x^2 - sqrt(2 + sqrt(-1)) is
				 * irreducible. */
				fp2_mul_art(t0, a);
				fp2_add(t0, t0, a);
				fp2_add(c, t0, a);
				break;
			default:
				THROW(ERR_INVALID);
		}
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp2_free(t0);
	}
}

void fp2_sqr(fp2_t c, fp2_t a) {
	fp_t t0, t1;

	fp_null(t0);
	fp_null(t1);

	TRY {
		fp_new(t0);
		fp_new(t1);

		/* t0 = (a0 + a1). */
		fp_add(t0, a[0], a[1]);

		if (fp_prime_get_qnr() == -1) {
			/* t1 = (a0 - a1). */
			fp_sub(t1, a[0], a[1]);
		} else {
			/* t1 = (a0 - 2 * a1). */
			if (fp_prime_get_qnr() == -2) {
				fp_dbl(t1, a[1]);
				fp_sub(t1, a[0], t1);
			}
		}

		/* c_1 = a0 * a1. */
		fp_mul(c[1], a[0], a[1]);

		/* c_0 = a0^2 + b_0^2 * u^2. */
		fp_mul(c[0], t0, t1);
		if (fp_prime_get_qnr() == -2) {
			fp_add(c[0], c[0], c[1]);
		}

		/* c_1 = 2 * a0 * a1. */
		fp_dbl(c[1], c[1]);
		/* c = c_0 + c_1 * u. */
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
		fp_free(t1);
	}
}

void fp2_inv(fp2_t c, fp2_t a) {
	fp_t t0, t1;

	fp_null(t0);
	fp_null(t1);

	TRY {
		fp_new(t0);
		fp_new(t1);

		/* t0 = a0^2, t1 = a1^2. */
		fp_sqr(t0, a[0]);
		fp_sqr(t1, a[1]);

		if (fp_prime_get_qnr() == -2) {
			fp_dbl(t1, t1);
		}

		/* t1 = 1/(a0^2 + a1^2). */
		fp_add(t0, t0, t1);
		fp_inv(t1, t0);

		/* c_0 = a0/(a0^2 + a1^2). */
		fp_mul(c[0], a[0], t1);
		/* c_1 = - a1/(a0^2 + a1^2). */
		fp_mul(c[1], a[1], t1);
		fp_neg(c[1], c[1]);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp_free(t0);
		fp_free(t1);
	}
}

void fp2_frb(fp2_t c, fp2_t a) {
	/* (a0 + a1 * u)^p = a0 - a1 * u. */
	fp_copy(c[0], a[0]);
	fp_neg(c[1], a[1]);
}

void fp2_exp(fp2_t c, fp2_t a, bn_t b) {
	fp2_t t;

	fp2_null(t);

	TRY {
		fp2_new(t);

		fp2_copy(t, a);

		for (int i = bn_bits(b) - 2; i >= 0; i--) {
			fp2_sqr(t, t);
			if (bn_test_bit(b, i)) {
				fp2_mul(t, t, a);
			}
		}
		fp2_copy(c, t);
	}
	CATCH_ANY {
		THROW(ERR_CAUGHT);
	}
	FINALLY {
		fp2_free(t);
	}
}

{'fraction_non_alphanumeric': 0.2306989171705808, 'fraction_numerical': 0.056672760511883, 'mean_word_length': 2.9818029115341544, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2187254', 'n_tokens_mistral': 7731, 'n_tokens_neox': 7069, 'n_words': 1489}