Crypto++ 8.0 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...

Inheritance diagram for MontgomeryRepresentation:

## Public Member Functions
| MontgomeryRepresentation (const Integer &modulus)
| Construct a MontgomeryRepresentation. More...
virtual ModularArithmetic * | Clone () 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 Integer & | MultiplicativeIdentity () const
| Retrieves the multiplicative identity. More...
const Integer & | Multiply (const Integer &a, const Integer &b) const
| Multiplies elements in the ring. More...
const Integer & | Square (const Integer &a) const
| Square an element in the ring. More...
const Integer & | MultiplicativeInverse (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...
| ModularArithmetic (BufferedTransformation &bt)
| Construct 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 Integer & | GetModulus () const
| Retrieves the modulus. More...
void | SetModulus (const Integer &newModulus)
| Sets the modulus. More...
const Integer & | Half (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 Integer & | Identity () const
| Provides the Identity element. More...
const Integer & | Add (const Integer &a, const Integer &b) const
| Adds elements in the ring. More...
Integer & | Accumulate (Integer &a, const Integer &b) const
| TODO. More...
const Integer & | Inverse (const Integer &a) const
| Inverts the element in the ring. More...
const Integer & | Subtract (const Integer &a, const Integer &b) const
| Subtracts elements in the ring. More...
Integer & | Reduce (Integer &a, const Integer &b) const
| TODO. More...
const Integer & | Double (const Integer &a) const
| Doubles an element in the ring. More...
bool | IsUnit (const Integer &a) const
| Determines whether an element is a unit in the ring. More...
const Integer & | Divide (const Integer &a, const Integer &b) const
| Divides elements 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...
AbstractRing & | operator= (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...

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

## Constructor & Destructor Documentation

## ◆ MontgomeryRepresentation()

MontgomeryRepresentation::MontgomeryRepresentation | ( | const Integer & | modulus | ) |

Construct a MontgomeryRepresentation.

Parameters

  modulus | congruence class modulus

Note
  The modulus must be odd.

Definition at line 4639 of file integer.cpp.

## Member Function Documentation

## ◆ Clone()

virtual ModularArithmetic* MontgomeryRepresentation::Clone | ( |  | ) | const
| inline virtual

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

## ◆ IsMontgomeryRepresentation()

bool MontgomeryRepresentation::IsMontgomeryRepresentation | ( |  | ) | const
| inline virtual

Retrieves the representation.

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

Reimplemented from ModularArithmetic.

Definition at line 290 of file modarith.h.

## ◆ ConvertIn()

Integer MontgomeryRepresentation::ConvertIn | ( | const Integer & | a | ) | const
| inline virtual

Reduces an element in the congruence class.

Parameters

  a | element 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 292 of file modarith.h.

## ◆ ConvertOut()

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

Reduces an element in the congruence class.

Parameters

  a | element to convert

Returns
  the reduced element

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

Reimplemented from ModularArithmetic.

Definition at line 4676 of file integer.cpp.

## ◆ MultiplicativeIdentity()

const Integer& MontgomeryRepresentation::MultiplicativeIdentity | ( |  | ) | const
| inline virtual

Retrieves the multiplicative identity.

Returns
  the multiplicative identity

the base class implementations returns 1.

Reimplemented from ModularArithmetic.

Definition at line 297 of file modarith.h.

## ◆ Multiply()

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

Multiplies elements in the ring.

Parameters

  a | the multiplicand
  b | the multiplier

Returns
  the product of a and b

Multiply returns `a*b%n`.

Reimplemented from ModularArithmetic.

Definition at line 4650 of file integer.cpp.

## ◆ Square()

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

Square an element in the ring.

Parameters

  a | the element

Returns
  the element squared

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

Reimplemented from ModularArithmetic.

Definition at line 4663 of file integer.cpp.

## ◆ MultiplicativeInverse()

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

Calculate the multiplicative inverse of an element in the ring.

Parameters

  a | the element

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

Reimplemented from ModularArithmetic.

Definition at line 4689 of file integer.cpp.

## ◆ CascadeExponentiate()

Integer MontgomeryRepresentation::CascadeExponentiate | ( | const Integer & | x,
|  | const Integer & | e1,
|  | const Integer & | y,
|  | const Integer & | e2
| ) |  | const
| inline virtual

TODO.

Parameters

  x | first element
  e1 | first exponent
  y | second element
  e2 | second exponent

Returns
  TODO

Reimplemented from ModularArithmetic.

Definition at line 306 of file modarith.h.

## ◆ SimultaneousExponentiate()

void MontgomeryRepresentation::SimultaneousExponentiate | ( | Element * | results,
|  | const Element & | base,
|  | const Integer * | exponents,
|  | unsigned int | exponentsCount
| ) |  | const
| inline virtual

Exponentiates a base to multiple exponents in the ring.

Parameters

  results | an array of Elements
  base | the base to raise to the exponents
  exponents | an array of exponents
  exponentsCount | the 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 309 of file modarith.h.

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

- modarith.h
- integer.cpp