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

#include <modarith.h>

Inheritance diagram for MontgomeryRepresentation:

Collaboration diagram for MontgomeryRepresentation:

Public Member Functions
virtual	~MontgomeryRepresentation ()

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

	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	~AbstractGroup ()

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

Private Attributes
Integer	m_u

IntegerSecBlock	m_workspace

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

Protected Attributes inherited from ModularArithmetic
Integer	m_modulus

Integer	m_result

Integer	m_result1

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

Constructor & Destructor Documentation

virtual MontgomeryRepresentation::~MontgomeryRepresentation ( )

inlinevirtual

Definition at line 274 of file modarith.h.

MontgomeryRepresentation::MontgomeryRepresentation ( const Integer & modulus )

Construct a MontgomeryRepresentation.

Parameters

modulus congruence class modulus

Note: The modulus must be odd.

Definition at line 4572 of file integer.cpp.

Here is the call graph for this function:

Member Function Documentation

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

inlinevirtual

TODO.

Parameters

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

Returns: TODO

Reimplemented from ModularArithmetic.

Definition at line 303 of file modarith.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Definition at line 289 of file modarith.h.

Here is the call graph for this function:

Here is the caller graph for this function:

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 4609 of file integer.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Here is the call graph for this function:

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 4622 of file integer.cpp.

Here is the call graph for this function:

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 4583 of file integer.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

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

Here is the call graph for this function:

Here is the caller graph for this function:

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 4596 of file integer.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

Integer MontgomeryRepresentation::m_u

private

Definition at line 310 of file modarith.h.

IntegerSecBlock MontgomeryRepresentation::m_workspace

mutableprivate

Definition at line 311 of file modarith.h.

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

src/cryptopp/modarith.h
src/cryptopp/integer.cpp

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation