/usr/include/givaro/givintnumtheo.h is in libgivaro-dev 4.0.2-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | // =================================================================== //
// Copyright(c)'1994-2009 by The Givaro group
// This file is part of Givaro.
// Givaro is governed by the CeCILL-B license under French law
// and abiding by the rules of distribution of free software.
// see the COPYRIGHT file for more details.
//
// Time-stamp: <16 Jun 15 16:05:31 Jean-Guillaume.Dumas@imag.fr>
// =================================================================== //
/*! @file givintnumtheo.h
* @ingroup integers
* @brief num theory.
* - Euler's phi function
* - Primitive roots
* - RSA scheme.
* .
*/
#ifndef __GIVARO_numtheory_H
#define __GIVARO_numtheory_H
#include <iostream>
#include "givaro/givinteger.h"
#include "givaro/givintprime.h"
#include "givaro/givintfactor.h"
#include "givaro/givrandom.h"
#include "givaro/udl.h"
namespace Givaro {
//! Num theory Domain.
template<class MyRandIter = GivRandom>
class IntNumTheoDom : public IntFactorDom<MyRandIter> {
public:
typedef IntFactorDom<MyRandIter> Father_t;
typedef typename IntFactorDom<MyRandIter>::Rep Rep;
IntNumTheoDom(MyRandIter g = MyRandIter())
: IntFactorDom<MyRandIter>(g) {}
// =================================================================== //
//! Euler's phi function
// =================================================================== //
template <template <class, class> class Container, template<class> class Alloc>
Rep& phi(Rep& res, const Container<Rep, Alloc<Rep> >& Lf, const Rep& n) const ;
Rep& phi(Rep& r, const Rep& n) const ;
// =================================================================== //
//! Primitive Root
// =================================================================== //
Rep& prim_root(Rep&, const Rep&) const ;
Rep& prim_root(Rep&, uint64_t&, const Rep&) const ;
Rep& prim_root_of_prime(Rep&, const Rep&) const ;
template<class Array> Rep& prim_root_of_prime(Rep& A, const Array& Lf, const Rep& phin, const Rep& n) 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.
*/
Rep& probable_prim_root(Rep&, double&, const Rep& n, const uint64_t L = 10000000_ui64) const;
//! Here L is computed so that the error is close to epsilon
Rep& probable_prim_root(Rep&, double&, const Rep& n, const double epsilon) const;
Rep& lowest_prim_root(Rep&, const Rep&) const ;
bool is_prim_root(const Rep&, const Rep&) const ;
Rep& order(Rep&, const Rep&, const Rep&) const ;
bool isorder(const Rep&, const 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
*
* 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
*/
// =================================================================== //
Rep& prim_inv(Rep & , const Rep&) const ;
Rep& prim_elem(Rep & , const Rep&) const ;
private:
Rep& prim_base(Rep & , const Rep&) const ;
Rep& lambda_base(Rep & , const Rep&) const ;
public:
Rep& lambda_primpow(Rep & , const Rep&, uint64_t) const ;
Rep& lambda_inv_primpow(Rep & , const Rep&, uint64_t) const ;
Rep& lambda(Rep & , const Rep&) const ;
Rep& lambda_inv(Rep & , const Rep&) const ;
// =================================================================== //
//! Möbius function
// =================================================================== //
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;
};
} // givaro
#include "givaro/givintnumtheo.inl"
#endif // __GIVARO_numtheory_H
// vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s
|