sl@0: /*
sl@0: * Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: * All rights reserved.
sl@0: * This component and the accompanying materials are made available
sl@0: * under the terms of the License "Eclipse Public License v1.0"
sl@0: * which accompanies this distribution, and is available
sl@0: * at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: *
sl@0: * Initial Contributors:
sl@0: * Nokia Corporation - initial contribution.
sl@0: *
sl@0: * Contributors:
sl@0: *
sl@0: * Description: 
sl@0: *
sl@0: */
sl@0: 
sl@0: 
sl@0: #include <bigint.h>
sl@0: #include <e32std.h>
sl@0: #include <securityerr.h>
sl@0: #include "words.h"
sl@0: #include "primes.h"
sl@0: #include "algorithms.h"
sl@0: #include "mont.h"
sl@0: #include "stackinteger.h"
sl@0: 
sl@0: static TBool IsSmallPrime(TUint aK);
sl@0: 
sl@0: static inline void EliminateComposites(TUint* aS, TUint aPrime, TUint aJ, 
sl@0: 	TUint aMaxIndex)
sl@0: 	{
sl@0: 	for(; aJ<aMaxIndex; aJ+=aPrime)
sl@0: 		ArraySetBit(aS, aJ);
sl@0: 	}
sl@0: 
sl@0: static inline TInt FindLeastSignificantZero(TUint aX)
sl@0: 	{
sl@0: 	aX = ~aX;
sl@0: 	int i = 0;
sl@0: 	if( aX << 16 == 0 ) aX>>=16, i+=16;
sl@0: 	if( aX << 24 == 0 ) aX>>=8, i+=8;
sl@0: 	if( aX << 28 == 0 ) aX>>=4, i+=4;
sl@0: 	if( aX << 30 == 0 ) aX>>=2, i+=2;
sl@0: 	if( aX << 31 == 0 ) ++i;
sl@0: 	return i;
sl@0: 	}
sl@0: 
sl@0: static inline TInt FindFirstPrimeCandidate(TUint* aS, TUint aBitLength)
sl@0: 	{
sl@0: 	assert(aBitLength % WORD_BITS == 0);
sl@0: 	TUint i=0;
sl@0: 	//The empty statement at the end of this is stop warnings in all compilers
sl@0: 	for(; aS[i] == KMaxTUint && i<BitsToWords(aBitLength); i++) {;}
sl@0: 
sl@0: 	if(i == BitsToWords(aBitLength))
sl@0: 		return -1;
sl@0: 	else
sl@0: 		{
sl@0: 		assert( FindLeastSignificantZero((TUint)(aS[i])) >= 0 );
sl@0: 		assert( FindLeastSignificantZero((TUint)(aS[i])) <= 31 );
sl@0: 		return i*WORD_BITS + FindLeastSignificantZero((TUint32)(aS[i]));
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: static inline TUint FindSmallestIndex(TUint aPrime, TUint aRemainder)
sl@0: 	{
sl@0: 	TUint& j = aRemainder;
sl@0: 	if(j)
sl@0: 		{
sl@0: 		j = aPrime - aRemainder;
sl@0: 		if( j & 0x1L )
sl@0: 			{
sl@0: 			//if j is odd then this + j is even so we actually want 
sl@0: 			//the next number for which (this + j % p == 0) st this + j is odd
sl@0: 			//that is: this + j + p == 0 mod p
sl@0: 			j += aPrime;
sl@0: 			}
sl@0: 		//Turn j into an index for a bit array representing odd numbers only
sl@0: 		j>>=1;
sl@0: 		}
sl@0: 	return j;
sl@0: 	}
sl@0: 
sl@0: static inline TUint RabinMillerRounds(TUint aBits) 
sl@0: 	{
sl@0: 	//See HAC Table 4.4
sl@0: 	if(aBits > 1300)
sl@0: 		return 2;
sl@0: 	if (aBits > 850)
sl@0: 		return 3;
sl@0: 	if (aBits > 650)
sl@0: 		return 4;
sl@0: 	if (aBits > 550)
sl@0: 		return 5;
sl@0: 	if (aBits > 450)
sl@0: 		return 6;
sl@0: 	if (aBits > 400)
sl@0: 		return 7;
sl@0: 	if (aBits > 350)
sl@0: 		return 8;
sl@0: 	if (aBits > 300)
sl@0: 		return 9;
sl@0: 	if (aBits > 250)
sl@0: 		return 12;
sl@0: 	if (aBits > 200)
sl@0: 		return 15;
sl@0: 	if (aBits > 150)
sl@0: 		return 18;
sl@0: 	if (aBits > 100)
sl@0: 		return 27;
sl@0: 	//All of the above are optimisations on the worst case.  The worst case
sl@0: 	//chance of odd composite integers being declared prime by Rabin-Miller is
sl@0: 	//(1/4)^t where t is the number of rounds.  Thus, t = 40 means that the
sl@0: 	//chance of declaring a composite integer prime is less than 2^(-80).  See
sl@0: 	//HAC Fact 4.25 and most of chapter 4 for more details.
sl@0: 	return 40;
sl@0: 	}
sl@0: 
sl@0: static TBool HasSmallDivisorL(const TInteger& aPossiblePrime)
sl@0: 	{
sl@0: 	assert(aPossiblePrime.IsOdd());
sl@0: 	//Start checking at the first odd prime, whether it is even should have
sl@0: 	//already been checked
sl@0: 	for( TUint i=1; i < KPrimeTableSize; i++ )
sl@0: 		{
sl@0: 		if( aPossiblePrime.ModuloL(KPrimeTable[i]) == 0 )
sl@0: 			{
sl@0: 			return ETrue;
sl@0: 			}
sl@0: 		}
sl@0: 	return EFalse;
sl@0: 	}
sl@0: 
sl@0: static TBool RabinMillerIterationL(const CMontgomeryStructure& aMont, 
sl@0: 	const TInteger& aProbablePrime, const TInteger& aBase)
sl@0: 	{
sl@0: 	//see HAC 4.24
sl@0: 	const TInteger& n = aProbablePrime;
sl@0: 	assert(n > KLastSmallPrimeSquared);
sl@0: 	assert(n.IsOdd());
sl@0: 	assert(aBase > TInteger::One());
sl@0: 
sl@0: 	RInteger nminus1 = n.MinusL(TInteger::One());
sl@0: 	CleanupStack::PushL(nminus1);
sl@0: 	assert(aBase < nminus1);
sl@0: 
sl@0: 	// 1) find (s | 2^s*r == n-1) where r is odd
sl@0: 	// we want the largest power of 2 that divides n-1
sl@0: 	TUint s=0;
sl@0: 	for(;;s++)
sl@0: 		{
sl@0: 		if(nminus1.Bit(s))
sl@0: 			{
sl@0: 			break;
sl@0: 			}
sl@0: 		}
sl@0: 	// (r = (n-1) / 2^s) which is equiv to (n-1 >>= s)
sl@0: 	RInteger r = RInteger::NewL(nminus1);
sl@0: 	CleanupStack::PushL(r);
sl@0: 	r >>= s;
sl@0: 
sl@0: 	//At no point do we own y, aMont owns it
sl@0: 	const TInteger* y = &(aMont.ExponentiateL(aBase, r));
sl@0: 
sl@0: 	TBool probablePrime = EFalse;
sl@0: 	
sl@0: 	TUint j=1;
sl@0: 	if( *y == TInteger::One() || *y == nminus1 )
sl@0: 		{
sl@0: 		probablePrime = ETrue;
sl@0: 		}
sl@0: 	else
sl@0: 		{
sl@0: 		for(j=1; j<s; j++)
sl@0: 			{
sl@0: 			y = &(aMont.SquareL(*y));
sl@0: 			if(*y == nminus1)
sl@0: 				{
sl@0: 				probablePrime = ETrue;
sl@0: 				break;
sl@0: 				}
sl@0: 			}
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy(&r);
sl@0: 	CleanupStack::PopAndDestroy(&nminus1);//y,r,nminus1
sl@0: 	return probablePrime;
sl@0: 	}
sl@0: 
sl@0: static TBool RabinMillerTestL(const CMontgomeryStructure& aMont, 
sl@0: 	const TInteger& aProbablePrime, TUint aRounds) 
sl@0: 	{
sl@0: 	const TInteger& n = aProbablePrime;
sl@0: 	assert(n > KLastSmallPrimeSquared);
sl@0: 	
sl@0: 	RInteger nminus2 = n.MinusL(TInteger::Two());
sl@0: 	CleanupStack::PushL(nminus2);
sl@0: 
sl@0: 	for(TUint i=0; i<aRounds; i++)
sl@0: 		{
sl@0: 		RInteger base = RInteger::NewRandomL(TInteger::Two(), nminus2);
sl@0: 		CleanupStack::PushL(base);
sl@0: 		if(!RabinMillerIterationL(aMont, n, base))
sl@0: 			{
sl@0: 			CleanupStack::PopAndDestroy(2, &nminus2);//base, nminus2
sl@0: 			return EFalse;
sl@0: 			}
sl@0: 		CleanupStack::PopAndDestroy(&base);
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy(&nminus2);
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: static TBool IsStrongProbablePrimeL(const TInteger& aPrime) 
sl@0: 	{
sl@0: 	CMontgomeryStructure* mont = CMontgomeryStructure::NewLC(aPrime);
sl@0: 	//This should be using short circuit evaluation
sl@0: 	TBool probablePrime = RabinMillerIterationL(*mont, aPrime, TInteger::Two())
sl@0: 		&& RabinMillerTestL(*mont, aPrime,RabinMillerRounds(aPrime.BitCount()));
sl@0: 	CleanupStack::PopAndDestroy(mont);
sl@0: 	return probablePrime;
sl@0: 	}
sl@0: 
sl@0: /* In the _vast_ majority of cases this simply checks that your chosen random
sl@0:  * number is >= KLastSmallPrimeSquared and return EFalse and lets the normal
sl@0:  * prime generation routines handle the situation.  In the case where it is
sl@0:  * smaller, it generates a provable prime and returns ETrue.  The algorithm for
sl@0:  * finding a provable prime < KLastPrimeSquared is not the most efficient in the
sl@0:  * world, but two points come to mind
sl@0:  * 1) The two if statements hardly _ever_ evaluate to ETrue in real life.
sl@0:  * 2) Even when it is, the distribution of primes < KLastPrimeSquared is pretty
sl@0:  * dense, so you aren't going to have check many.
sl@0:  * This function is essentially here for two reasons:
sl@0:  * 1) Ensures that it is possible to generate primes < KLastPrimeSquared (the
sl@0:  * test code does this)
sl@0:  * 2) Ensures that if you request a prime of a large bit size that there is an
sl@0:  * even probability distribution across all integers < 2^aBits
sl@0:  */
sl@0: TBool TInteger::SmallPrimeRandomizeL(void)
sl@0: 	{
sl@0: 	TBool foundPrime = EFalse;
sl@0: 	//If the random number we've chosen is less than KLastSmallPrime,
sl@0: 	//testing for primality is easy.
sl@0: 	if(*this <= KLastSmallPrime)
sl@0: 		{
sl@0: 		//If Zero or One, or two, next prime number is two
sl@0: 		if(IsZero() || *this == One() || *this == Two())
sl@0: 			{
sl@0: 			CopyL(TInteger::Two());
sl@0: 			foundPrime = ETrue;
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			//Make sure any number we bother testing is at least odd
sl@0: 			SetBit(0);
sl@0: 			//Binary search the small primes.
sl@0: 			while(!IsSmallPrime(ConvertToUnsignedLong()))
sl@0: 				{
sl@0: 				//If not prime, add two and try the next odd number.
sl@0: 
sl@0: 				//will never carry as the minimum size of an RInteger is 2
sl@0: 				//words.  Much bigger than KLastSmallPrime on 32bit
sl@0: 				//architectures.
sl@0: 				IncrementNoCarry(Ptr(), Size(), 2);
sl@0: 				}
sl@0: 			assert(IsSmallPrime(ConvertToUnsignedLong()));
sl@0: 			foundPrime = ETrue;
sl@0: 			}
sl@0: 		}
sl@0: 	else if(*this <= KLastSmallPrimeSquared)
sl@0: 		{
sl@0: 		//Make sure any number we bother testing is at least odd
sl@0: 		SetBit(0);
sl@0: 
sl@0: 		while(HasSmallDivisorL(*this) && *this <= KLastSmallPrimeSquared)
sl@0: 			{
sl@0: 			//If not prime, add two and try the next odd number.
sl@0: 
sl@0: 			//will never carry as the minimum size of an RInteger is 2
sl@0: 			//words.  Much bigger than KLastSmallPrime on 32bit
sl@0: 			//architectures.
sl@0: 			IncrementNoCarry(Ptr(), Size(), 2);
sl@0: 			}
sl@0: 		//If we exited while loop because it had no small divisor then it is
sl@0: 		//prime.  Otherwise, we've exceeded the limit of what we can provably
sl@0: 		//generate.  Therefore the normal prime gen routines will be run on it
sl@0: 		//now.
sl@0: 		if(*this < KLastSmallPrimeSquared)
sl@0: 			{
sl@0: 			foundPrime = ETrue;
sl@0: 			}
sl@0: 		}
sl@0: 	//This doesn't mean there is no such prime, simply means that the number
sl@0: 	//wasn't less than KSmallPrimeSquared and needs to be handled by the normal
sl@0: 	//prime generation routines.
sl@0: 	return foundPrime;
sl@0: 	}
sl@0: 
sl@0: void TInteger::PrimeRandomizeL(TUint aBits, TRandomAttribute aAttr)
sl@0: 	{
sl@0: 	assert(aBits > 1); 
sl@0: 	
sl@0: 	//"this" is "empty" currently.  Consists of Size() words of 0's.  This is just
sl@0: 	//checking that sign flag is positive as we don't set it later.
sl@0: 	assert(NotNegative());
sl@0: 
sl@0: 	//Flag for the whole function saying if we've found a prime
sl@0: 	TBool foundProbablePrime = EFalse;
sl@0: 
sl@0: 	//Find 2^aBits + 1 -- any prime we find must be less than this.
sl@0: 	RInteger max = RInteger::NewEmptyL(BitsToWords(aBits)+1);
sl@0: 	CleanupStack::PushL(max);
sl@0: 	max.SetBit(aBits);
sl@0: 	assert(max.BitCount()-1 == aBits);
sl@0: 
sl@0: 	// aBits 	| approx number of odd numbers you must try to have a 50% 
sl@0: 	//			chance of finding a prime
sl@0: 	//---------------------------------------------------------
sl@0: 	// 512		| 122		
sl@0: 	// 1024		| 245
sl@0: 	// 2048		| 1023
sl@0: 	//Therefore if we are generating larger than 1024 bit numbers we'll use a
sl@0: 	//bigger bit array to have a better chance of avoiding re-generating it.
sl@0: 	TUint sLength = aBits > 1024 ? 1024 : 512;
sl@0: 	RInteger S = RInteger::NewEmptyL(BitsToWords(sLength));
sl@0: 	CleanupStack::PushL(S);
sl@0: 
sl@0: 	while(!foundProbablePrime)
sl@0: 		{
sl@0: 		//Randomly choose aBits
sl@0: 		RandomizeL(aBits, aAttr);
sl@0: 
sl@0: 		//If the random number chosen is less than KSmallPrimeSquared, we have a
sl@0: 		//special set of routines.
sl@0: 		if(SmallPrimeRandomizeL())
sl@0: 			{
sl@0: 			foundProbablePrime = ETrue;
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			//if it was <= KLastSmallPrimeSquared then it would have been
sl@0: 			//handled by SmallPrimeRandomizeL()
sl@0: 			assert(*this > KLastSmallPrimeSquared);
sl@0: 
sl@0: 			//Make sure any number we bother testing is at least odd
sl@0: 			SetBit(0);
sl@0: 
sl@0: 			//Ensure that this + 2*sLength < max
sl@0: 			RInteger temp = max.MinusL(*this);
sl@0: 			CleanupStack::PushL(temp);
sl@0: 			++temp;
sl@0: 			temp >>=1;
sl@0: 			if(temp < sLength)
sl@0: 				{
sl@0: 				//if this + 2*sLength >= max then we use a smaller sLength to
sl@0: 				//ensure we don't find a number that is outside of our bounds
sl@0: 				//(and bigger than our allocated memory for this)
sl@0: 
sl@0: 				//temp must be less than KMaxTUint as sLength is a TUint 
sl@0: 				sLength = temp.ConvertToUnsignedLong();	
sl@0: 				}
sl@0: 			CleanupStack::PopAndDestroy(&temp);
sl@0: 
sl@0: 			//Start at 1 as no point in checking against 2 (all odd numbers)
sl@0: 			for(TUint i=1; i<KPrimeTableSize; i++)
sl@0: 				{
sl@0: 				//no need to call ModuloL as we know KPrimeTable[i] is not 0
sl@0: 				TUint remainder = Modulo(*this, KPrimeTable[i]);
sl@0: 				TUint index = FindSmallestIndex(KPrimeTable[i], remainder);
sl@0: 				EliminateComposites(S.Ptr(), KPrimeTable[i], index, sLength);
sl@0: 				}
sl@0: 			TInt j = FindFirstPrimeCandidate(S.Ptr(), sLength);
sl@0: 			TInt prev = 0;
sl@0: 			for(; j>=0; j=FindFirstPrimeCandidate(S.Ptr(), sLength))
sl@0: 				{
sl@0: 				ArraySetBit(S.Ptr(), j);
sl@0: 
sl@0: 				//should never carry as we earlier made sure that 2*j + this < max
sl@0: 				//where max is 1 bit more than we asked for.
sl@0: 				IncrementNoCarry(Ptr(), Size(), 2*(j-prev));
sl@0: 
sl@0: 				assert(*this < max);
sl@0: 				assert(!HasSmallDivisorL(*this));
sl@0: 
sl@0: 				prev = j;
sl@0: 
sl@0: 				if( IsStrongProbablePrimeL(*this) )
sl@0: 					{
sl@0: 					foundProbablePrime = ETrue;
sl@0: 					break;
sl@0: 					}
sl@0: 				}
sl@0: 			//This clears the memory
sl@0: 			S.CopyL(0, EFalse);
sl@0: 			}
sl@0: 		}
sl@0: 	CleanupStack::PopAndDestroy(2, &max);
sl@0: 	}
sl@0: 
sl@0: EXPORT_C TBool TInteger::IsPrimeL(void) const
sl@0: 	{
sl@0: 	if( NotPositive() )
sl@0: 		{
sl@0: 		return EFalse;
sl@0: 		}
sl@0: 	else if( IsEven() )
sl@0: 		{
sl@0: 		return *this == Two();
sl@0: 		}
sl@0: 	else if( *this <= KLastSmallPrime )
sl@0: 		{
sl@0: 		assert(KLastSmallPrime < KMaxTUint);
sl@0: 		return IsSmallPrime(this->ConvertToUnsignedLong());
sl@0: 		}
sl@0: 	else if( *this <= KLastSmallPrimeSquared )
sl@0: 		{
sl@0: 		return !HasSmallDivisorL(*this);
sl@0: 		}
sl@0: 	else 
sl@0: 		{
sl@0: 		return !HasSmallDivisorL(*this) && IsStrongProbablePrimeL(*this);
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: // Method is excluded from coverage due to the problem with BullsEye on ONB.
sl@0: // Manually verified that this method is functionally covered.
sl@0: #ifdef _BullseyeCoverage
sl@0: #pragma suppress_warnings on
sl@0: #pragma BullseyeCoverage off
sl@0: #pragma suppress_warnings off
sl@0: #endif
sl@0: 
sl@0: static TBool IsSmallPrime(TUint aK) 
sl@0: 	{
sl@0: 	//This is just a binary search of our small prime table.
sl@0: 	TUint l = 0;
sl@0: 	TUint u = KPrimeTableSize;
sl@0: 	while( u > l )
sl@0: 		{
sl@0: 		TUint m = (l+u)>>1;
sl@0: 		TUint p = KPrimeTable[m];
sl@0: 		if(aK < p)
sl@0: 			u = m;
sl@0: 		else if (aK > p)
sl@0: 			l = m + 1;
sl@0: 		else
sl@0: 			return ETrue;
sl@0: 		}
sl@0: 	return EFalse;
sl@0: 	}