Click or drag to resize
gmp_libmpn_gcdext Method (mp_ptr, mp_ptr, mp_size_t, mp_ptr, mp_size_t, mp_ptr, mp_size_t)
Compute the greatest common divisor G of U and V. Compute a cofactor S such that G = US + VT.

Namespace:  Math.Gmp.Native
Assembly:  Math.Gmp.Native (in Math.Gmp.Native.dll) Version: 1.0.0.0 (1.0.0.0)
Syntax
public static mp_size_t mpn_gcdext(
	mp_ptr gp,
	mp_ptr sp,
	ref mp_size_t sn,
	mp_ptr up,
	mp_size_t un,
	mp_ptr vp,
	mp_size_t vn
)

Parameters

gp
Type: Math.Gmp.Nativemp_ptr
The fisrt result operand.
sp
Type: Math.Gmp.Nativemp_ptr
The second result operand.
sn
Type: Math.Gmp.Nativemp_size_t
Pointer to the number of limbs of sp.
up
Type: Math.Gmp.Nativemp_ptr
The first operand integer.
un
Type: Math.Gmp.Nativemp_size_t
The number of limbs of up.
vp
Type: Math.Gmp.Nativemp_ptr
The second operand integer.
vn
Type: Math.Gmp.Nativemp_size_t
The number of limbs of vp.

Return Value

Type: mp_size_t
The number of limbs of gp.
Remarks

Let U be defined by {up, un} and let V be defined by {vp, vn}.

The second cofactor T is not computed but can easily be obtained from (G - U * S) / V (the division will be exact). It is required that unvn > 0, and the most significant limb of {vp, vn} must be non-zero.

Store G at gp and let the return value define its limb count. Store S at sp and let | sn.Value | define its limb count. S can be negative; when this happens sn.Value will be negative. The area at gp should have room for vn limbs and the area at sp should have room for vn + 1 limbs.

Both source operands are destroyed.

Compatibility notes: GMP 4.3.0 and 4.3.1 defined S less strictly. Earlier as well as later GMP releases define S as described here. GMP releases before GMP 4.3.0 required additional space for both input and output areas. More precisely, the areas {up, un + 1} and {vp, vn + 1} were destroyed (i.e. the operands plus an extra limb past the end of each), and the areas pointed to by gp and sp should each have room for un + 1 limbs.

Examples
// Create multi-precision operands, and expected result.
mp_ptr up = new mp_ptr(new uint[] { 0x40000000, 0x00000000 });
mp_ptr vp = new mp_ptr(new uint[] { 0x00000000, 0x00000001 });
mp_ptr gp = new mp_ptr(new uint[vp.Size * (IntPtr.Size / 4)]);
mp_ptr sp = new mp_ptr(new uint[(vp.Size + 1) * (IntPtr.Size / 4)]);
mp_ptr result = new mp_ptr(new uint[] { 0x40000000, 0x00000000 });
mp_ptr cofactor = new mp_ptr(new uint[] { 0x00000001, 0x00000000, 0x00000000 });

// Set gp = gcd(up, vp).
mp_size_t sn = 0;
mp_size_t size = gmp_lib.mpn_gcdext(gp, sp, ref sn, up, up.Size, vp, vp.Size);

// Assert result.
Assert.IsTrue(size == 1);
Assert.IsTrue(gp.SequenceEqual(result));
Assert.IsTrue(sn == 1);
Assert.IsTrue(sp.SequenceEqual(cofactor));

// Release unmanaged memory.
gmp_lib.free(gp, up, vp, sp, result, cofactor);
See Also