primesieve.cs

Granados是一个基于.NET的SSH客户端库。同时支持SSH1和SSH2。实现了AES, Blowfish, TripleDES, RSA, DSA等加密验证算法。实现TCP协议连接。

/* ---------------------------------------------------------------------------
 *
 * Copyright (c) Routrek Networks, Inc.    All Rights Reserved..
 * 
 * This file is a part of the Granados SSH Client Library that is subject to
 * the license included in the distributed package.
 * You may not use this file except in compliance with the license.
 * 
 * ---------------------------------------------------------------------------
 * 
 * I implemented this algorithm with reference to following products or books though the algorithm is known publicly.
 *   * MindTerm ( AppGate Network Security )
 * 
 */
using System;

namespace Routrek.PKI
{
	public class PrimeSieve {

	public readonly static byte[] bitCounts = {
											0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,
											2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,
											2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,
											4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,
											2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,
											4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,
											4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,
											6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
										};

	private uint[] table;

	public PrimeSieve(int x) {
		if(x < 4)
			x = 4;

		int len = (x - 3) / (32 * 2);
		table = new uint[len];

		int max   = len * 32;
		int stop = (int)Math.Sqrt((double)max) + 1;
		for(int i = 0; i < stop ; i++) {
			if((table[i / 32] & (1 << (i & (32 - 1)))) == 0) {
				int k = 3 + i * 2;
				for (int j = i + k; j < max; j += k) {
					table[j / 32] |= ((uint)1 << (j & (32 - 1)));
				}
			}
		}
	}

	public uint AvailablePrimes() {
		uint i, bits, w, primes;
		for(i = 0, primes = 2; i < table.Length; i++) {
			w = table[i];
			for(bits = 0; w != 0; w >>= 8)
				bits += (uint)bitCounts[w & 0xff];
			primes += (32 - bits);
		}
		return primes;
	}

	public int getNextPrime(int x) {
		int p = ((x - 3) / 2) + 1;
		switch (x) {
				/* Trivial cases. */
			case 0:
				return 2;
			case 1:
				return 2;
			case 2:
				return 3;
				/* Cases above 2 are handled with the table. */
			default:
				while(true) {
					if((p / 32) >= table.Length)
						return 0;

					if((table[p / 32] & (1 << (p & (32 - 1)))) == 0)
						return p * 2 + 3;
					p++;
				}
		}
	}

}
}