4.9.2 Number theoretic functions

uint32 gcd (unsigned long a, unsigned long b)

cl_I gcd (const cl_I& a, const cl_I& b)

This function returns the greatest common divisor of a and b, normalized to be >= 0.

cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v)

This function (“extended gcd”) returns the greatest common divisor g of a and b and at the same time the representation of g as an integral linear combination of a and b: u and v with u*a+v*b = g, g >= 0. u and v will be normalized to be of smallest possible absolute value, in the following sense: If a and b are non-zero, and abs(a) != abs(b), u and v will satisfy the inequalities abs(u) <= abs(b)/(2*g), abs(v) <= abs(a)/(2*g).

cl_I lcm (const cl_I& a, const cl_I& b)

This function returns the least common multiple of a and b, normalized to be >= 0.

bool logp (const cl_I& a, const cl_I& b, cl_RA* l)

bool logp (const cl_RA& a, const cl_RA& b, cl_RA* l)

a must be > 0. b must be >0 and != 1. If log(a,b) is rational number, this function returns true and sets *l = log(a,b), else it returns false.

int jacobi (signed long a, signed long b)

int jacobi (const cl_I& a, const cl_I& b)

Returns the Jacobi symbol (a/b), a,b must be integers, b>0 and odd. The result is 0 iff gcd(a,b)>1.

bool isprobprime (const cl_I& n)

Returns true if n is a small prime or passes the Miller-Rabin primality test. The probability of a false positive is 1:10^30.

cl_I nextprobprime (const cl_R& x)

Returns the smallest probable prime >=x.

This document was generated on August 27, 2013 using texi2html 5.0.