ringzp.h

Go to the documentation of this file.

/////////////////////////////////////////////////////////////////////////////
///
/// \file
///
/// Elements of the ring Z_p.
///
/////////////////////////////////////////////////////////////////////////////

// Copyright (C) 2009-2016 by Pawel Pilarczyk.
//
// This file is part of my research software package. This is free software:
// you can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this software; see the file "license.txt". If not,
// please, see <http://www.gnu.org/licenses/>.

// Started on March 24, 2009. Last revision: June 20, 2012.


#ifndef _CHAINCON_RINGZP_H_
#define _CHAINCON_RINGZP_H_


// include some standard C++ header files
#include <istream>
#include <ostream>
#include <sstream>
#include <string>

// include selected header files from the CHomP library
#include "chomp/system/config.h"


// --------------------------------------------------
// --------- selected features of integers ----------
// --------------------------------------------------

/// A collection of selected features of integer numbers.
template <class intType>
class IntFeatures
{
}; /* IntFeatures */

// --------------------------------------------------

/// Specific features of the type 'int'.
template <>
class IntFeatures<int>
{
public:
        /// The name of a twice longer integer type.
        typedef long LongerInt;

}; /* IntFeatures<int> */

// --------------------------------------------------

/// Specific features of the type 'short'.
template <>
class IntFeatures<short>
{
public:
        /// The name of a twice longer integer type.
        typedef int LongerInt;

}; /* IntFeatures<short> */

// --------------------------------------------------

/// Specific features of the type 'char' (use with caution!).
template <>
class IntFeatures<char>
{
public:
        /// The name of a twice longer integer type.
        typedef short LongerInt;

}; /* IntFeatures<char> */

// --------------------------------------------------

/// Inverts a number in the modulo 'p' arithmetic,
/// provided that 'p' is a prime number.
/// This procedure is good for large values of 'p'
/// and uses a longer type of integers for multiplication.
template <class intType>
intType invertModuloLargeP (const intType &n, const intType &q)
{
        if ((n == 1) || (n == (q - 1)))
                return n;

        typedef typename IntFeatures<intType>::LongerInt LongerInt;
        LongerInt result (1);
        LongerInt nLonger (n);
        intType i (q - 2);

        while (i)
        {
                if (i & 1)
                {
                        result = (result * nLonger) % q;
                        -- i;
                }
                else
                {
                        nLonger = (nLonger * nLonger) % q;
                        i >>= 1;
                }
        }

        return (static_cast<intType> (result));
} /* invertModuloLargeP */

/// Inverts a number in the modulo 'p' arithmetic,
/// provided that 'p' is a prime number.
/// This procedure is good for small values of 'p',
/// such that 'p' squared still fits in the same integer type.
template <class intType>
intType invertModuloSmallP (const intType &n, const intType &q)
{
        if ((n == 1) || (n == (q - 1)))
                return n;

        intType result (1);
        intType m (n);
        intType i (q - 2);

        while (i)
        {
                if (i & 1)
                {
                        result = (result * m) % q;
                        -- i;
                }
                else
                {
                        m = (m * m) % q;
                        i >>= 1;
                }
        }

        return result;
} /* invertModuloSmallP */

/// Verifies if the given number is a positive prime number.
template <class intType>
bool numberIsPrime (const intType &n)
{
        if (n < 2)
                return 0;

        typedef typename IntFeatures<intType>::LongerInt LongerInt;
        LongerInt i (2);

        while (1)
        {
                if (i * i > n)
                        return true;
                if (!(n % i))
                        return false;
                ++ i;
        }
} /* numberIsPrime */


// --------------------------------------------------
// ----- division with reminder in the ring Z_p -----
// --------------------------------------------------

template <class intType>
class tZp;

