fp2.c File Reference

#include <string.h>
#include "fp2.h"
#include "utilities.h"

Include dependency graph for fp2.c:

Go to the source code of this file.

Functions
void	fp2_add (fp2_t *output, fp2_t input_a, fp2_t input_b)
void	fp2_sub (fp2_t *output, fp2_t input_a, fp2_t input_b)
void	fp2_mul (fp2_t *output, fp2_t input_a, fp2_t input_b)
void	fp2_sqr (fp2_t *output, fp2_t input)
void	fp2_neg (fp2_t *output, fp2_t input)
void	fp2_set_to_one (fp2_t *output)
void	fp2_set_to_zero (fp2_t *output)
void	fp2_copy (fp2_t *output, fp2_t input)
void	fp2_cswap (fp2_t *input_a, fp2_t *input_b, uint64_t input)
void	fp2_cset (fp2_t *output, fp2_t input, uint64_t input_mask)
void	fp2_inv (fp2_t *output, fp2_t input)
void	fp2_half (fp2_t *output, fp2_t input)
void	fp2_to_mont (fp2_t *output, fp2_t input)
void	fp2_from_mont (fp2_t *output, fp2_t input)
void	fp2_conj (fp2_t *output, fp2_t input)
void	fp2_to_bytes (uint8_t *output, fp2_t input)
void	fp2_element_from_bytes (fp2_t *output, const uint8_t *input)
int64_t	fp2_is_zero (fp2_t input)
uint8_t	fp2_is_equal (fp2_t input_a, fp2_t input_b)
void	fp2_linear_pass_in (fp2_t *output, const fp2_t *input, uint8_t input_length, uint8_t input_index)
void	fp2_linear_pass_out (fp2_t *output, fp2_t input, uint8_t input_length, uint8_t input_index)
uint8_t	fp2_locate_zero (const fp2_t *input, uint8_t input_length)
uint8_t	fp2_is_square (fp2_t input)
void	fp2_batchinv (fp2_t *output_list, const fp2_t *input_list, uint8_t input_length)
void	fp2_sqrt_slow (fp2_t *output, fp2_t input)
void	fp2_sqrt_fast (fp2_t *output, fp2_t input)
void	fp2_curt (fp2_t *output, fp2_t input)

Function Documentation

fp2_add()

void fp2_add	(	fp2_t *	output,
		fp2_t	input_a,
		fp2_t	input_b )

Definition at line 10 of file fp2.c.

                                                          {
    fp_add(output->re, input_a.re, input_b.re);
    fp_add(output->im, input_a.im, input_b.im);
}

References fp_add, fp2_t::im, and fp2_t::re.

fp2_batchinv()

void fp2_batchinv	(	fp2_t *	output_list,
		const fp2_t *	input_list,
		uint8_t	input_length )

Definition at line 202 of file fp2.c.

                                                                                     {
    int i;
    fp2_t tmp_list[input_length], inv, tmp;
 
    fp2_copy(&tmp_list[0], input_list[0]);
    for(i = 1; i < input_length; i++) { fp2_mul(&tmp_list[i], tmp_list[i - 1], input_list[i]); }
    fp2_inv(&inv, tmp_list[input_length - 1]);
    for(i = (input_length - 1); i > 0; i--) {
        fp2_mul(&tmp, inv, tmp_list[i - 1]);
        fp2_mul(&inv, inv, input_list[i]);
        fp2_copy(&output_list[i], tmp);
    }
    fp2_copy(&output_list[0], inv);
}

References fp2_copy, fp2_inv, fp2_mul, and i.

fp2_conj()

void fp2_conj	(	fp2_t *	output,
		fp2_t	input )

Definition at line 125 of file fp2.c.

                                          {
    fp_copy(output->re, input.re);
    fp_neg(output->im, input.im);
}

References fp_copy, fp_neg(), fp2_t::im, and fp2_t::re.

Here is the call graph for this function:

fp2_copy()

void fp2_copy	(	fp2_t *	output,
		fp2_t	input )

Definition at line 59 of file fp2.c.

                                          {
    fp_copy(output->re, input.re);
    fp_copy(output->im, input.im);
}

References fp_copy, fp2_t::im, and fp2_t::re.

fp2_cset()

void fp2_cset	(	fp2_t *	output,
		fp2_t	input,
		uint64_t	input_mask )

Definition at line 81 of file fp2.c.

                                                               {
    // If mask = 0 then output is not modified, else if input = 0xFF...FF then output <- input
    uint64_t temp;
    unsigned int i;
 
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        temp = input_mask & (output->re[i] ^ input.re[i]);
        output->re[i] = temp ^ output->re[i];
        temp = input_mask & (output->im[i] ^ input.im[i]);
        output->im[i] = temp ^ output->im[i];
    }
}

References FIELD_64BITS_WORDS, i, fp2_t::im, and fp2_t::re.

Referenced by fp2_linear_pass_in(), and fp2_linear_pass_out().

Here is the caller graph for this function:

fp2_cswap()

void fp2_cswap	(	fp2_t *	input_a,
		fp2_t *	input_b,
		uint64_t	input )

Definition at line 65 of file fp2.c.

                                                               {
    // If input = 0 then a <- a and b <- b, else if input = 0xFF...FF then a <- b and b <- a
    uint64_t temp;
    unsigned int i;
 
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        temp = input & (input_a->re[i] ^ input_b->re[i]);
        input_a->re[i] = temp ^ input_a->re[i];
        input_b->re[i] = temp ^ input_b->re[i];
        temp = input & (input_a->im[i] ^ input_b->im[i]);
        input_a->im[i] = temp ^ input_a->im[i];
        input_b->im[i] = temp ^ input_b->im[i];
    }
}

References FIELD_64BITS_WORDS, i, fp2_t::im, and fp2_t::re.

fp2_curt()

void fp2_curt	(	fp2_t *	output,
		fp2_t	input )

Definition at line 399 of file fp2.c.

                                          {
    // This function assumes the input has cube-root
    int i, j, k;
    uint64_t flag;
    fp2_t temp, aux;
    fp2_set_to_one(&aux);
    fp2_copy(&temp, input);
 
    for (i = 0, k = 0; i < 2 * FIELD_64BITS_WORDS && k < CUBE_ROOT_EXPONENT_BITS; i++, k++) {
        flag = 1;
        for (j = 0; j < 64; j++, k++) {
            if ((flag & CUBE_ROOT_EXPONENT[i]) != 0) {fp2_mul(&aux, temp, aux);}
            fp2_sqr(&temp, temp);
            flag <<= 1;
        }
    }
 
    fp2_copy(output, aux);
}

References CUBE_ROOT_EXPONENT_BITS, FIELD_64BITS_WORDS, fp2_copy, fp2_mul, fp2_set_to_one(), fp2_sqr, i, and j.

Referenced by isogeny_walks_3(), and isogeny_walks_get_points_3().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_element_from_bytes()

void fp2_element_from_bytes	(	fp2_t *	output,
		const uint8_t *	input )

Definition at line 140 of file fp2.c.

                                                                 {
    output->re[FIELD_64BITS_WORDS - 1] = 0;
    memcpy(output->re, input, FIELD_BYTES);
    output->im[FIELD_64BITS_WORDS - 1] = 0;
    memcpy(output->im, &input[FIELD_BYTES], FIELD_BYTES);
    fp2_to_mont(output, *output);
}

References FIELD_64BITS_WORDS, FIELD_BYTES, and fp2_to_mont().

Here is the call graph for this function:

fp2_from_mont()

void fp2_from_mont	(	fp2_t *	output,
		fp2_t	input )

Definition at line 119 of file fp2.c.

                                               {
    fp_from_mont(output->re, input.re);
    fp_from_mont(output->im, input.im);
}

References fp_from_mont(), fp2_t::im, and fp2_t::re.

Referenced by fp2_to_bytes().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_half()

void fp2_half	(	fp2_t *	output,
		fp2_t	input )

Definition at line 107 of file fp2.c.

                                          {
    fp_half(output->re, input.re);
    fp_half(output->im, input.im);
}

References fp_half(), fp2_t::im, and fp2_t::re.

Referenced by isogeny_walks_2(), isogeny_walks_2_slow(), and isogeny_walks_get_points_3().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_inv()

void fp2_inv	(	fp2_t *	output,
		fp2_t	input )

Definition at line 95 of file fp2.c.

                                         {
    fp_t N0, N1, S1, S2, zero = {0};
    fp_sqr(N0, input.re);
    fp_sqr(N1, input.im);
    fp_add(S1, N0, N1);
    fp_inv(S1, S1);
    fp_sub(S2, zero, input.im);
    fp_mul(output->re, S1, input.re);
    fp_mul(output->im, S1, S2);
}

References fp_add, fp_inv, fp_mul, fp_sqr, fp_sub, fp2_t::im, and fp2_t::re.

fp2_is_equal()

uint8_t fp2_is_equal	(	fp2_t	input_a,
		fp2_t	input_b )

Definition at line 154 of file fp2.c.

                                                   {
    return fp_is_equal(input_a.re, input_b.re) & fp_is_equal(input_a.im, input_b.im);
}

References fp_is_equal(), fp2_t::im, and fp2_t::re.

Here is the call graph for this function:

fp2_is_square()

uint8_t fp2_is_square

(

fp2_t

input

)

Definition at line 192 of file fp2.c.

                                   {
    fp_t t0, t1;
 
    fp_sqr(t0, input.re);
    fp_sqr(t1, input.im);
    fp_add(t0, t0, t1);
    return fp_is_square(t0);
}

References fp_add, fp_is_square(), fp_sqr, fp2_t::im, and fp2_t::re.

Here is the call graph for this function:

fp2_is_zero()

int64_t fp2_is_zero

(

fp2_t

input

)

Definition at line 149 of file fp2.c.

                                 {
    return fp_is_zero(input.re) & fp_is_zero(input.im);
}

References fp_is_zero(), fp2_t::im, and fp2_t::re.

Referenced by fp2_locate_zero().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_linear_pass_in()

void fp2_linear_pass_in	(	fp2_t *	output,
		const fp2_t *	input,
		uint8_t	input_length,
		uint8_t	input_index )

Definition at line 159 of file fp2.c.

                                                                                                      {
    // This function copies the ith entry of the input into the output 
    // At most 255-length lists
    uint8_t i;
    for(i = 0; i < input_length; i++) {
        int64_t mask = (int64_t)input_index - (int64_t)i;
        fp2_cset(output, input[i], ~((mask >> 63) | (-mask >> 63)));
    }
}

References fp2_cset(), and i.

Referenced by fp2_sqrt_slow(), isogeny_walks_2(), isogeny_walks_2_slow(), and isogeny_walks_3().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_linear_pass_out()

void fp2_linear_pass_out	(	fp2_t *	output,
		fp2_t	input,
		uint8_t	input_length,
		uint8_t	input_index )

Definition at line 170 of file fp2.c.

                                                                                                {
    // This function copies the input into the ith entry of the output
    // At most 255-length lists
    uint8_t i;
    for(i = 0; i < input_length; i++) {
        int64_t mask = (int64_t)input_index - (int64_t)i;
        fp2_cset(&output[i], input, ~((mask >> 63) | (-mask >> 63)));
    }
}

References fp2_cset(), and i.

Here is the call graph for this function:

fp2_locate_zero()

uint8_t fp2_locate_zero	(	const fp2_t *	input,
		uint8_t	input_length )

Definition at line 181 of file fp2.c.

                                                                  {
    // At most 255-length lists
    uint8_t i;
    int64_t index = 0;
    for(i = 0; i < input_length; i++) {
        index |= i & fp2_is_zero(input[i]);
    }
    return (uint8_t)index;
}

References fp2_is_zero(), and i.

Here is the call graph for this function:

fp2_mul()

void fp2_mul	(	fp2_t *	output,
		fp2_t	input_a,
		fp2_t	input_b )

Definition at line 21 of file fp2.c.

                                                          {
    fp_t z0, z1, z2, z3, tmp;
    fp_add(z0, input_a.re, input_a.im);
    fp_add(z1, input_b.re, input_b.im);
    fp_mul(tmp, z0, z1);
    fp_mul(z2, input_a.re, input_b.re);
    fp_mul(z3, input_a.im, input_b.im);
    fp_sub(output->re, z2, z3);
    fp_sub(output->im, tmp, z2);
    fp_sub(output->im, output->im, z3);
}

References fp_add, fp_mul, fp_sub, fp2_t::im, and fp2_t::re.

fp2_neg()

void fp2_neg	(	fp2_t *	output,
		fp2_t	input )

