Program Listing for File NumberTheory.h

↰ Return to documentation for file (ADS/numeric/NumberTheory.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File NumberTheory.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_NumberTheory
 #define __ADS_NumberTheory
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/set/BoolSet.h"

#include <algorithm>
#include <array>
#include <bit>
#include <cstdint>
#include <random>
#include <stdexcept>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

using U64 = std::uint64_t;

inline U64 gcd( U64 s , U64 m );

[[nodiscard]] constexpr U64 binaryGcd( U64 a , U64 b );

inline std::tuple< long long , long long , long long > extendedEuclid(
                                                   long long s , long long m );

inline long long modInverse( long long s , long long m );

inline constexpr U64 kMersenne61 = ( U64( 1 ) << 61 ) - 1;

[[nodiscard]] constexpr U64 mulMod61( U64 a , U64 b );

[[nodiscard]] constexpr U64 mulMod( U64 a , U64 b , U64 m );

/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS Montgomery64 ----------------------------*/
/*--------------------------------------------------------------------------*/
class Montgomery64 {
 public:
 explicit constexpr Montgomery64( U64 n );

 [[nodiscard]] constexpr U64 modulus( void ) const { return( f_n ); }

 [[nodiscard]] constexpr U64 to( U64 x ) const;

 [[nodiscard]] constexpr U64 from( U64 x ) const { return( reduce( 0 , x ) ); }

 [[nodiscard]] constexpr U64 one( void ) const { return( f_one ); }

 [[nodiscard]] constexpr U64 mul( U64 a , U64 b ) const;

 [[nodiscard]] constexpr U64 pow( U64 x , U64 v ) const;

 private:
 [[nodiscard]] constexpr U64 reduce( U64 hi , U64 lo ) const;

 U64 f_n;
 U64 f_inv;
 U64 f_one;
 U64 f_r2;
 };  // end( class Montgomery64 )

inline U64 powMod( U64 x , U64 v , U64 m );

inline bool isPrimeTrial( U64 n );

inline bool witness( U64 n , U64 b );

template< class R >
bool millerRabin( U64 n , int K , R & rng );

inline bool isPrime( U64 n );

inline std::vector< U64 > sieve( U64 n );

inline std::vector< U64 > factorize( U64 n );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/numeric/impl/NumberTheory.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* NumberTheory.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File NumberTheory.h -------------------------*/
/*--------------------------------------------------------------------------*/