Team-Fly
Previous Section Next Section

B.10 Number-Theoretic Friend Functions

const unsigned
ld (const LINT& a);

return ⌊log2(a)⌋ 

const int
iseven (const LINT& a);

test a for divisibility by 2: true if a even

 

const int
isodd (const LINT& a);

test a for divisibility by 2: true if a odd

 

const LINT
issqr (const LINT& a);

test a for being a square

 

const int
isprime (const LINT& a);

test a for primality

 

const LINT
gcd (const LINT& a,
     const LINT& b);

return gcd of a and b 

const LINT
xgcd (const LINT& a,
     const LINT& b,
     LINT& u, int& sign_u,
     LINT& v, int& sign_v);

extended Euclidean algorithm with return of gcd of a and b, u and v contain the absolute values of the factors of the linear combination g = sign_u*u*a + sign_v*v*b 

const LINT
inv (const LINT& a,
     const LINT& b);

return the multiplicative inverse of a mod b 

const LINT
lcm (const LINT& a,
     const LINT& b);

return the least common multiple of a and b 

const int
jacobi (const LINT& a,
     const LINT& b);

return the Jacobi symbol ()

 

const LINT
root (const LINT& a);

return the integer part of the square root of a 

const LINT
root (const LINT& a,
     const LINT& p);

return the square root of a modulo an odd prime p 

const LINT
root (const LINT& a,
     const LINT& p,
     const LINT& q);

return the square root of a modulo p*q for p and q odd primes

 

const LINT
chinrem (const unsigned
     noofeq, LINT** coeff);

return a solution of a system of simultaneous linear congruences. In coeff is passed a vector of pointers to LINT objects as coefficients a1, m1, a2, m2, a3, m3, ... of the congruence system with noofeq equations x ≡ ai mod mi 

const LINT
primroot (const unsigned
     noofprimes,
     LINT** primes);

return a primitive root modulo p. In noofprimes is passed the number of distinct prime factors of the group order p − 1, in primes a vector of pointers to LINT objects, beginning with p − 1, then come the prime divisors p1,...,pk of the group order p − 1 = with k = noofprimes 

const int
twofact (const LINT& even,
    LINT& odd);

return the even part of a, odd contains the odd part of a 

const LINT
findprime (const USHORT l);

return a prime p of length l bits, i.e., 2l−1 ≤ p < 2l 

const LINT
findprime (const USHORT l,
     const LINT& f);

return a prime p of length l bits, i.e., 2l−1 ≤ p < 2l and gcd(p − 1, f) = 1, f odd

 

const LINT
findprime (const LINT& pmin,
     const LINT& pmax,
     const LINT& f);

return a prime p with pmin ≤ p ≤ pmax and gcd(p − 1, f) = 1, f odd

 

const LINT
nextprime (const LINT& a,
     const LINT& f);

return the smallest prime p above a with gcd(p − 1, f) = 1, f odd

 

const LINT
extendprime (const USHORT l,
     const LINT& a,
     const LINT& q,
     const LINT& f);
const LINT
extendprime (const LINT& pmin,
const LINT& pmax,
     const LINT& a,
     const LINT& q,
     const LINT& f);

return a prime p of length l bits, i.e., 2l−1 ≤ p < 2l, with p ≡ a mod q and gcd(p − 1, f) = 1, f odd

return a prime p with pmin ≤ p ≤ pmax, with p ≡ a mod q and gcd(p − 1, f) = 1, f odd

 

const LINT
strongprime (const USHORT l);

return a strong prime p of length l bits, i.e., 2l−1 ≤ p < 2l 

const LINT
strongprime (const USHORT l,
     const LINT& f);

return a strong prime p of length l bits, i.e., 2l−1 ≤ p < 2l, with gcd(p − 1, f) = 1, f odd

 

const LINT
strongprime (const USHORT l,
     const USHORT lt,
     const USHORT lr,
     const USHORT ls,
     const LINT& f);

return a strong prime p of length l bits, i.e., 2l−1 ≤ p < 2l, with gcd(p − 1, f) = 1, f odd lt , ls ≈ lr of length of p 

const LINT
strongprime (const LINT& pmin,
     const LINT& pmax,
     const LINT& f);

return a strong prime p with pmin ≤ p ≤ pmax, gcd(p − 1, f) = 1, f odd, default lengths lr, lt, ls of prime divisors r of p − 1, t of r−1, s of p+1:lt , ls ≈ lr of the binary length of pmin 

const LINT
strongprime (const LINT& pmin,
     const LINT& pmax,
     const USHORT lt,
     const USHORT lr,
     const USHORT ls,
     const LINT& f);

return a strong prime p with pmin ≤ p ≤ pmax, gcd(p − 1, f) = 1, f odd, lengths lr, lt, ls of prime divisors r of p − 1, t of r − 1, s of p + 1
Team-Fly Previous Section Next Section