Givaro
IntNumTheoDom< MyRandIter > Class Template Referenceabstract

Num theory Domain. More...

#include <givintnumtheo.h>

+ Inheritance diagram for IntNumTheoDom< MyRandIter >:
+ Collaboration diagram for IntNumTheoDom< MyRandIter >:

Public Member Functions

template<template< class, class > class Container, template< class > class Alloc>
Rep & phi (Rep &res, const Container< Rep, Alloc< Rep > > &Lf, const Rep &n) const
 Euler's phi function.
 
Rep & prim_root (Rep &, const Rep &) const
 Primitive Root.
 
Rep & probable_prim_root (Rep &, double &, const Rep &n, const uint64_t L=10000000_ui64) const
 Polynomial-time generation of primitive roots.
 
Rep & probable_prim_root (Rep &, double &, const Rep &n, const double epsilon) const
 Here L is computed so that the error is close to epsilon.
 
Rep & prim_inv (Rep &, const Rep &) const
 Generalization of primitive roots for any modulus Primitive means maximal order Primitive Element, Primitive invertible Both functions coincide except for m=8.
 
template<template< class, class > class Container, template< class > class Alloc>
short mobius (const Container< Rep, Alloc< Rep > > &lpow) const
 Möbius function.
 
short mobius (const Rep &a) const
 Möbius function.
 
template<class Array >
IntNumTheoDom< MyRandIter >::Rep & prim_root_of_prime (Rep &A, const Array &aLf, const Rep &phin, const Rep &n) const
 Add Jacobi for quadratic nonresidue.
 
bool set (Container1 &setint, Container2 &setpwd, const Rep &a, unsigned long loops=0) const
 Factors with primes.
 
Rep & Erathostene (Rep &, const Rep &p) const
 returns a small factor
 
bool isUnit (const Rep &x) const
 isUnit
 
bool isDivisor (const Element &a, const Element &b) const
 isDivisor (a, b) Test if b | a.
 
Input/Output Operations
std::ostream & write (std::ostream &os, std::string F) const
 Read field.
 
std::ostream & write (std::ostream &os, const Element &x) const
 Print field element.
 
std::istream & read (std::istream &is) const
 Read field.
 
virtual std::istream & read (std::istream &is, Element &x) const
 Read field element.
 
Arithmetic Operations

The first argument is set and is also the return value.

Elementmul (Element &x, const Element &y, const Element &z) const
 x := y*z
 
Elementdiv (Element &x, const Element &y, const Element &z) const
 x := y/z
 
Elementmod (Element &x, const Element &y, const Element &z) const
 x := y mod z
 
Elementadd (Element &x, const Element &y, const Element &z) const
 x := y + z
 
Elementsub (Element &x, const Element &y, const Element &z) const
 x := y - z
 
Elementaxpy (Element &z, const Element &a, const Element &x, const Element &y) const
 z := a*x + y
 
Elementmaxpy (Element &z, const Element &a, const Element &x, const Element &y) const
 z := y - a*x
 
Elementmaxpyin (Element &z, const Element &a, const Element &x) const
 z := z - a*x
 
Elementaxmy (Element &z, const Element &a, const Element &x, const Element &y) const
 z := a*x - y
 
Elementaxpyin (Element &z, const Element &a, const Element &x) const
 z := a*x + z
 
Elementaxmyin (Element &z, const Element &a, const Element &x) const
 z := a*x - z
 
Elementneg (Element &x, const Element &y) const
 x := -y
 
Elementinv (Element &x, const Element &y) const
 x := 1/y
 
Inplace Arithmetic Operations

The first argument is modified and the result is the return value.

Elementmulin (Element &x, const Element &y) const
 x := x*y
 
Elementdivin (Element &x, const Element &y) const
 x := x/y
 
Elementmodin (Element &x, const Element &y) const
 x := x mod y
 
Elementaddin (Element &x, const Element &y) const
 x := x + y
 
Elementsubin (Element &x, const Element &y) const
 x := x - y
 
Elementnegin (Element &x) const
 x := -x
 
Elementinvin (Element &x) const
 x := 1/x
 
Comparison Predicates
bool areEqual (const Element &x, const Element &y) const
 x == y
 
Data Object Management.

first argument is set and the value is also returned.

Detailed Description

Member Function Documentation

◆ probable_prim_root()

template<class MyRandIter >
IntNumTheoDom< MyRandIter >::Rep & probable_prim_root ( Rep & primroot,
double & error,
const Rep & n,
const uint64_t L = 10000000_ui64 ) const

Polynomial-time generation of primitive roots.

L is number of loops of Pollard partial factorization of n-1 10,000,000 gives at least 1-2^{-40} probability of success [Dubrois & Dumas, Industrial-strength primitive roots] Returns the probable primitive root and the probability of error.

◆ prim_inv()

template<class MyRandIter >
IntNumTheoDom< MyRandIter >::Rep & prim_inv ( Rep & A,
const Rep & n ) const

Generalization of primitive roots for any modulus Primitive means maximal order Primitive Element, Primitive invertible Both functions coincide except for m=8.

Lambda Function : maximal orbit size lambda : Order of a primitive Element lambda_inv : Order of an invertible primitive Element Both functions coincide except for m=8

◆ write() [1/2]

template<class _Element >
std::ostream & write ( std::ostream & os,
std::string F ) const
inlineinherited

Read field.

Returns
input stream from which field is read.
Parameters
isinput stream from which field is read.

◆ write() [2/2]

template<class _Element >
std::ostream & write ( std::ostream & os,
const Element & x ) const
inlineinherited

Print field element.

Returns
output stream to which field element is written.
Parameters
osoutput stream to which field element is written.
xfield element.

◆ read() [1/2]

template<class _Element >
std::istream & read ( std::istream & is) const
inlineinherited

Read field.

Returns
input stream from which field is read.
Parameters
isinput stream from which field is read.

◆ read() [2/2]

template<class _Element >
virtual std::istream & read ( std::istream & is,
Element & x ) const
inlinevirtualinherited

Read field element.

Returns
input stream from which field element is read.
Parameters
isinput stream from which field element is read.
xfield element.

The documentation for this class was generated from the following files: