ciperlib.h

关于大数运算的加 减 乘 除 模 等运算 运用了libtommath库的算法

/*
    Big Integer Operation
    HEADER FILE
    BY CSK(陈士凯)
    [e-mail]
    www.csksoft.net


*/


#pragma once

#ifndef CIPER_LIB_H
#define CIPER_LIB_H



class ZModn;
class IntHelper;
class Integer
{
/*
    STATIC AREA 
*/
friend class ZModn;
friend class IntHelper;
public:
    //Please call this function before any operation first!
    //otherwise this function will be automatically called with u_data_arr_num = 1024
    //This func can called by ONLY ONCE!
    static bool Init(unsigned int u_data_arr_num = 1024);
    

    //intend_op = 0 : add , 1: sub
    //this func judge whether to do adding or subing operation
    static void add_sub_director(Integer &src,  Integer &dest, unsigned int intend_op);

protected:

    static unsigned int ms_u_ref_cnt;//the number of instances
    static bool ms_b_inited;    //indicate whether the func Init was called
    static unsigned int ms_u_data_arr_num; //indicate the bits length of Integer, this value is set by Init

    //create memory for holding num data, the length of the buffer is ms_u_data_arr_num/32
    static void create_data_buf(Integer & i);

    //release the memory allocated by create_data_buf
    static void release_data_buf(Integer & i);
  
    //src += dest, assume src.sign = dest.sign
    static void raw_add(Integer &src, const Integer &dest);

    //src -= dest, assume src.sign = dest.sign
    static void raw_sub(Integer &src, const Integer &dest);
    
    //dest = left * right + dest
    static void raw_mul(const Integer &left, const Integer &right, Integer &dest);

    //dest = left / right
    //left = left mod right
    //if &dest = &left, only quotient returns
    //if &dest = &right, only reminder returns
    //return 0 if success
    //1: div by zero
    static int raw_div(Integer &left, Integer &right, Integer &dest);    


    static void raw_mul_int(Integer &left, unsigned int n, Integer &dest);

    static unsigned int raw_div_int(Integer &left, unsigned int n, Integer &dest);

    static int norm_divisor(Integer &left, Integer &right);
/*
    END OF STATIC AREA
*/
    //pointer to the buffer created by create_data_buf
    unsigned int *m_p_data_arr;

    //indicate the sign of current integer, 0 for positive, 1 for negative
    unsigned int  m_dw_sign;

    //current length of the integer, range for 1 to ms_u_data_arr_num
    unsigned int  m_acutual_len;

    //indicate whether this number is overflowed
    unsigned int  m_dw_isOverflow;

    //common init func
    void inner_init();
public:
//------Init func
    Integer();
    Integer(const Integer &); //create a new copy of Integer
    Integer(__int64);   //create from a 64-bit integer
    Integer(int);   //create from a 32-bit integer
    Integer(char *, unsigned int  = 10);   //create from string, the second argument indicate the base number
    //release func
    ~Integer();

//------convert
    //convert current integer value to string, 
    //max_buffer_size indicates the max buffer size of  strNum,
    //base indicate the base number, only 10 and 16 is valid
    bool toString(char *strNum, unsigned int max_buffer_size, unsigned int base = 10)  const;

    //parse integer value from string, base indicate the base number, only 10 and 16 is valid
    bool fromString(char *strNum, unsigned int base = 10);

    //parse integer from 64-bit buildin type
    void fromInt64(__int64);

    //parse integer from 32-bit buildin type
    void fromInt(int);
//------copy
    //make a new copy without affect the previous one 
    Integer & copyFrom(const Integer &);
//------operation
    //compare this and the argument
    // if this > argument , return 1
    // if this < argument , return -1
    // if this == argument , return 0
    int compare(const Integer &)  const;
    bool isZero() const;

    // make this = 0
    Integer& zero();
    
    //this += argu
    Integer& plus( Integer &);
    //this -= argu
    Integer& minus( Integer &);

    //dest = this * right
    Integer& mul(const Integer &right,Integer &dest);

 //   Integer& full_div(const Integer &right,Integer &dest);

    //dest = this / right
    Integer& div(const Integer &right);

    //dest = this mod right
    Integer& mod(const Integer &right);

    //set x=x.(base^n) 
    Integer& shift(int n);

//------operator
    Integer & operator= (const Integer &);
    
    int operator>(const Integer &) const;
    int operator<(const Integer &) const;
    int operator==(const Integer &) const;
    int operator!=(const Integer &) const;
    int operator>=(const Integer &) const;
    int operator<=(const Integer &) const;

    Integer & operator+=(const Integer &);
    Integer & operator+=(int);

    Integer & operator-=(const Integer &);
    Integer & operator-=(int);

    Integer & operator*=(const Integer &);
    Integer & operator*=(int);

    Integer & operator/=(const Integer &);
    Integer & operator/=(int);

    Integer & operator%=(const Integer &);
    Integer & operator%=(int);


    Integer  operator+(const Integer &);
    Integer  operator+(int);

    Integer  operator-(const Integer &);
    Integer  operator-(int);

    Integer  operator*(const Integer &);
    Integer  operator*(int);

    Integer  operator/(const Integer &);
    Integer  operator/(int);

    Integer  operator%(const Integer &);
    Integer  operator%(int);
};


class ZModn
{
protected:
    Integer m_mod_value;

    static unsigned int prime_array[];
    static bool is_prime_arr_inited;
    static void genPrimeArr();
public:
    //set the mod value of Zm
    //Call this func First!!!
     bool setMod( Integer&);
    

     //judge a prime using Rabin-Miller method
     static bool isPrime( Integer&);

     //generate a prime >= start_val
     static bool genPrime(Integer & start_val,Integer &  dest);

     //quick judge a Integer whether it is a prime
     //returns 0 means it is not a prime
     //        1 means it must be a prime
     //        2 means it may be a prime
     static int quickPrimeDec( Integer&);
    //A = A mod m_mod_value
     Integer & toMod(Integer& A);
    //B = A + B (mod m_mod_value)
     Integer & mod_add(Integer& A, Integer& B);
    //B = A * B (mod m_mod_value)
     Integer & mod_mul(Integer&, Integer& );
    //A = A^N (mod m_mod_value)
     Integer & mod_pow(Integer& A, Integer& N);
    
     Integer & Euc(Integer&, Integer&);
};

class IntHelper
{

private:
    //used for Marsaglia & Zaman's algorithm
    static unsigned int rnd_seeds[];
    static unsigned int rnd_carry_flag;
    static int rnd_pos;

public:
    //returns number of bits
    static int logb2(const Integer&);

    //returns the sliding windows's value
    static int sliding_window(const Integer& ,int ,int *,int * ,int );

    //get the n-bits' value
    static int testbit(const Integer& x,unsigned int n);

    //using Marsaglia & Zaman's method to generation long period random number

    static void MZ_seed(unsigned int seed);

    static unsigned int MZ_rand();
};

#endif