template <class intType>
inline bool divide (const tZp<intType> &a, const tZp<intType> &b,
        tZp<intType> &quotient, tZp<intType> &remainder)
{
        if (!b. _n)
                throw "Division by zero in the ring Z_p.";
        if (tZp<intType>::_p)
        {
                quotient = b;
                quotient. invert ();
                quotient *= a;
                remainder = tZp<intType> (static_cast<intType> (0));
                return true;
        }
        else
        {
                intType q = a. _n / b. _n;
                intType r = a. _n % b. _n;
                quotient = tZp<intType> (q);
                remainder = tZp<intType> (r);
                return !r;
        }
} /* divide */


// --------------------------------------------------
// ------------ elements of the ring Z_p ------------
// --------------------------------------------------

/// An element of the ring Z_p, where p is globally set.
/// Set p=0 for the ring Z (note the limited range of valid values).
/// In this implementation, p must be set smaller than the square root
/// of the largest positive number that can be encoded in the underlying
/// integer type.
template <class intType>
class tZp
{
public:
        /// Default constructor of a ring element.
        /// Note: The default copy constructor, destructor,
        /// and assignment operators are fine.
        tZp ();

        /// Constructor from an integer number
        /// (to be used mainly for 0 or 1).
        explicit tZp (const intType &n);

        /// Conversion to an integer.
        /// Note that in some rings this conversion may not be valid.
        operator intType () const;

        /// The delta function.
        intType delta () const;

        /// Negates the ring element.
        tZp<intType> &negate ();

        /// Inverts the ring element. Assumes that 'p' is a prime number.
        tZp<intType> &invert ();

        /// Adds another ring element.
        tZp<intType> &operator += (const tZp<intType> &another);

        /// Multiplies by another ring element.
        tZp<intType> &operator *= (const tZp<intType> &another);

        /// Swaps the internal data with another ring element.
        void swap (tZp<intType> &another);

        /// Sets the number p for the ring.
        static void setp (const intType &p);

        /// Gets the currently set number p for the ring.
        static const intType &getp ();

        /// Returns the symbol of the ring.
        static std::string ringsymbol ();

        /// Performs the division with remainder in the ring.
        /// Returns true if the remainer is zero, false otherwise.
        friend bool divide<intType>
                (const tZp<intType> &a, const tZp<intType> &b,
                tZp<intType> &quotient, tZp<intType> &remainder);

private:
        /// The number corresponding to the ring element.
        intType _n;

        /// The number that defines the ring.
        static intType _p;

}; /* class tZp */

// --------------------------------------------------

template <class intType>
intType tZp<intType>::_p = 2;

// --------------------------------------------------

template <class intType>
inline tZp<intType>::tZp ()
{
        return;
} /* tZp::tZp */

template <class intType>
inline tZp<intType>::tZp (const intType &n)
{
        if (_p)
        {
                if (n < 0)
                {
                        if (n > -_p)
                        {
                                _n = n + _p;
                        }
                        else
                        {
                                intType r = (-n) % _p;
                                _n = r ? (_p - r) : 0;
                        }
                }
                else if (n < _p)
                        _n = n;
                else if (n - _p < _p)
                        _n = n - _p;
                else
                        _n = n % _p;
        }
        else
        {
                _n = n;
        }
        return;
} /* tZp::tZp */

template <class intType>
inline tZp<intType>::operator intType () const
{
        return _n;
} /* tZp::operator intType */

template <class intType>
inline intType tZp<intType>::delta () const
{
        if (_p)
                return (_n ? 1 : 0);
        else
                return (_n >= 0) ? _n : -_n;
} /* tZp::delta */

template <class intType>
inline tZp<intType> &tZp<intType>::negate ()
{
        if (_n)
        {
                if (!_p)
                        _n = -_n;
                else
                        _n = _p - _n;
        }
        return *this;
} /* tZp::negate */

template <class intType>
inline tZp<intType> &tZp<intType>::invert ()
{
        if (_p)
        {
        //      _n = invertModuloLargeP (_n, _p);
                _n = invertModuloSmallP (_n, _p);
        }
        else if ((_n != -1) && (_n != 1))
                throw "Trying to invert a noninvertible integer number.";
        return *this;
} /* tZp::invert */

template <class intType>
inline tZp<intType> &tZp<intType>::operator += (const tZp<intType> &another)
{
        _n += another. _n;
        if (_p && (_n >= _p))
                _n -= _p;
        return *this;
} /* tZp::operator += */

template <class intType>
inline tZp<intType> &tZp<intType>::operator *= (const tZp<intType> &another)
{
        _n *= another. _n;
        if (_p && (_n >= _p))
                _n = _n % _p;
        return *this;
} /* tZp::operator *= */

template <class intType>
inline void tZp<intType>::swap (tZp<intType> &another)
{
        intType tmp (_n);
        _n = another. _n;
        another. _n = tmp;
        return;
} /* tZp::swap */

// --------------------------------------------------

template <class intType>
inline void tZp<intType>::setp (const intType &p)
{
        // the number cannot be negative
        if (p < 0)
                throw "Trying to set p < 0 for the ring Z_p.";

        // if the number is positive...
        if (p)
        {
                // increase the number to the nearest prime
                if (!numberIsPrime (p))
                {
                        intType q (p);
                        do
                        {
                                ++ q;
                        } while ((q > 0) && !numberIsPrime (q));
                        if (q <= 0)
                        {
                                throw "Can't increase p to a prime number "
                                        "for Z_p.";
                        }
                        _p = q;
                }
                else
                {
                        _p = p;
                }

                // make sure that the number is not too large
                typename IntFeatures<intType>::LongerInt p2long (_p);
                p2long *= _p;
                intType p2 (_p);
                p2 *= _p;
                if (p2long != p2)
                        throw "Int type too small for p requested in Z_p.";
        }
        else
        {
                _p = p;
        }

        return;
} /* tZp::setp */

template <class intType>
inline const intType &tZp<intType>::getp ()
{
        return _p;
} /* tZp::getp */

template <class intType>
inline std::string tZp<intType>::ringsymbol ()
{
        std::ostringstream out;
        out << 'Z';
        if (_p)
                out << '_' << _p;
        return out. str ();
} /* tZp::ringsymbol */

// --------------------------------------------------

/// Generates a hashing key no. 1 for an element of the Zp ring.
/// This key is to be used in a hashed set.
template <class intType>
inline int_t hashkey1 (const tZp<intType> &n)
{
        return static_cast<int_t> (static_cast<intType> (n));
} /* hashkey1 */

/// Generates a hashing key no. 2 for a general pair of elements,
/// based on hashing keys of the elements.
/// This key is to be used in a hashed set.
template <class intType>
inline int_t hashkey2 (const tZp<intType> &n)
{
        return static_cast<int_t> (static_cast<intType> (n)) ^ 0xA5A5;
} /* hashkey2 */

// --------------------------------------------------

/// Reads an element from an input stream.
template <class intType>
inline std::istream &operator >> (std::istream &in, tZp<intType> &n)
{
        intType number;
        in >> number;
        n = tZp<intType> (number);
        return in;
} /* operator >> */

/// Writes an element to an output stream.
template <class intType>
inline std::ostream &operator << (std::ostream &out, const tZp<intType> &n)
{
        out << static_cast<intType> (n);
        return out;
} /* operator << */

// --------------------------------------------------

/// Operator == for checking whether two elements of possibly different rings
/// are equal.
template <class intType1, class intType2>
inline bool operator == (const tZp<intType1> &n1, const tZp<intType2> &n2)
{
        return (static_cast<intType1> (n1) == static_cast<intType2> (n2));
} /* operator == */

/// Operator == for checking whether a ring element is equivalent
/// to an integer number. Intended to compare with 0 and 1 only.
template <class intType1, class intType2>
inline bool operator == (const tZp<intType1> &n1, const intType2 &n2)
{
        return (static_cast<intType1> (n1) == n2);
} /* operator == */

/// Operator == for checking whether a ring element is equivalent
/// to an integer number. Intended to compare with 0 and 1 only.
template <class intType1, class intType2>
inline bool operator == (const intType1 &n1, const tZp<intType2> &n2)
{
        return (n1 == static_cast<intType2> (n2));
} /* operator == */


#endif // _CHAINCON_RINGZP_H_