NTTL Function - Inverse

Description

Compute the modular inverse of a number.

Header

<nttl/inverse.h>

Signature

template< class T >
T Inverse( const T& x, const T& modulus )

Parameters

Name	Type	Description
x	T	The number for which to find the inverse.
modulus	T	The modulus (duh!).

Returns

( T )  The inverse of x mod modulus

Example

#include <nttl/inverse.h> ... long i = Inverse( 10, 23 );

Algorithm

The algorithm used here is digusting.  It needs to be replaced with something more efficient.

Notes

This function does not handle negative number properly.  Consider using EGCD, instead.