fp.h File Reference

#include <stdint.h>
#include "rng.h"
#include "parameters.h"

Include dependency graph for fp.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef uint64_t	fp_t[FIELD_64BITS_WORDS]

Functions
void	fp_add (uint64_t *output, const uint64_t *input_a, const uint64_t *input_b)
void	fp_sub (uint64_t *output, const uint64_t *input_a, const uint64_t *input_b)
void	fp_mul (uint64_t *output, const uint64_t *input_a, const uint64_t *input_b)
void	fp_sqr (uint64_t *output, const uint64_t *input_a)
void	fp_neg (fp_t output, const fp_t input)
void	fp_set_to_one (fp_t output)
void	fp_set_to_zero (fp_t output)
void	fp_copy (fp_t output, const fp_t input)
void	fp_cset (fp_t output, const fp_t input, uint64_t input_mask)
void	fp_cswap (fp_t input_a, fp_t input_b, uint64_t input)
void	fp_sample (fp_t output)
void	fp_inv (fp_t output, const fp_t input)
void	fp_half (fp_t output, const fp_t input)
void	fp_to_mont (fp_t output, const fp_t input)
void	fp_from_mont (fp_t output, const fp_t input)
int64_t	fp_is_zero (const fp_t input)
uint8_t	fp_is_equal (const fp_t input_a, const fp_t input_b)
uint8_t	fp_is_smaller (const fp_t input1, const fp_t input2)
uint8_t	fp_is_square (const fp_t input)
void	fp_sqrt (fp_t output, const fp_t input)
void	fp_curt (fp_t output, const fp_t input)

Typedef Documentation

fp_t

typedef uint64_t fp_t[FIELD_64BITS_WORDS]

Definition at line 12 of file fp.h.

Function Documentation

fp_add()

void fp_add ( uint64_t *  output, const uint64_t *  input_a, const uint64_t *  input_b  )

extern

fp_copy()

void fp_copy	(	fp_t	output,
		const fp_t	input
	)

Definition at line 24 of file fp.c.

                                            {
    memcpy(output, input, sizeof(fp_t));
}

fp_cset()

void fp_cset	(	fp_t	output,
		const fp_t	input,
		uint64_t	input_mask
	)

Definition at line 28 of file fp.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[i] ^ input[i]);
        output[i] = temp ^ output[i];
    }
}

References FIELD_64BITS_WORDS, and i.

Referenced by isogeny_walks_3_fp(), and isogeny_walks_get_points_3_fp().

Here is the caller graph for this function:

fp_cswap()

void fp_cswap	(	fp_t	input_a,
		fp_t	input_b,
		uint64_t	input
	)

Definition at line 39 of file fp.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[i] ^ input_b[i]);
        input_a[i] = temp ^ input_a[i];
        input_b[i] = temp ^ input_b[i];
    }
}

References FIELD_64BITS_WORDS, and i.

fp_curt()

void fp_curt	(	fp_t	output,
		const fp_t	input
	)

Definition at line 189 of file fp.c.

                                            {
    fp_t temp, input_1;
    uint64_t flag;
    int i, j;
    // input_1 <- input ^ -([p - 2] / 3)
    fp_set_to_one(input_1);
    fp_copy(temp, input);
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        flag = 1;
        for (j = 0; j < 64; j++) {
            if ((flag & CUBE_ROOT_EXPONENT_213[i]) != 0)
                fp_mul(input_1, temp, input_1);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
    fp_copy(output, input_1);
}

References FIELD_64BITS_WORDS, fp_copy, fp_mul, fp_set_to_one(), fp_sqr, i, and j.

Referenced by isogeny_walks_get_points_3_fp(), isogeny_walks_get_points_3_fp(), isogeny_walks_to_montgomery_model_3_fp(), and isogeny_walks_to_montgomery_model_3_fp().

Here is the call graph for this function:

Here is the caller graph for this function:

fp_from_mont()

void fp_from_mont	(	fp_t	output,
		const fp_t	input
	)

Definition at line 104 of file fp.c.

                                                 {
    fp_t one = {0};
    one[0] = 1;
    fp_mul(output, input, one);
}

References fp_mul.

Referenced by fp2_from_mont().

Here is the caller graph for this function:

fp_half()

void fp_half	(	fp_t	output,
		const fp_t	input
	)

Definition at line 84 of file fp.c.

                                            {
    uint8_t carry = 0;
    int i;
    uint64_t mask;
 
    mask = 0 - (uint64_t) (input[0] & 1);
    // If a is odd compute a + p
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        addition_with_carry_u64(output[i], carry, carry, input[i], FIELD_CHARACTERISTIC[i] & mask);
    }
 
    multiprecision_shift_to_right(output, FIELD_64BITS_WORDS);
}

