The world's most popular open source database

MySQL 5.1: TaoCrypt::AbstractGroup Class Reference

TaoCrypt::AbstractGroup

TaoCrypt::AbstractGroup Class Reference

#include <algebra.hpp>

Inheritance diagram for TaoCrypt::AbstractGroup:

[legend]Collaboration diagram for TaoCrypt::AbstractGroup:

[legend]List of all members.


Public Types
typedef Integer	Element
Public Member Functions
virtual	~AbstractGroup ()
virtual bool	Equal (const Element &a, const Element &b) const =0
virtual const Element &	Identity () const =0
virtual const Element &	Add (const Element &a, const Element &b) const =0
virtual const Element &	Inverse (const Element &a) const =0
virtual bool	InversionIsFast () const
virtual const Element &	Double (const Element &a) const
virtual const Element &	Subtract (const Element &a, const Element &b) const
virtual Element &	Accumulate (Element &a, const Element &b) const
virtual Element &	Reduce (Element &a, const Element &b) const
virtual Element	ScalarMultiply (const Element &a, const Integer &e) const
virtual Element	CascadeScalarMultiply (const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
virtual void	SimultaneousMultiply (Element results, const Element &base, const Integer exponents, unsigned int exponentsCount) const

Detailed Description

Definition at line 45 of file algebra.hpp.

Member Typedef Documentation

typedef Integer TaoCrypt::AbstractGroup::Element

Reimplemented in TaoCrypt::AbstractRing, TaoCrypt::AbstractEuclideanDomain, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Definition at line 48 of file algebra.hpp.

Constructor & Destructor Documentation

virtual TaoCrypt::AbstractGroup::~AbstractGroup ( ) [inline, virtual]

Definition at line 50 of file algebra.hpp.

00050 {}

Member Function Documentation

Integer & TaoCrypt::AbstractGroup::Accumulate	(	Element &	a,
		const Element &	b
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Definition at line 50 of file algebra.cpp.

References Add().

Referenced by CascadeScalarMultiply(), and SimultaneousMultiply().

00051 {
00052     return a = Add(a, b);
00053 }

Here is the call graph for this function:

Here is the caller graph for this function:

virtual const Element& TaoCrypt::AbstractGroup::Add	(	const Element &	a,
		const Element &	b
	)			const `[pure virtual]`

Implemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Referenced by Accumulate(), CascadeScalarMultiply(), Double(), SimultaneousMultiply(), and Subtract().

Here is the caller graph for this function:

Integer TaoCrypt::AbstractGroup::CascadeScalarMultiply	(	const Element &	x,
		const Integer &	e1,
		const Element &	y,
		const Integer &	e2
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT.

Definition at line 109 of file algebra.cpp.

References Accumulate(), Add(), TaoCrypt::Integer::BitCount(), Double(), TaoCrypt::Integer::GetBit(), Identity(), TaoCrypt::max(), and x.

00111 {
00112     const unsigned expLen = max(e1.BitCount(), e2.BitCount());
00113     if (expLen==0)
00114         return Identity();
00115 
00116     const unsigned w = (expLen <= 46 ? 1 : (expLen <= 260 ? 2 : 3));
00117     const unsigned tableSize = 1<<w;
00118     mySTL::vector<Element> powerTable(tableSize << w);
00119 
00120     powerTable[1] = x;
00121     powerTable[tableSize] = y;
00122     if (w==1)
00123         powerTable[3] = Add(x,y);
00124     else
00125     {
00126         powerTable[2] = Double(x);
00127         powerTable[2*tableSize] = Double(y);
00128 
00129         unsigned i, j;
00130 
00131         for (i=3; i<tableSize; i+=2)
00132             powerTable[i] = Add(powerTable[i-2], powerTable[2]);
00133         for (i=1; i<tableSize; i+=2)
00134             for (j=i+tableSize; j<(tableSize<<w); j+=tableSize)
00135                 powerTable[j] = Add(powerTable[j-tableSize], y);
00136 
00137         for (i=3*tableSize; i<(tableSize<<w); i+=2*tableSize)
00138             powerTable[i] = Add(powerTable[i-2*tableSize],
00139             powerTable[2*tableSize]);
00140         for (i=tableSize; i<(tableSize<<w); i+=2*tableSize)
00141             for (j=i+2; j<i+tableSize; j+=2)
00142                 powerTable[j] = Add(powerTable[j-1], x);
00143     }
00144 
00145     Element result;
00146     unsigned power1 = 0, power2 = 0, prevPosition = expLen-1;
00147     bool firstTime = true;
00148 
00149     for (int i = expLen-1; i>=0; i--)
00150     {
00151         power1 = 2*power1 + e1.GetBit(i);
00152         power2 = 2*power2 + e2.GetBit(i);
00153 
00154         if (i==0 || 2*power1 >= tableSize || 2*power2 >= tableSize)
00155         {
00156             unsigned squaresBefore = prevPosition-i;
00157             unsigned squaresAfter = 0;
00158             prevPosition = i;
00159             while ((power1 || power2) && power1%2 == 0 && power2%2==0)
00160             {
00161                 power1 /= 2;
00162                 power2 /= 2;
00163                 squaresBefore--;
00164                 squaresAfter++;
00165             }
00166             if (firstTime)
00167             {
00168                 result = powerTable[(power2<<w) + power1];
00169                 firstTime = false;
00170             }
00171             else
00172             {
00173                 while (squaresBefore--)
00174                 result = Double(result);
00175                 if (power1 || power2)
00176                     Accumulate(result, powerTable[(power2<<w) + power1]);
00177             }
00178             while (squaresAfter--)
00179                 result = Double(result);
00180             power1 = power2 = 0;
00181         }
00182     }
00183     return result;
00184 }

Here is the call graph for this function:

const Integer & TaoCrypt::AbstractGroup::Double ( const Element & a ) const [virtual]

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Definition at line 38 of file algebra.cpp.

References Add().

Referenced by CascadeScalarMultiply(), and SimultaneousMultiply().

00039 {
00040     return Add(a, a);
00041 }

Here is the call graph for this function:

Here is the caller graph for this function:

virtual bool TaoCrypt::AbstractGroup::Equal	(	const Element &	a,
		const Element &	b
	)			const `[pure virtual]`

Implemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Referenced by TaoCrypt::AbstractEuclideanDomain::Gcd().

Here is the caller graph for this function:

virtual const Element& TaoCrypt::AbstractGroup::Identity ( ) const [pure virtual]

Implemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Referenced by CascadeScalarMultiply(), and SimultaneousMultiply().

Here is the caller graph for this function:

virtual const Element& TaoCrypt::AbstractGroup::Inverse ( const Element & a ) const [pure virtual]

Implemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Referenced by SimultaneousMultiply(), and Subtract().

Here is the caller graph for this function:

virtual bool TaoCrypt::AbstractGroup::InversionIsFast ( ) const [inline, virtual]

Definition at line 56 of file algebra.hpp.

Referenced by SimultaneousMultiply().

00056 {return false;}

Here is the caller graph for this function:

Integer & TaoCrypt::AbstractGroup::Reduce	(	Element &	a,
		const Element &	b
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Definition at line 55 of file algebra.cpp.

References Subtract().

00056 {
00057     return a = Subtract(a, b);
00058 }

Here is the call graph for this function:

Integer TaoCrypt::AbstractGroup::ScalarMultiply	(	const Element &	a,
		const Integer &	e
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT.

Definition at line 100 of file algebra.cpp.

References SimultaneousMultiply().

00102 {
00103     Element result;
00104     SimultaneousMultiply(&result, base, &exponent, 1);
00105     return result;
00106 }

Here is the call graph for this function:

void TaoCrypt::AbstractGroup::SimultaneousMultiply	(	Element *	results,
		const Element &	base,
		const Integer *	exponents,
		unsigned int	exponentsCount
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT.

Definition at line 240 of file algebra.cpp.

References Accumulate(), Add(), assert, Double(), yaSSL::finished, Identity(), Inverse(), InversionIsFast(), TaoCrypt::Integer::NotNegative(), mySTL::vector< T >::push_back(), mySTL::vector< T >::reserve(), mySTL::vector< T >::resize(), and mySTL::vector< T >::size().

Referenced by ScalarMultiply().

00242 {
00243     mySTL::vector<mySTL::vector<Element> > buckets(expCount);
00244     mySTL::vector<WindowSlider> exponents;
00245     exponents.reserve(expCount);
00246     unsigned int i;
00247 
00248     for (i=0; i<expCount; i++)
00249     {
00250         assert(expBegin->NotNegative());
00251         exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 0));
00252         exponents[i].FindNextWindow();
00253         buckets[i].resize(1<<(exponents[i].windowSize-1), Identity());
00254     }
00255 
00256     unsigned int expBitPosition = 0;
00257     Element g = base;
00258     bool notDone = true;
00259 
00260     while (notDone)
00261     {
00262         notDone = false;
00263         for (i=0; i<expCount; i++)
00264         {
00265             if (!exponents[i].finished && expBitPosition == 
00266                  exponents[i].windowBegin)
00267             {
00268                 Element &bucket = buckets[i][exponents[i].expWindow/2];
00269                 if (exponents[i].negateNext)
00270                     Accumulate(bucket, Inverse(g));
00271                 else
00272                     Accumulate(bucket, g);
00273                 exponents[i].FindNextWindow();
00274             }
00275             notDone = notDone || !exponents[i].finished;
00276         }
00277 
00278         if (notDone)
00279         {
00280             g = Double(g);
00281             expBitPosition++;
00282         }
00283     }
00284 
00285     for (i=0; i<expCount; i++)
00286     {
00287         Element &r = *results++;
00288         r = buckets[i][buckets[i].size()-1];
00289         if (buckets[i].size() > 1)
00290         {
00291             for (int j = buckets[i].size()-2; j >= 1; j--)
00292             {
00293                 Accumulate(buckets[i][j], buckets[i][j+1]);
00294                 Accumulate(r, buckets[i][j]);
00295             }
00296             Accumulate(buckets[i][0], buckets[i][1]);
00297             r = Add(Double(r), buckets[i][0]);
00298         }
00299     }
00300 }

Here is the call graph for this function:

Here is the caller graph for this function:

const Integer & TaoCrypt::AbstractGroup::Subtract	(	const Element &	a,
		const Element &	b
	)			const `[virtual]`

Reimplemented in TaoCrypt::AbstractRing::MultiplicativeGroupT, TaoCrypt::EuclideanDomainOf, and TaoCrypt::ModularArithmetic.

Definition at line 43 of file algebra.cpp.

References Add(), and Inverse().

Referenced by Reduce().

00044 {
00045     // make copy of a in case Inverse() overwrites it
00046     Element a1(a);
00047     return Add(a1, Inverse(b));
00048 }

Here is the call graph for this function:

Here is the caller graph for this function:

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

mysql/src/5.1-dbg/extra/yassl/taocrypt/include/algebra.hpp
mysql/src/5.1-dbg/extra/yassl/taocrypt/src/algebra.cpp

Generated on Sun Sep 10 00:34:41 2006 for MySQL 5.1 by

1.4.7

The world's most popular open source database

TaoCrypt::AbstractGroup Class Reference

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation