manpagez: man pages & more
info cln
Home | html | info | man
 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

### 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`.

 [ << ] [ < ] [ Up ] [ > ] [ >> ] [Top] [Contents] [Index] [ ? ]

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

```© manpagez.com 2000-2018