References addition_with_carry_u64, FIELD_64BITS_WORDS, i, and multiprecision_shift_to_right().

Referenced by fp2_half().

Here is the call graph for this function:

Here is the caller graph for this function:

fp_inv()

void fp_inv	(	fp_t	output,
		const fp_t	input
	)

Definition at line 62 of file fp.c.

                                           {
 
    fp_t temp, out;
    fp_set_to_one(out);
    fp_copy(temp, input);
 
    int i, j, k;
    uint64_t flag;
 
    for (i = 0, k = 0; i < FIELD_64BITS_WORDS && k < FIELD_BITS; i++, k++) {
        flag = 1;
        for (j = 0; j < 64; j++, k++) {
            if ((flag & FIELD_INVERSION_EXPONENT[i]) != 0)
                fp_mul(out, temp, out);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
    fp_copy(output, out);
}

References FIELD_64BITS_WORDS, FIELD_BITS, fp_copy, fp_mul, fp_set_to_one(), fp_sqr, i, and j.

Here is the call graph for this function:

fp_is_equal()

uint8_t fp_is_equal	(	const fp_t	input_a,
		const fp_t	input_b
	)

Definition at line 122 of file fp.c.

                                                            {
    int i;
    uint8_t r = 0;
    uint64_t t;
 
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        t = 0;
        uint8_t *ta = (uint8_t *) &input_a[i];
        uint8_t *tb = (uint8_t *) &input_b[i];
        t = (ta[0] ^ tb[0]) | (ta[1] ^ tb[1]) | (ta[2] ^ tb[2]) | (ta[3] ^ tb[3]) |
            (ta[4] ^ tb[4]) | (ta[5] ^ tb[5]) | (ta[6] ^ tb[6]) | (ta[7] ^ tb[7]);
 
        t = (-t);
        t = t >> 63;
        r |= t;
    }
 
    return (uint8_t) (1 - r);
}

References FIELD_64BITS_WORDS, and i.

Referenced by fp2_is_equal(), fp2_sqrt_fast(), fp2_sqrt_slow(), fp_is_square(), and isogeny_walks_get_points_3_fp().

Here is the caller graph for this function:

fp_is_smaller()

uint8_t fp_is_smaller	(	const fp_t	input1,
		const fp_t	input2
	)

Definition at line 143 of file fp.c.

                                                            {
    return multiprecision_is_smaller(input1, input2, FIELD_64BITS_WORDS);
}

References FIELD_64BITS_WORDS, and multiprecision_is_smaller().

Here is the call graph for this function:

fp_is_square()

uint8_t fp_is_square

(

const fp_t

input

)

Definition at line 148 of file fp.c.

                                       {
    fp_t temp, input_1;
    uint64_t flag;
    int i, j;
    // input_1 <- input ^ ([p - 1] / 2)
    fp_set_to_one(input_1);
    fp_copy(temp, input);
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        flag = 1;
        for (j = 0; j < 64; j++) {
            if ((flag & SQUARE_ROOT_EXPONENT_12[i]) != 0)   
                fp_mul(input_1, temp, input_1);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
 
    return fp_is_equal(input_1, MONTGOMERY_CONSTANT_ONE);
}

References FIELD_64BITS_WORDS, fp_copy, fp_is_equal(), fp_mul, fp_set_to_one(), fp_sqr, i, and j.

Referenced by fp2_is_square(), and isogeny_walks_get_points_3_fp().

Here is the call graph for this function:

Here is the caller graph for this function:

fp_is_zero()

int64_t fp_is_zero

(

const fp_t

input

)

Definition at line 112 of file fp.c.

                                     {
    int i;
    uint64_t output = 0;
    for (i = FIELD_64BITS_WORDS - 1; i >= 0; i--)
        output |= input[i];
 
    return ~(((int64_t)output >> 63) | (-(int64_t)output >> 63));
}

References FIELD_64BITS_WORDS, and i.

Referenced by fp2_is_zero(), and fp2_sqrt_slow().

Here is the caller graph for this function:

fp_mul()

void fp_mul ( uint64_t *  output, const uint64_t *  input_a, const uint64_t *  input_b  )

extern

fp_neg()

void fp_neg	(	fp_t	output,
		const fp_t	input
	)

Definition at line 9 of file fp.c.

                                           {
    fp_t zero = {0};
    fp_sub(output, zero, input);
}

References fp_sub.

Referenced by fp2_conj(), fp2_neg(), fp2_sqrt_fast(), isogeny_walks_get_points_3(), and isogeny_walks_get_points_3_fp().

Here is the caller graph for this function:

fp_sample()

void fp_sample

(

fp_t

output

)

Definition at line 51 of file fp.c.

                            {
    randombytes((uint8_t *) output, FIELD_BYTES);
    output[FIELD_64BITS_WORDS - 1] &= MASK_FIELD_ELEMENT;
    while (!multiprecision_is_smaller(output, FIELD_CHARACTERISTIC, FIELD_64BITS_WORDS)) {
        randombytes((uint8_t *) output, FIELD_BYTES);
        output[FIELD_64BITS_WORDS - 1] &= MASK_FIELD_ELEMENT;
    }
}

References FIELD_64BITS_WORDS, FIELD_BYTES, MASK_FIELD_ELEMENT, multiprecision_is_smaller(), and randombytes().

Here is the call graph for this function:

fp_set_to_one()

void fp_set_to_one

(

fp_t

output

)

Definition at line 14 of file fp.c.

                                      {
    fp_copy(input_output, MONTGOMERY_CONSTANT_ONE);
}

References fp_copy.

Referenced by fp2_set_to_one(), fp2_sqrt_fast(), fp2_sqrt_slow(), fp_curt(), fp_inv(), fp_is_square(), fp_sqrt(), isogeny_walks_3_fp(), and isogeny_walks_get_points_3().

Here is the caller graph for this function:

fp_set_to_zero()

void fp_set_to_zero

(

fp_t

output

)

Definition at line 19 of file fp.c.

                                       {
    memset(input_output, 0, sizeof(fp_t));
}

Referenced by fp2_set_to_one(), fp2_set_to_zero(), and fp2_sqrt_fast().

Here is the caller graph for this function:

fp_sqr()

void fp_sqr ( uint64_t *  output, const uint64_t *  input_a  )

extern

fp_sqrt()

void fp_sqrt	(	fp_t	output,
		const fp_t	input
	)

Definition at line 168 of file fp.c.

                                            {
    fp_t temp, input_1;
    uint64_t flag;
    int i, j;
    // input_1 <- input ^ ([p - 3] / 4)
    fp_set_to_one(input_1);
    fp_copy(temp, input);
    for (i = 0; i < FIELD_64BITS_WORDS; i++) {
        flag = 1;
        for (j = 0; j < 64; j++) {
            if ((flag & SQUARE_ROOT_EXPONENT_34[i]) != 0)
                fp_mul(input_1, temp, input_1);
            fp_sqr(temp, temp);
            flag <<= 1;
        }
    }
    fp_mul(output, input_1, input);
}

References FIELD_64BITS_WORDS, fp_copy, fp_mul, fp_set_to_one(), fp_sqr, i, and j.

Referenced by elligator(), isogeny_walks_get_points_3_fp(), and isogeny_walks_get_points_3_fp().

Here is the call graph for this function:

Here is the caller graph for this function:

fp_sub()

void fp_sub ( uint64_t *  output, const uint64_t *  input_a, const uint64_t *  input_b  )

extern

fp_to_mont()

void fp_to_mont	(	fp_t	output,
		const fp_t	input
	)

Definition at line 99 of file fp.c.

                                               {
    fp_mul(output, input, (uint64_t *) &MONTGOMERY_CONSTANT_R_SQUARED);
}

References fp_mul.

Referenced by fp2_to_mont().

Here is the caller graph for this function: