Crypto++  5.6.5
Free C++ class library of cryptographic schemes
Public Types | Public Member Functions | Static Public Attributes | List of all members
ModularArithmetic Class Reference

Ring of congruence classes modulo n. More...

+ Inheritance diagram for ModularArithmetic:

Public Types

typedef int RandomizationParameter
 
typedef Integer Element
 
- Public Types inherited from AbstractRing< Integer >
typedef Integer Element
 
- Public Types inherited from AbstractGroup< Integer >
typedef Integer Element
 

Public Member Functions

 ModularArithmetic (const Integer &modulus=Integer::One())
 Construct a ModularArithmetic. More...
 
 ModularArithmetic (const ModularArithmetic &ma)
 Copy construct a ModularArithmetic. More...
 
 ModularArithmetic (BufferedTransformation &bt)
 Construct a ModularArithmetic. More...
 
virtual ModularArithmeticClone () const
 Clone a ModularArithmetic. More...
 
void DEREncode (BufferedTransformation &bt) const
 Encodes in DER format. More...
 
void DEREncodeElement (BufferedTransformation &out, const Element &a) const
 Encodes element in DER format. More...
 
void BERDecodeElement (BufferedTransformation &in, Element &a) const
 Decodes element in DER format. More...
 
const IntegerGetModulus () const
 Retrieves the modulus. More...
 
void SetModulus (const Integer &newModulus)
 Sets the modulus. More...
 
virtual bool IsMontgomeryRepresentation () const
 Retrieves the representation. More...
 
virtual Integer ConvertIn (const Integer &a) const
 Reduces an element in the congruence class. More...
 
virtual Integer ConvertOut (const Integer &a) const
 Reduces an element in the congruence class. More...
 
const IntegerHalf (const Integer &a) const
 Divides an element by 2. More...
 
bool Equal (const Integer &a, const Integer &b) const
 Compare two elements for equality. More...
 
const IntegerIdentity () const
 Provides the Identity element. More...
 
const IntegerAdd (const Integer &a, const Integer &b) const
 Adds elements in the ring. More...
 
IntegerAccumulate (Integer &a, const Integer &b) const
 TODO. More...
 
const IntegerInverse (const Integer &a) const
 Inverts the element in the ring. More...
 
const IntegerSubtract (const Integer &a, const Integer &b) const
 Subtracts elements in the ring. More...
 
IntegerReduce (Integer &a, const Integer &b) const
 TODO. More...
 
const IntegerDouble (const Integer &a) const
 Doubles an element in the ring. More...
 
const IntegerMultiplicativeIdentity () const
 Retrieves the multiplicative identity. More...
 
const IntegerMultiply (const Integer &a, const Integer &b) const
 Multiplies elements in the ring. More...
 
const IntegerSquare (const Integer &a) const
 Square an element in the ring. More...
 
bool IsUnit (const Integer &a) const
 Determines whether an element is a unit in the ring. More...
 
const IntegerMultiplicativeInverse (const Integer &a) const
 Calculate the multiplicative inverse of an element in the ring. More...
 
const IntegerDivide (const Integer &a, const Integer &b) const
 Divides elements in the ring. More...
 
Integer CascadeExponentiate (const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const
 TODO. More...
 
void SimultaneousExponentiate (Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
 Exponentiates a base to multiple exponents in the ring. More...
 
unsigned int MaxElementBitLength () const
 Provides the maximum bit size of an element in the ring. More...
 
unsigned int MaxElementByteLength () const
 Provides the maximum byte size of an element in the ring. More...
 
Element RandomElement (RandomNumberGenerator &rng, const RandomizationParameter &ignore_for_now=0) const
 Provides a random element in the ring. More...
 
bool operator== (const ModularArithmetic &rhs) const
 Compares two ModularArithmetic for equality. More...
 
- Public Member Functions inherited from AbstractRing< Integer >
 AbstractRing ()
 Construct an AbstractRing.
 
 AbstractRing (const AbstractRing &source)
 Copy construct an AbstractRing. More...
 
AbstractRingoperator= (const AbstractRing &source)
 Assign an AbstractRing. More...
 
virtual Element Exponentiate (const Element &a, const Integer &e) const
 Raises a base to an exponent in the group. More...
 
virtual const AbstractGroup< Integer > & MultiplicativeGroup () const
 Retrieves the multiplicative group. More...
 
- Public Member Functions inherited from AbstractGroup< Integer >
virtual bool InversionIsFast () const
 Determine if inversion is fast. More...
 
virtual Element ScalarMultiply (const Element &a, const Integer &e) const
 Performs a scalar multiplication. More...
 
virtual Element CascadeScalarMultiply (const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
 TODO. More...
 
virtual void SimultaneousMultiply (Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
 Multiplies a base to multiple exponents in a group. More...
 

Static Public Attributes

static const RandomizationParameter DefaultRandomizationParameter
 

Detailed Description

Ring of congruence classes modulo n.

This implementation represents each congruence class as the smallest non-negative integer in that class.

const Element& returned by member functions are references to internal data members. Since each object may have only one such data member for holding results, the following code will produce incorrect results:

    abcd = group.Add(group.Add(a,b), group.Add(c,d));

But this should be fine:

    abcd = group.Add(a, group.Add(b, group.Add(c,d));

Definition at line 34 of file modarith.h.

Constructor & Destructor Documentation

ModularArithmetic::ModularArithmetic ( const Integer modulus = Integer::One())
inline

Construct a ModularArithmetic.

Parameters
moduluscongruence class modulus

Definition at line 45 of file modarith.h.

ModularArithmetic::ModularArithmetic ( const ModularArithmetic ma)
inline

Copy construct a ModularArithmetic.

Parameters
maother ModularArithmetic

Definition at line 50 of file modarith.h.

ModularArithmetic::ModularArithmetic ( BufferedTransformation bt)

Construct a ModularArithmetic.

Parameters
btBER encoded ModularArithmetic

Definition at line 4422 of file integer.cpp.

Member Function Documentation

virtual ModularArithmetic* ModularArithmetic::Clone ( ) const
inlinevirtual

Clone a ModularArithmetic.

Returns
pointer to a new ModularArithmetic

Clone effectively copy constructs a new ModularArithmetic. The caller is responsible for deleting the pointer returned from this method.

Reimplemented in MontgomeryRepresentation.

Definition at line 61 of file modarith.h.

void ModularArithmetic::DEREncode ( BufferedTransformation bt) const

Encodes in DER format.

Parameters
btBufferedTransformation object

Definition at line 4433 of file integer.cpp.

void ModularArithmetic::DEREncodeElement ( BufferedTransformation out,
const Element a 
) const

Encodes element in DER format.

Parameters
outBufferedTransformation object
aElement to encode

Definition at line 4441 of file integer.cpp.

void ModularArithmetic::BERDecodeElement ( BufferedTransformation in,
Element a 
) const

Decodes element in DER format.

Parameters
inBufferedTransformation object
aElement to decode

Definition at line 4446 of file integer.cpp.

const Integer& ModularArithmetic::GetModulus ( ) const
inline

Retrieves the modulus.

Returns
the modulus

Definition at line 79 of file modarith.h.

void ModularArithmetic::SetModulus ( const Integer newModulus)
inline

Sets the modulus.

Parameters
newModulusthe new modulus

Definition at line 83 of file modarith.h.

virtual bool ModularArithmetic::IsMontgomeryRepresentation ( ) const
inlinevirtual

Retrieves the representation.

Returns
true if the if the modulus is in Montgomery form for multiplication, false otherwise

Reimplemented in MontgomeryRepresentation.

Definition at line 88 of file modarith.h.

virtual Integer ModularArithmetic::ConvertIn ( const Integer a) const
inlinevirtual

Reduces an element in the congruence class.

Parameters
aelement to convert
Returns
the reduced element

ConvertIn is useful for derived classes, like MontgomeryRepresentation, which must convert between representations.

Reimplemented in MontgomeryRepresentation.

Definition at line 95 of file modarith.h.

virtual Integer ModularArithmetic::ConvertOut ( const Integer a) const
inlinevirtual

Reduces an element in the congruence class.

Parameters
aelement to convert
Returns
the reduced element

ConvertOut is useful for derived classes, like MontgomeryRepresentation, which must convert between representations.

Reimplemented in MontgomeryRepresentation.

Definition at line 103 of file modarith.h.

const Integer & ModularArithmetic::Half ( const Integer a) const

Divides an element by 2.

Parameters
aelement to convert

Definition at line 4451 of file integer.cpp.

bool ModularArithmetic::Equal ( const Integer a,
const Integer b 
) const
inlinevirtual

Compare two elements for equality.

Parameters
afirst element
bsecond element
Returns
true if the elements are equal, false otherwise

Equal() tests the elements for equality using a==b

Implements AbstractGroup< Integer >.

Definition at line 115 of file modarith.h.

const Integer& ModularArithmetic::Identity ( ) const
inlinevirtual

Provides the Identity element.

Returns
the Identity element

Implements AbstractGroup< Integer >.

Definition at line 120 of file modarith.h.

const Integer & ModularArithmetic::Add ( const Integer a,
const Integer b 
) const
virtual

Adds elements in the ring.

Parameters
afirst element
bsecond element
Returns
the sum of a and b

Implements AbstractGroup< Integer >.

Definition at line 4462 of file integer.cpp.

Integer & ModularArithmetic::Accumulate ( Integer a,
const Integer b 
) const
virtual

TODO.

Parameters
afirst element
bsecond element
Returns
TODO

Reimplemented from AbstractGroup< Integer >.

Definition at line 4482 of file integer.cpp.

const Integer & ModularArithmetic::Inverse ( const Integer a) const
virtual

Inverts the element in the ring.

Parameters
afirst element
Returns
the inverse of the element

Implements AbstractGroup< Integer >.

Definition at line 4536 of file integer.cpp.

const Integer & ModularArithmetic::Subtract ( const Integer a,
const Integer b 
) const
virtual

Subtracts elements in the ring.

Parameters
afirst element
bsecond element
Returns
the difference of a and b. The element a must provide a Subtract member function.

Reimplemented from AbstractGroup< Integer >.

Definition at line 4502 of file integer.cpp.

Integer & ModularArithmetic::Reduce ( Integer a,
const Integer b 
) const
virtual

TODO.

Parameters
afirst element
bsecond element
Returns
TODO

Reimplemented from AbstractGroup< Integer >.

Definition at line 4519 of file integer.cpp.

const Integer& ModularArithmetic::Double ( const Integer a) const
inlinevirtual

Doubles an element in the ring.

Parameters
athe element
Returns
the element doubled

Double returns Add(a, a). The element a must provide an Add member function.

Reimplemented from AbstractGroup< Integer >.

Definition at line 156 of file modarith.h.

const Integer& ModularArithmetic::MultiplicativeIdentity ( ) const
inlinevirtual

Retrieves the multiplicative identity.

Returns
the multiplicative identity

the base class implementations returns 1.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 162 of file modarith.h.

const Integer& ModularArithmetic::Multiply ( const Integer a,
const Integer b 
) const
inlinevirtual

Multiplies elements in the ring.

Parameters
athe multiplicand
bthe multiplier
Returns
the product of a and b

Multiply returns a*b%n.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 170 of file modarith.h.

const Integer& ModularArithmetic::Square ( const Integer a) const
inlinevirtual

Square an element in the ring.

Parameters
athe element
Returns
the element squared

Square returns a*a%n. The element a must provide a Square member function.

Reimplemented from AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 177 of file modarith.h.

bool ModularArithmetic::IsUnit ( const Integer a) const
inlinevirtual

Determines whether an element is a unit in the ring.

Parameters
athe element
Returns
true if the element is a unit after reduction, false otherwise.

Implements AbstractRing< Integer >.

Definition at line 183 of file modarith.h.

const Integer& ModularArithmetic::MultiplicativeInverse ( const Integer a) const
inlinevirtual

Calculate the multiplicative inverse of an element in the ring.

Parameters
athe element

MultiplicativeInverse returns a-1%n. The element a must provide a InverseMod member function.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 190 of file modarith.h.

const Integer& ModularArithmetic::Divide ( const Integer a,
const Integer b 
) const
inlinevirtual

Divides elements in the ring.

Parameters
athe dividend
bthe divisor
Returns
the quotient

Divide returns a*b-1%n.

Reimplemented from AbstractRing< Integer >.

Definition at line 198 of file modarith.h.

Integer ModularArithmetic::CascadeExponentiate ( const Integer x,
const Integer e1,
const Integer y,
const Integer e2 
) const
virtual

TODO.

Parameters
xfirst element
e1first exponent
ysecond element
e2second exponent
Returns
TODO

Reimplemented from AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 4548 of file integer.cpp.

void ModularArithmetic::SimultaneousExponentiate ( Element results,
const Element base,
const Integer exponents,
unsigned int  exponentsCount 
) const
virtual

Exponentiates a base to multiple exponents in the ring.

Parameters
resultsan array of Elements
basethe base to raise to the exponents
exponentsan array of exponents
exponentsCountthe number of exponents in the array

SimultaneousExponentiate() raises the base to each exponent in the exponents array and stores the result at the respective position in the results array.

SimultaneousExponentiate() must be implemented in a derived class.

Precondition
COUNTOF(results) == exponentsCount
COUNTOF(exponents) == exponentsCount

Reimplemented from AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 4559 of file integer.cpp.

unsigned int ModularArithmetic::MaxElementBitLength ( ) const
inline

Provides the maximum bit size of an element in the ring.

Returns
maximum bit size of an element

Definition at line 223 of file modarith.h.

unsigned int ModularArithmetic::MaxElementByteLength ( ) const
inline

Provides the maximum byte size of an element in the ring.

Returns
maximum byte size of an element

Definition at line 228 of file modarith.h.

Element ModularArithmetic::RandomElement ( RandomNumberGenerator rng,
const RandomizationParameter &  ignore_for_now = 0 
) const
inline

Provides a random element in the ring.

Parameters
rngRandomNumberGenerator used to generate material
ignore_for_nowunused
Returns
a random element that is uniformly distributed

RandomElement constructs a new element in the range [0,n-1], inclusive. The element's class must provide a constructor with the signature Element(RandomNumberGenerator rng, Element min, Element max).

Definition at line 238 of file modarith.h.

bool ModularArithmetic::operator== ( const ModularArithmetic rhs) const
inline

Compares two ModularArithmetic for equality.

Parameters
rhsother ModularArithmetic
Returns
true if this is equal to the other, false otherwise

The operator tests for equality using this.m_modulus == rhs.m_modulus.

Definition at line 249 of file modarith.h.


The documentation for this class was generated from the following files: