Crypto++ 8.7
Free C++ class library of cryptographic schemes
Public Member Functions | List of all members
MontgomeryRepresentation Class Reference

Performs modular arithmetic in Montgomery representation for increased speed. More...

#include <modarith.h>

+ Inheritance diagram for MontgomeryRepresentation:

Public Member Functions

 MontgomeryRepresentation (const Integer &modulus)
 Construct a MontgomeryRepresentation. More...
 
virtual ModularArithmeticClone () const
 Clone a MontgomeryRepresentation. More...
 
bool IsMontgomeryRepresentation () const
 Retrieves the representation. More...
 
Integer ConvertIn (const Integer &a) const
 Reduces an element in the congruence class. More...
 
Integer ConvertOut (const Integer &a) const
 Reduces an element in the congruence class. 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...
 
const IntegerMultiplicativeInverse (const Integer &a) const
 Calculate the multiplicative inverse of an element 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...
 
- Public Member Functions inherited from ModularArithmetic
 ModularArithmetic (const Integer &modulus=Integer::One())
 Construct a ModularArithmetic. More...
 
 ModularArithmetic (const ModularArithmetic &ma)
 Copy construct a ModularArithmetic. More...
 
ModularArithmeticoperator= (const ModularArithmetic &ma)
 Assign 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. More...
 
 AbstractRing (const AbstractRing &source)
 Copy construct an AbstractRing. More...
 
AbstractRingoperator= (const AbstractRing &source)
 Assign an AbstractRing. More...
 
virtual bool IsUnit (const Element &a) const=0
 Determines whether an element is a unit in the group. More...
 
virtual const ElementMultiplicativeIdentity () const=0
 Retrieves the multiplicative identity. More...
 
virtual const ElementMultiply (const Element &a, const Element &b) const=0
 Multiplies elements in the group. More...
 
virtual const ElementMultiplicativeInverse (const Element &a) const=0
 Calculate the multiplicative inverse of an element in the group. More...
 
virtual const ElementSquare (const Element &a) const
 Square an element in the group. More...
 
virtual const ElementDivide (const Element &a, const Element &b) const
 Divides elements in the group. More...
 
virtual Element Exponentiate (const Element &a, const Integer &e) const
 Raises a base to an exponent in the group. More...
 
virtual Element CascadeExponentiate (const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
 TODO. More...
 
virtual void SimultaneousExponentiate (Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
 Exponentiates a base to multiple exponents in the Ring. More...
 
virtual const AbstractGroup< Integer > & MultiplicativeGroup () const
 Retrieves the multiplicative group. More...
 
- Public Member Functions inherited from AbstractGroup< Integer >
virtual bool Equal (const Element &a, const Element &b) const=0
 Compare two elements for equality. More...
 
virtual const ElementIdentity () const=0
 Provides the Identity element. More...
 
virtual const ElementAdd (const Element &a, const Element &b) const=0
 Adds elements in the group. More...
 
virtual const ElementInverse (const Element &a) const=0
 Inverts the element in the group. More...
 
virtual bool InversionIsFast () const
 Determine if inversion is fast. More...
 
virtual const ElementDouble (const Element &a) const
 Doubles an element in the group. More...
 
virtual const ElementSubtract (const Element &a, const Element &b) const
 Subtracts elements in the group. More...
 
virtual ElementAccumulate (Element &a, const Element &b) const
 TODO. More...
 
virtual ElementReduce (Element &a, const Element &b) const
 Reduces an element in the congruence class. 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...
 

Additional Inherited Members

- Public Types inherited from ModularArithmetic
typedef int RandomizationParameter
 
typedef Integer Element
 
- Public Types inherited from AbstractRing< Integer >
typedef Integer Element
 
- Public Types inherited from AbstractGroup< Integer >
typedef Integer Element
 
- Static Public Attributes inherited from ModularArithmetic
static const RandomizationParameter DefaultRandomizationParameter
 

Detailed Description

Performs modular arithmetic in Montgomery representation for increased speed.

The Montgomery representation represents each congruence class [a] as a*r%n, where r is a convenient power of 2.

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 295 of file modarith.h.

Constructor & Destructor Documentation

◆ ~MontgomeryRepresentation()

virtual MontgomeryRepresentation::~MontgomeryRepresentation ( )
inlinevirtual

Definition at line 298 of file modarith.h.

◆ MontgomeryRepresentation()

MontgomeryRepresentation::MontgomeryRepresentation ( const Integer modulus)

Construct a MontgomeryRepresentation.

Parameters
moduluscongruence class modulus
Note
The modulus must be odd.

Member Function Documentation

◆ Clone()

virtual ModularArithmetic * MontgomeryRepresentation::Clone ( ) const
inlinevirtual

Clone a MontgomeryRepresentation.

Returns
pointer to a new MontgomeryRepresentation

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

Reimplemented from ModularArithmetic.

Definition at line 309 of file modarith.h.

◆ IsMontgomeryRepresentation()

bool MontgomeryRepresentation::IsMontgomeryRepresentation ( ) const
inlinevirtual

Retrieves the representation.

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

Reimplemented from ModularArithmetic.

Definition at line 311 of file modarith.h.

◆ ConvertIn()

Integer MontgomeryRepresentation::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 from ModularArithmetic.

Definition at line 313 of file modarith.h.

◆ ConvertOut()

Integer MontgomeryRepresentation::ConvertOut ( const Integer a) const
virtual

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 from ModularArithmetic.

◆ MultiplicativeIdentity()

const Integer & MontgomeryRepresentation::MultiplicativeIdentity ( ) const
inlinevirtual

Retrieves the multiplicative identity.

Returns
the multiplicative identity

the base class implementations returns 1.

Reimplemented from ModularArithmetic.

Definition at line 318 of file modarith.h.

◆ Multiply()

const Integer & MontgomeryRepresentation::Multiply ( const Integer a,
const Integer b 
) const
virtual

Multiplies elements in the ring.

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

Multiply returns a*b%n.

Reimplemented from ModularArithmetic.

◆ Square()

const Integer & MontgomeryRepresentation::Square ( const Integer a) const
virtual

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 ModularArithmetic.

◆ MultiplicativeInverse()

const Integer & MontgomeryRepresentation::MultiplicativeInverse ( const Integer a) const
virtual

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.

Reimplemented from ModularArithmetic.

◆ CascadeExponentiate()

Integer MontgomeryRepresentation::CascadeExponentiate ( const Integer x,
const Integer e1,
const Integer y,
const Integer e2 
) const
inlinevirtual

TODO.

Parameters
xfirst element
e1first exponent
ysecond element
e2second exponent
Returns
TODO

Reimplemented from ModularArithmetic.

Definition at line 327 of file modarith.h.

◆ SimultaneousExponentiate()

void MontgomeryRepresentation::SimultaneousExponentiate ( Element results,
const Element base,
const Integer exponents,
unsigned int  exponentsCount 
) const
inlinevirtual

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 ModularArithmetic.

Definition at line 330 of file modarith.h.


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