Cryptography Reference
In-Depth Information
Function:
calculate the greatest common divisor of two
LINT
objects
Syntax:
LINT
LINT::gcd (const LINT& b);
implicit argument
a
second argument
b
Input:
gcd
(a, b)
of the input values
Return:
Example:
c = a.gcd (b);
calculate the multiplicative inverse modulo
n
Function:
LINT
LINT::inv (const LINT& n);
Syntax:
implicit argument
a
modulus
n
Input:
multiplicative inverse of
a
modulo
n
(if the result
is equal to zero, then
gcd(
a
,
n
)
>
1
and the inverse does not exist)
Return:
c = a.inv (n);
Example:
calculate the greatest common divisor of
a
and
b
as well as its representation
g = ua+vb
as a linear
combination of
a
and
b
Function:
Syntax:
LINT
LINT::xgcd(const LINT& b,
LINT& u, int& sign_u,
LINT& v, int& sign_v);
Input:
implicit argument
a
, second argument
b
Factor
u
of the representation of
gcd
(a, b)
sign of
u
in
sign_u
factor
v
of the representation of
gcd
(a, b)
sign of
v
in
sign_v
Output:
gcd(
a
,
b
)
of the input values
Return:
g = a.xgcd (b, u, sign_u, v, sign_v);
Example: