Givaro
|
Num theory Domain. More...
#include <givintnumtheo.h>
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 coïncides 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. | |
Num theory Domain.
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.
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 coïncides 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 coïncides except for m=8