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.

template<class Array >
Rep &	prim_root_of_prime (Rep &A, const Array &Lf, const Rep &phin, const Rep &n) const
	Add Jacobi for quadratic nonresidue.

Rep &	probable_prim_root (Rep &, double &, const Rep &n, const uint64_t L=10000000_ui64) const
	Polynomial-time generation of primitive roots. More...

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. More...

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.

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. More...

std::istream &	read (std::istream &is) const
	Read field. More...

Arithmetic Operations
The first argument is set and is also the return value.
Element &	mul (Element &x, const Element &y, const Element &z) const
	x := y*z

Element &	div (Element &x, const Element &y, const Element &z) const
	x := y/z

Element &	mod (Element &x, const Element &y, const Element &z) const
	x := y mod z

Element &	add (Element &x, const Element &y, const Element &z) const
	x := y + z

Element &	sub (Element &x, const Element &y, const Element &z) const
	x := y - z

Element &	axpy (Element &z, const Element &a, const Element &x, const Element &y) const
	z := a*x + y

Element &	maxpy (Element &z, const Element &a, const Element &x, const Element &y) const
	z := y - a*x

Element &	maxpyin (Element &z, const Element &a, const Element &x) const
	z := z - a*x

Element &	axmy (Element &z, const Element &a, const Element &x, const Element &y) const
	z := a*x - y

Element &	axpyin (Element &z, const Element &a, const Element &x) const
	z := a*x + z

Element &	axmyin (Element &z, const Element &a, const Element &x) const
	z := a*x - z

Element &	neg (Element &x, const Element &y) const
	x := -y

Element &	inv (Element &x, const Element &y) const
	x := 1/y

Inplace Arithmetic Operations
The first argument is modified and the result is the return value.
Element &	mulin (Element &x, const Element &y) const
	x := x*y

Element &	divin (Element &x, const Element &y) const
	x := x/y

Element &	modin (Element &x, const Element &y) const
	x := x mod y

Element &	addin (Element &x, const Element &y) const
	x := x + y

Element &	subin (Element &x, const Element &y) const
	x := x - y

Element &	negin (Element &x) const
	x := -x

Element &	invin (Element &x) const
	x := 1/x

Comparison Predicates
bool	areEqual (const Element &x, const Element &y) const
	x == y

Detailed Description

template<class MyRandIter = GivRandom>
class Givaro::IntNumTheoDom< MyRandIter >

Num theory Domain.

Member Function Documentation

◆ probable_prim_root()

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()

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()

std::ostream& write	(	std::ostream &	os,
		std::string	F
	)		const

inlineinherited

Read field.

Returns: input stream from which field is read.

Parameters

is	input stream from which field is read.

◆ read()

std::istream& read ( std::istream & is ) const