pgsqlclient-checkins Mailing List for PostgreSqlClient (Page 28)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Update of /cvsroot/pgsqlclient/pgsqlclient_10/Mono.Security.Protocol.Tls/Mono.Security.Protocol.Tls/Mono.Math.Prime
In directory sc8-pr-cvs1:/tmp/cvs-serv2701

Added Files:
	ConfidenceFactor.cs PrimalityTests.cs 
Log Message:
2003-12-21 Carlos Guzmán Álvarez  <car...@te...>

	* Added files from mono:: project that are going to be needed
	for client authentication:

		Mono.Math/*

		Mono.Math.Prime/*

		Mono.Math.Prime.Generator/*

		Mono.Security.Cryptography/RSAManaged.cs

--- NEW FILE: ConfidenceFactor.cs ---
//
// Mono.Math.Prime.ConfidenceFactor.cs - Confidence factor for prime generation
//
// Authors:
//	Ben Maurer
//
// Copyright (c) 2003 Ben Maurer. All rights reserved
//

using System;

namespace Mono.Math.Prime {
	/// <summary>
	/// A factor of confidence.
	/// </summary>
	internal enum ConfidenceFactor {
		/// <summary>
		/// Only suitable for development use, probability of failure may be greater than 1/2^20.
		/// </summary>
		ExtraLow,
		/// <summary>
		/// Suitable only for transactions which do not require forward secrecy.  Probability of failure about 1/2^40
		/// </summary>
		Low,
		/// <summary>
		/// Designed for production use. Probability of failure about 1/2^80.
		/// </summary>
		Medium,
		/// <summary>
		/// Suitable for sensitive data. Probability of failure about 1/2^160.
		/// </summary>
		High,
		/// <summary>
		/// Use only if you have lots of time! Probability of failure about 1/2^320.
		/// </summary>
		ExtraHigh,
		/// <summary>
		/// Only use methods which generate provable primes. Not yet implemented.
		/// </summary>
		Provable
	}
}

--- NEW FILE: PrimalityTests.cs ---
//
// Mono.Math.Prime.PrimalityTests.cs - Test for primality
//
// Authors:
//	Ben Maurer
//
// Copyright (c) 2003 Ben Maurer. All rights reserved
//

using System;
using System.Security.Cryptography;

namespace Mono.Math.Prime {

	[CLSCompliant(false)]
	internal delegate bool PrimalityTest (BigInteger bi, ConfidenceFactor confidence);

	[CLSCompliant(false)]
	internal sealed class PrimalityTests {

		#region SPP Test
		
		private static int GetSPPRounds (BigInteger bi, ConfidenceFactor confidence)
		{
			int bc = bi.bitCount();

			int Rounds;

			// Data from HAC, 4.49
			if      (bc <= 100 ) Rounds = 27;
			else if (bc <= 150 ) Rounds = 18;
			else if (bc <= 200 ) Rounds = 15;
			else if (bc <= 250 ) Rounds = 12;
			else if (bc <= 300 ) Rounds =  9;
			else if (bc <= 350 ) Rounds =  8;
			else if (bc <= 400 ) Rounds =  7;
			else if (bc <= 500 ) Rounds =  6;
			else if (bc <= 600 ) Rounds =  5;
			else if (bc <= 800 ) Rounds =  4;
			else if (bc <= 1250) Rounds =  3;
			else		     Rounds =  2;

			switch (confidence) {
				case ConfidenceFactor.ExtraLow:
					Rounds >>= 2;
					return Rounds != 0 ? Rounds : 1;
				case ConfidenceFactor.Low:
					Rounds >>= 1;
					return Rounds != 0 ? Rounds : 1;
				case ConfidenceFactor.Medium:
					return Rounds;
				case ConfidenceFactor.High:
					return Rounds <<= 1;
				case ConfidenceFactor.ExtraHigh:
					return Rounds <<= 2;
				case ConfidenceFactor.Provable:
					throw new Exception ("The Rabin-Miller test can not be executed in a way such that its results are provable");
				default:
					throw new ArgumentOutOfRangeException ("confidence");
			}
		}

		/// <summary>
		///     Probabilistic prime test based on Rabin-Miller's test
		/// </summary>
		/// <param name="bi" type="BigInteger.BigInteger">
		///     <para>
		///         The number to test.
		///     </para>
		/// </param>
		/// <param name="confidence" type="int">
		///     <para>
		///	The number of chosen bases. The test has at least a
		///	1/4^confidence chance of falsely returning True.
		///     </para>
		/// </param>
		/// <returns>
		///	<para>
		///		True if "this" is a strong pseudoprime to randomly chosen bases.
		///	</para>
		///	<para>
		///		False if "this" is definitely NOT prime.
		///	</para>
		/// </returns>
		public static bool RabinMillerTest (BigInteger bi, ConfidenceFactor confidence)
		{
			int Rounds = GetSPPRounds (bi, confidence);

			// calculate values of s and t
			BigInteger p_sub1 = bi - 1;
			int s = p_sub1.LowestSetBit ();

			BigInteger t = p_sub1 >> s;

			int bits = bi.bitCount ();
			BigInteger a = null;
			RandomNumberGenerator rng = RandomNumberGenerator.Create ();
			BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi);

			for (int round = 0; round < Rounds; round++) {
				while (true) {		           // generate a < n
					a = BigInteger.genRandom (bits, rng);

					// make sure "a" is not 0
					if (a > 1 && a < bi)
						break;
				}

				if (a.gcd (bi) != 1) return false;

				BigInteger b = mr.Pow (a, t);

				if (b == 1) continue;              // a^t mod p = 1

				bool result = false;
				for (int j = 0; j < s; j++) {

					if (b == p_sub1) {         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
						result = true;
						break;
					}

					b = (b * b) % bi;
				}

				if (result == false)
					return false;
			}
			return true;
		}

		public static bool SmallPrimeSppTest (BigInteger bi, ConfidenceFactor confidence)
		{
			int Rounds = GetSPPRounds (bi, confidence);

			// calculate values of s and t
			BigInteger p_sub1 = bi - 1;
			int s = p_sub1.LowestSetBit ();

			BigInteger t = p_sub1 >> s;


			BigInteger.ModulusRing mr = new BigInteger.ModulusRing (bi);

			for (int round = 0; round < Rounds; round++) {

				BigInteger b = mr.Pow (BigInteger.smallPrimes [round], t);

				if (b == 1) continue;              // a^t mod p = 1

				bool result = false;
				for (int j = 0; j < s; j++) {

					if (b == p_sub1) {         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
						result = true;
						break;
					}

					b = (b * b) % bi;
				}

				if (result == false)
					return false;
			}
			return true;

		}

		#endregion


		// TODO: Implement the Lucus test
		// TODO: Implement other new primality tests
		// TODO: Implement primality proving
	}
}

2003	Jan	Feb	Mar	Apr	May	Jun	Jul (120)	Aug (95)	Sep (95)	Oct (213)	Nov (114)	Dec (64)
2004	Jan (6)	Feb (134)	Mar (88)	Apr (28)	May (22)	Jun (15)	Jul (23)	Aug (2)	Sep (15)	Oct (2)	Nov (6)	Dec
2005	Jan (8)	Feb (6)	Mar	Apr (42)	May (3)	Jun	Jul	Aug	Sep (84)	Oct	Nov	Dec
2006	Jan	Feb	Mar (84)	Apr (46)	May (40)	Jun (8)	Jul	Aug	Sep	Oct	Nov	Dec

pgsqlclient-checkins Mailing List for PostgreSqlClient (Page 28)

pgsqlclient-checkins — Mailing list for CVS commit messages.