big_int.h

/*
**  UICore
**  Copyright (c) 1997-2015 The UICore Team
**
**  This software is provided 'as-is', without any express or implied
**  warranty.  In no event will the authors be held liable for any damages
**  arising from the use of this software.
**
**  Permission is granted to anyone to use this software for any purpose,
**  including commercial applications, and to alter it and redistribute it
**  freely, subject to the following restrictions:
**
**  1. The origin of this software must not be misrepresented; you must not
**     claim that you wrote the original software. If you use this software
**     in a product, an acknowledgment in the product documentation would be
**     appreciated but is not required.
**  2. Altered source versions must be plainly marked as such, and must not be
**     misrepresented as being the original software.
**  3. This notice may not be removed or altered from any source distribution.
**
**  Note: Some of the libraries UICore may link to may have additional
**  requirements or restrictions.
**
**  File Author(s):
**
**    Mark Page
**    Michael J. Fromberger
*/

// This class is based on the original MPI library (not NSS, because of license restrictions) with some modifications.
// Some ideas and algorithms are from NSS (Netscape Security Suite). Where they have been used, the function contains a reference note
//
// Note, since September 2011, I believe the MPI homepage is now: http://spinning-yarns.org/michael/mpi/
// Note, since 2013, the MPI page no longer exists, however the internet archive has the details here: http://web.archive.org/web/20100426001741/http://spinning-yarns.org/michael/mpi/README
// The license is as follows
// This software was written by Michael J. Fromberger,
//   http://www.dartmouth.edu/~sting/
//
// See the MPI home page at
//   http://www.dartmouth.edu/~sting/mpi/
//
// This software is in the public domain.  It is entirely free, and you
// may use it and/or redistribute it for whatever purpose you choose;
// however, as free software, it is provided without warranty of any
// kind, not even the implied warranty of merchantability or fitness for
// a particular purpose.


#pragma once

#include <cstdint>
#include <memory>

namespace uicore
{
    class BigInt_Impl;

    class BigInt
    {
    public:
        BigInt();

        explicit BigInt(uint32_t value);

        explicit BigInt(int32_t value);

        explicit BigInt(uint64_t value);

        explicit BigInt(int64_t value);

        BigInt(const BigInt &other);

        ~BigInt();

        BigInt &operator=(const BigInt& other);

        void read_unsigned_octets(const unsigned char *input_str, unsigned int input_length);

        void zero();

        bool make_prime(unsigned int num_bits);

        int cmp_z() const;

        void set_bit(unsigned int bit_number, unsigned int value);

        int significant_bits() const;

        void sieve(const uint32_t *primes, unsigned int num_primes, std::vector<unsigned char> &sieve);

        uint32_t mod_d(uint32_t d) const;

        void div_d(uint32_t d, BigInt *q, uint32_t *r) const;

        bool fermat(uint32_t w) const;

        bool pprime(int nt) const;

        void set(int32_t d);
        void set(uint32_t d);
        void set(uint64_t d);
        void set(int64_t d);

        void get(uint32_t &d);
        void get(uint64_t &d);
        void get(int64_t &d);
        void get(int32_t &d);

        void exptmod(const BigInt *b, const BigInt *m, BigInt *c) const;

        void mod(const BigInt *m, BigInt *c) const;

        void div(const BigInt &b, BigInt *q, BigInt *r) const;
        void div(uint32_t d, BigInt *q, BigInt *r) const;

        BigInt operator + (const BigInt& b);
        BigInt operator + (uint32_t d);

        BigInt operator += (const BigInt& b);
        BigInt operator += (uint32_t d);

        BigInt operator - (const BigInt& b);
        BigInt operator - (uint32_t d);

        BigInt operator -= (const BigInt& b);
        BigInt operator -= (uint32_t d);

        BigInt operator * (const BigInt& b);
        BigInt operator * (uint32_t d);

        BigInt operator *= (const BigInt& b);
        BigInt operator *= (uint32_t d);

        BigInt operator / (const BigInt& b);
        BigInt operator / (uint32_t d);

        BigInt operator /= (const BigInt& b);
        BigInt operator /= (uint32_t d);

        BigInt operator % (const BigInt& b);
        BigInt operator % (uint32_t d);

        BigInt operator %= (const BigInt& b);
        BigInt operator %= (uint32_t d);

        int cmp(const BigInt *b) const;

        int cmp_d(uint32_t d) const;

        void neg(BigInt *b) const;

        unsigned int trailing_zeros() const;

        void sqrmod(const BigInt *m, BigInt *c) const;
        void sqr(BigInt *b) const;

        void random();

        void exch(BigInt *mp2);

        bool invmod(const BigInt *m, BigInt *c) const;

        void xgcd(const BigInt *b, BigInt *g, BigInt *x, BigInt *y) const;

        void abs(BigInt *b) const;

        bool is_even() const;

        bool is_odd() const;

        void div_2(BigInt *c) const;

        void to_unsigned_octets(unsigned char *output_str, unsigned int output_length) const;

        int unsigned_octet_size() const;

    private:
        std::unique_ptr<BigInt_Impl> impl;
    };
}