Ring of congruence classes modulo n. More...

#include <modarith.h>

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

	AbstractRing (const AbstractRing &source)
	Copy construct an AbstractRing. More...

AbstractRing &	operator= (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 Element &	MultiplicativeIdentity () const=0
	Retrieves the multiplicative identity. More...

virtual const Element &	Multiply (const Element &a, const Element &b) const=0
	Multiplies elements in the group. More...

virtual const Element &	MultiplicativeInverse (const Element &a) const=0
	Calculate the multiplicative inverse of an element in the group. More...

virtual const Element &	Square (const Element &a) const
	Square an element in the group. More...

virtual const Element &	Divide (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 Element &	Identity () const=0
	Provides the Identity element. More...

virtual const Element &	Add (const Element &a, const Element &b) const=0
	Adds elements in the group. More...

virtual const Element &	Inverse (const Element &a) const=0
	Inverts the element in the group. More...

virtual bool	InversionIsFast () const
	Determine if inversion is fast. More...

virtual const Element &	Double (const Element &a) const
	Doubles an element in the group. More...

virtual const Element &	Subtract (const Element &a, const Element &b) const
	Subtracts elements in the group. More...

virtual Element &	Accumulate (Element &a, const Element &b) const
	TODO. More...

virtual Element &	Reduce (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...

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.

Member Typedef Documentation

◆ RandomizationParameter

typedef int ModularArithmetic::RandomizationParameter

Definition at line 47 of file modarith.h.

◆ Element

typedef Integer ModularArithmetic::Element

Definition at line 48 of file modarith.h.

Constructor & Destructor Documentation

◆ ~ModularArithmetic()

virtual ModularArithmetic::~ModularArithmetic ( )

inlinevirtual

Definition at line 50 of file modarith.h.

◆ 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

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

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

◆ ConvertIn()

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

inlinevirtual

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

inlinevirtual

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

inlinevirtual

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

inlinevirtual

Provides the Identity element.

Returns: the Identity element

Implements AbstractGroup< Integer >.

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

inlinevirtual

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

inlinevirtual

Retrieves the multiplicative identity.

Returns: the multiplicative identity

the base class implementations returns 1.

Implements AbstractRing< Integer >.

Reimplemented in MontgomeryRepresentation.

Definition at line 182 of file modarith.h.

◆ Multiply()

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

inlinevirtual

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

inlinevirtual

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

inlinevirtual

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

inlinevirtual

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

inlinevirtual

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.

Member Data Documentation

◆ DefaultRandomizationParameter

const RandomizationParameter ModularArithmetic::DefaultRandomizationParameter

static

Definition at line 272 of file modarith.h.

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

modarith.h

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ RandomizationParameter

◆ Element

Constructor & Destructor Documentation

◆ ~ModularArithmetic()

◆ ModularArithmetic() [1/3]

◆ ModularArithmetic() [2/3]

◆ ModularArithmetic() [3/3]

Member Function Documentation

◆ operator=()

◆ Clone()

◆ DEREncode()

◆ DEREncodeElement()

◆ BERDecodeElement()

◆ GetModulus()

◆ SetModulus()

◆ IsMontgomeryRepresentation()

◆ ConvertIn()

◆ ConvertOut()

◆ Half()

◆ Equal()

◆ Identity()

◆ Add()

◆ Accumulate()

◆ Inverse()

◆ Subtract()

◆ Reduce()

◆ Double()

◆ MultiplicativeIdentity()

◆ Multiply()

◆ Square()

◆ IsUnit()

◆ MultiplicativeInverse()

◆ Divide()

◆ CascadeExponentiate()

◆ SimultaneousExponentiate()

◆ MaxElementBitLength()

◆ MaxElementByteLength()

◆ RandomElement()

◆ operator==()

Member Data Documentation

◆ DefaultRandomizationParameter