Definition at line 43 of file fp2.c.

                                         {
    fp_neg(output->re, input.re);
    fp_neg(output->im, input.im);
}

References fp_neg(), fp2_t::im, and fp2_t::re.

Here is the call graph for this function:

fp2_set_to_one()

void fp2_set_to_one

(

fp2_t *

output

)

Definition at line 49 of file fp2.c.

                                   {
    fp_set_to_one(output->re);
    fp_set_to_zero(output->im);
}

References fp_set_to_one(), and fp_set_to_zero().

Referenced by fp2_curt(), fp2_sqrt_slow(), isogeny_walks_2(), isogeny_walks_2_slow(), isogeny_walks_3(), isogeny_walks_from_montgomery_model_2(), isogeny_walks_from_montgomery_model_3(), isogeny_walks_get_previous_step_2(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_set_to_zero()

void fp2_set_to_zero

(

fp2_t *

output

)

Definition at line 54 of file fp2.c.

                                    {
    fp_set_to_zero(output->re);
    fp_set_to_zero(output->im);
}

References fp_set_to_zero().

Referenced by cgl_hash_digest_2(), cgl_hash_digest_3(), fp2_sqrt_slow(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_sqr()

void fp2_sqr	(	fp2_t *	output,
		fp2_t	input )

Definition at line 33 of file fp2.c.

                                         {
    fp_t z0, z1, z2;
    fp_add(z0, input.re, input.re);
    fp_add(z1, input.re, input.im);
    fp_sub(z2, input.re, input.im);
    fp_mul(output->re, z1, z2);
    fp_mul(output->im, z0, input.im);
}

References fp_add, fp_mul, fp_sub, fp2_t::im, and fp2_t::re.

fp2_sqrt_fast()

void fp2_sqrt_fast	(	fp2_t *	output,
		fp2_t	input )

Definition at line 333 of file fp2.c.

                                               {
    fp_t delta, x0, t0, x1, t1, temp;
    uint64_t flag;
 
    // x1 <- (a0^2 + a1^2)
    fp_sqr(x0, input.re);
    fp_sqr(x1, input.im);
    fp_add(x1, x0, x1);
    
    // alpha <- x1 ^ ([p + 1] / 4)
    fp_set_to_one(delta);
    fp_copy(temp, x1);
    for (int i = 0; i < FIELD_64BITS_WORDS; i++) {
        flag = 1;
        for (int j = 0; j < 64; j++) {
            if ((flag & SQUARE_ROOT_EXPONENT_14[i]) != 0)
                fp_mul(delta, temp, delta);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
 
    // x0 <- a0 + delta
    fp_add(x0, input.re, delta);
    // t0 <- 2 * x0
    fp_add(t0, x0, x0);
 
    // x1 <- t0 ^ ([p - 3] / 4)
    fp_set_to_one(x1);
    fp_copy(temp, t0);
    for (int i = 0; i < FIELD_64BITS_WORDS; i++) {
        flag = 1;
        for (int j = 0; j < 64; j++) {
            if ((flag & SQUARE_ROOT_EXPONENT_34[i]) != 0)
                fp_mul(x1, temp, x1);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
    
    // x0 <- x0 * x1
    fp_mul(x0, x0, x1);
    // x1 <- a1 * x1
    fp_mul(x1, input.im, x1);
 
    // t1 <- (2 * x0)^2
    fp_add(t1, x0, x0);
    fp_sqr(t1, t1);
 
    fp_t uno, zero;
    fp_set_to_one(uno);
    fp_set_to_zero(zero);
 
    uint8_t selector = -fp_is_equal(t1, t0);
    
    fp_neg(temp, x0);
    fp_copy(t0, x1);
    fp_copy(t1, temp);
 
    constant_time_conditional_mov((uint8_t *)&t0, (uint8_t *)&x0, FIELD_64BITS_WORDS * 8, selector);
    constant_time_conditional_mov((uint8_t *)&t1, (uint8_t *)&x1, FIELD_64BITS_WORDS * 8, selector);
 
    fp_copy(output->re, t0);
    fp_copy(output->im, t1);
}

References constant_time_conditional_mov(), FIELD_64BITS_WORDS, fp_add, fp_copy, fp_is_equal(), fp_mul, fp_neg(), fp_set_to_one(), fp_set_to_zero(), fp_sqr, i, fp2_t::im, j, and fp2_t::re.

Referenced by isogeny_walks_2().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_sqrt_slow()

void fp2_sqrt_slow	(	fp2_t *	output,
		fp2_t	input )

Definition at line 283 of file fp2.c.

                                               {
    // Square root over Fq with q = p²: Kong et al.'s algorithm. We assume p² = 9 mod 16 and p = 3 mod 4
    // This function assumes the input has square-root
 
    int i, j, k;
    uint64_t flag;
    fp_t one;
    fp2_t a_double, b, b_square, c, r, temp, s[2], u;
 
    fp_set_to_one(one);
 
    fp2_set_to_one(&b);
    fp2_add(&a_double, input, input);
    fp2_copy(&temp, a_double);
 
    for (i = 0, k = 0; i < 2 * FIELD_64BITS_WORDS && k < SQUARE_ROOT_EXPONENT_BITS; i++, k++) {
        flag = 1;
        for (j = 0; j < 64; j++, k++) {
            if ((flag & SQUARE_ROOT_EXPONENT_916[i]) != 0) {fp2_mul(&b, temp, b);}
            fp2_sqr(&temp, temp);
            flag <<= 1;
        }
    }
    fp2_sqr(&b_square, b);
    fp2_mul(&c, a_double, b_square);
    fp2_sqr(&r, c);
    fp_sub(c.re, c.re, one); // c - 1
 
    fp2_mul(&s[0], input, b);
    fp2_mul(&s[0], s[0], c);
    fp2_mul(&u, b, *((fp2_t *)&SQUARE_ROOT_CONSTANT_T));
    fp2_mul(&s[1], u, *((fp2_t *)&SQUARE_ROOT_CONSTANT_D));
 
    fp2_sqr(&c, s[1]);
    fp2_mul(&c, c, input);
    fp2_add(&c, c, c);
    fp_sub(c.re, c.re, one); // c - 1
    fp2_mul(&s[1], s[1], input);
    fp2_mul(&s[1], s[1], c);
 
    // select the correct square-root output by linear pass (constant-time)
    fp2_linear_pass_in(output, s, 2, fp_is_equal(one, r.re) & fp_is_zero(r.im));
 
    // clear data
    fp2_set_to_zero(&s[0]);
    fp2_set_to_zero(&s[1]);
    fp2_set_to_zero(&temp);
}

References FIELD_64BITS_WORDS, fp2_add, fp2_copy, fp2_linear_pass_in(), fp2_mul, fp2_set_to_one(), fp2_set_to_zero(), fp2_sqr, fp_is_equal(), fp_is_zero(), fp_set_to_one(), fp_sub, i, fp2_t::im, j, fp2_t::re, and SQUARE_ROOT_EXPONENT_BITS.

Referenced by isogeny_walks_2_slow(), and isogeny_walks_get_points_3().

Here is the call graph for this function:

Here is the caller graph for this function:

fp2_sub()

void fp2_sub	(	fp2_t *	output,
		fp2_t	input_a,
		fp2_t	input_b )

Definition at line 16 of file fp2.c.

                                                          {
    fp_sub(output->re, input_a.re, input_b.re);
    fp_sub(output->im, input_a.im, input_b.im);
}

References fp_sub, fp2_t::im, and fp2_t::re.

fp2_to_bytes()

void fp2_to_bytes	(	uint8_t *	output,
		fp2_t	input )

Definition at line 131 of file fp2.c.

                                                {
    fp2_t t;
 
    fp2_from_mont(&t, input);
    memcpy(output, t.re, FIELD_BYTES);
    memcpy(&output[FIELD_BYTES], t.im, FIELD_BYTES);
}

References FIELD_BYTES, fp2_from_mont(), fp2_t::im, and fp2_t::re.

Here is the call graph for this function:

fp2_to_mont()

void fp2_to_mont	(	fp2_t *	output,
		fp2_t	input )

Definition at line 113 of file fp2.c.

                                             {
    fp_to_mont(output->re, input.re);
    fp_to_mont(output->im, input.im);
}

References fp_to_mont(), fp2_t::im, and fp2_t::re.

Referenced by fp2_element_from_bytes().

Here is the call graph for this function:

Here is the caller graph for this function: