Crypto++ 8.6 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 & | operator= (const ModularArithmetic &ma)
| Assign a ModularArithmetic. More...
| ModularArithmetic (BufferedTransformation &bt)
| Construct a ModularArithmetic. More...
virtual ModularArithmetic * | Clone () 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 Integer & | GetModulus () 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 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...
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...
bool | IsUnit (const Integer &a) const
| Determines whether an element is a unit in the ring. More...
const Integer & | MultiplicativeInverse (const Integer &a) const
| Calculate the multiplicative inverse of an element in the ring. More...
const Integer & | Divide (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...
AbstractRing & | operator= (const AbstractRing &source)
| Assign an AbstractRing. More...
virtual const Element & | MultiplicativeIdentity () const=0
| Retrieves the multiplicative identity. 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 const Element & | Identity () const=0
| Provides the Identity element. More...
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, you should use the class like this:

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

The following code will produce incorrect results:

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

If a ModularArithmetic() is copied or assigned the modulus is copied, but not the internal data members. The internal data members are undefined after copy or assignment.

See also
  Integer on the Crypto++ wiki.

Definition at line 43 of file modarith.h.

## Constructor & Destructor Documentation

## ◆ ModularArithmetic() [1/3]

ModularArithmetic::ModularArithmetic | ( | const Integer & | modulus = `Integer::One()` | ) |
| inline

Construct a ModularArithmetic.

Parameters

  modulus | congruence class modulus

Definition at line 54 of file modarith.h.

## ◆ ModularArithmetic() [2/3]

ModularArithmetic::ModularArithmetic | ( | const ModularArithmetic & | ma | ) |
| inline

Copy construct a ModularArithmetic.

Parameters

  ma | other ModularArithmetic

Definition at line 59 of file modarith.h.

## ◆ ModularArithmetic() [3/3]

ModularArithmetic::ModularArithmetic | ( | BufferedTransformation & | bt | ) |

Construct a ModularArithmetic.

Parameters

  bt | BER encoded ModularArithmetic

## Member Function Documentation

## ◆ operator=()

ModularArithmetic& ModularArithmetic::operator= | ( | const ModularArithmetic & | ma | ) |
| inline

Assign a ModularArithmetic.

Parameters

  ma | other ModularArithmetic

Definition at line 64 of file modarith.h.

## ◆ Clone()

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

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

## ◆ DEREncode()

void ModularArithmetic::DEREncode | ( | BufferedTransformation & | bt | ) | const

Encodes in DER format.

Parameters

  bt | BufferedTransformation object

## ◆ DEREncodeElement()

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

Encodes element in DER format.

Parameters

  out | BufferedTransformation object
  a | Element to encode

## ◆ BERDecodeElement()

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

Decodes element in DER format.

Parameters

  in | BufferedTransformation object
  a | Element to decode

## ◆ GetModulus()

const Integer& ModularArithmetic::GetModulus | ( |  | ) | const
| inline

Retrieves the modulus.

Returns
  the modulus

Definition at line 99 of file modarith.h.

## ◆ SetModulus()

void ModularArithmetic::SetModulus | ( | const Integer & | newModulus | ) |
| inline

Sets the modulus.

Parameters

  newModulus | the new modulus

Definition at line 103 of file modarith.h.

## ◆ IsMontgomeryRepresentation()

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

Retrieves the representation.

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

Reimplemented in MontgomeryRepresentation.

Definition at line 108 of file modarith.h.

## ◆ ConvertIn()

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

Definition at line 115 of file modarith.h.

## ◆ ConvertOut()

virtual Integer ModularArithmetic::ConvertOut | ( | const Integer & | a | ) | const
| inline 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 in MontgomeryRepresentation.

Definition at line 123 of file modarith.h.

## ◆ Half()

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

Divides an element by 2.

Parameters

  a | element to convert

## ◆ Equal()

bool ModularArithmetic::Equal | ( | const Integer & | a,
|  | const Integer & | b
| ) |  | const
| inline virtual

Compare two elements for equality.

Parameters

  a | first element
  b | second 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 135 of file modarith.h.

## ◆ Identity()

const Integer& ModularArithmetic::Identity | ( |  | ) | const
| inline

Provides the Identity element.

Returns
  the Identity element

Definition at line 140 of file modarith.h.

## ◆ Add()

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

Adds elements in the ring.

Parameters

  a | first element
  b | second element

Returns
  the sum of `a` and `b`

Implements AbstractGroup< Integer >.

## ◆ Accumulate()

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

TODO.

Parameters

  a | first element
  b | second element

Returns
  TODO

Reimplemented from AbstractGroup< Integer >.

## ◆ Inverse()

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

Inverts the element in the ring.

Parameters

  a | first element

Returns
  the inverse of the element

Implements AbstractGroup< Integer >.

## ◆ Subtract()

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

Subtracts elements in the ring.

Parameters

  a | first element
  b | second element

Returns
  the difference of `a` and `b`. The element `a` must provide a Subtract member function.

Reimplemented from AbstractGroup< Integer >.

## ◆ Reduce()

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

TODO.

Parameters

  a | first element
  b | second element

Returns
  TODO

Reimplemented from AbstractGroup< Integer >.

## ◆ Double()

const Integer& ModularArithmetic::Double | ( | const Integer & | a | ) | const
| inline virtual

Doubles an element in the ring.

Parameters

  a | the 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 176 of file modarith.h.

## ◆ MultiplicativeIdentity()

const Integer& ModularArithmetic::MultiplicativeIdentity | ( |  | ) | const
| inline

Retrieves the multiplicative identity.

Returns
  the multiplicative identity

the base class implementations returns 1.

Definition at line 182 of file modarith.h.

## ◆ Multiply()

const Integer& ModularArithmetic::Multiply | ( | const Integer & | a,
|  | const Integer & | b
| ) |  | const
| inline 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`.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 190 of file modarith.h.

## ◆ Square()

const Integer& ModularArithmetic::Square | ( | const Integer & | a | ) | const
| inline 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 AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 197 of file modarith.h.

## ◆ IsUnit()

bool ModularArithmetic::IsUnit | ( | const Integer & | a | ) | const
| inline virtual

Determines whether an element is a unit in the ring.

Parameters

  a | the element

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

Implements AbstractRing< Integer >.

Definition at line 203 of file modarith.h.

## ◆ MultiplicativeInverse()

const Integer& ModularArithmetic::MultiplicativeInverse | ( | const Integer & | a | ) | const
| inline 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.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 210 of file modarith.h.

## ◆ Divide()

const Integer& ModularArithmetic::Divide | ( | const Integer & | a,
|  | const Integer & | b
| ) |  | const
| inline virtual

Divides elements in the ring.

Parameters

  a | the dividend
  b | the divisor

Returns
  the quotient

Divide returns `a*b-1%n`.

Reimplemented from AbstractRing< Integer >.

Definition at line 218 of file modarith.h.

## ◆ CascadeExponentiate()

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

TODO.

Parameters

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

Returns
  TODO

Reimplemented from AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

## ◆ SimultaneousExponentiate()

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

  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 AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

## ◆ MaxElementBitLength()

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

## ◆ MaxElementByteLength()

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

## ◆ RandomElement()

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

Provides a random element in the ring.

Parameters

  rng | RandomNumberGenerator used to generate material
  ignore_for_now | unused

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

## ◆ operator==()

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

Compares two ModularArithmetic for equality.

Parameters

  rhs | other 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 269 of file modarith.h.

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

- modarith.h