fr_inv.cu File Reference

#include "fr.cuh"
#include <stdio.h>

Include dependency graph for fr_inv.cu:

Go to the source code of this file.

Functions
__device__ void	fr_inv (fr_t &z)
	Calculates the multiplicative inverse of z, and stores back. More...

Function Documentation

fr_inv()

__device__ void fr_inv

(

fr_t &

z

)

Calculates the multiplicative inverse of z, and stores back.

Parameters

[in,out]

z

Returns

void

This function calculates the multiplicative inverse of the argument. An integer a is the inverse of z if a*z mod r == 1

Normally, the inverse is found by using the Extended Euclidean Algorithm, to find integers (z,y) to satisfy the Bézout's identity: a*z + r*y == gcd(a, r) == 1 which can be rewritten as: az-1 == (-y)*m which follows that a*z mod r == 1. This approach has complexity in the order of O(log2(r)).

This implementation uses Euler's theorem, calculating the inverse as z^(phi(r)-1). where phi is Euler's totient function. For the special case where r is prime, phi(r) = r-1. Therefore, the inverse here is calculated as z^(r-2). Although this is asymptotically worse than EEA, this implementation avoid flow divergence and uses 258 squarings and 55 multiplications. Furthermore, since curve operations are done in projective coordinates, inversions are needed only at the very end when projective coordinates are translated into affine coordinates.

Definition at line 33 of file fr_inv.cu.

Here is the call graph for this function: