MAXimal

���������: 10 Jun 2008 18:18
�������������: 10 Jun 2008 18:40

���������� [������]

���� BPSW �� �������� �����


��������

�������� BPSW - ��� ���� ����� �� ��������. ���� �������� ������ �� �������� ��� �������������: ������ ����� (Ballie), ���� �������� (Pomerance), ���� �������� (Selfridge), ������� �������� (Wagstaff). �������� ��� ��������� � 1980 ����. �� ����������� ���� � ��������� �� ���� ������� �� ������ ������������, ����� ��� � �� ���� ������� ��������������.

�������� BPSW ��� �������� �� ���� ������ �� 1015. ����� ����, ����������� �������� ����� � ������� ��������� PRIMO (��. [6]), ���������� �� ����� �� �������� � ������� ������������� ������. ���������, ���������� ��� ����, �� ����� �� ������ ������������, �� ��������� ���� ������ �����������, ��� �� ���������� �� ������ BPSW-��������������, �������� 1010000 (������������� ����� - ��������� �����, �� ������� �������� ��� ��������� "�������"). � �� �� �����, ���� �������� � 1984 ���� ���������� ������������� �������������� ����, ��� ���������� ����������� ��������� BPSW-������������� �����.

��������� ��������� BPSW ���� O (log3(N)) ������� ��������. ���� �� ���������� �������� BPSW � ������� �������, ��������, ������ �������-������, �� �������� BPSW ������ ����������� � 3-7 ��� ���������.

�������� ������� ����������� �� ��������. ��-��������, ������ ������������ �������������� ������, ��������� ��� ��������, ���������� �� �������� BPSW ��� �������� ����� �� ��������.


������� ��������

�������� ����� ��������� ��������� ����������, ������������ ���� �� ����� ������ ��������. � ����� ������ �������� ����� ���:

1. ��������� ���� �������-������ �� ��������� 2.

2. ��������� ������� ���� ������-���������, ��������� ������������������ ������ � ����������� ���������.

3. ������� "�������" ������ � ��� ������, ����� ��� ����� ������� "�������".

+0. ����� ����, � ������ ��������� ����� �������� �������� �� ����������� ��������, ������, �� 1000. ��� �������� ��������� �������� ������ �� ��������� ������, ������, ��������� �������� �������� �� �������.

����, �������� BPSW ������������ �� ���������:

1. (����) ���� �������-������ � ���� ������-��������� ���� � ���������, �� ������ � ���� �������: ��������� ��������� ����� ����� ����������� ���������� ��� �������. � �������� ������� ��� ��������� �� ��������� �������.

2. (�������������) ���� �������-������ � ���� ������-��������� ���� � ���������, �� ������� �� ��������� �� ����� ����� ������������.

�� ����� ����, ������ ������������� ����� �� ��� � ������� - ������������� ��������������-������������ ��������� ��������� ����. ��� �� �����, �� �������� �� ������ �������������� �� ��� ��� �� �����, ������� ������� ����� ������� ������ ������������� ������.


���������� ���������� � ������ ������

��� ��������� � ������ ������ ����� ����������� �� C++. ��� ��������� ������������� ������ �� ����������� Microsoft C++ 8.0 SP1 (2005), ����� ������ ��������������� �� g++.

��������� ����������� � �������������� �������� (templates), ��� ��������� ��������� �� ��� � ���������� �������� �����, ��� � ����������� �������, ����������� ������� ����������. [ ���� ������� ���������� � ������ �� ������ - TODO ]

� ����� ������ ����� ��������� ������ ����� ������������ �������, ������ �� ��������������� ������� ����� ������� � ���������� � ������. ����� ����� ��������� ������ ��������� ���� ������� ������ � �������������:

//! ������ 64-������� �����
long long abs (long long n);
unsigned long long abs (unsigned long long n);

//! ���������� true, ���� n ������
template <class T>
bool even (const T & n);

//! ����� ����� �� 2
template <class T>
void bisect (T & n);

//! �������� ����� �� 2
template <class T>
void redouble (T & n);

//! ���������� true, ���� n - ������ ������� �������� �����
template <class T>
bool perfect_square (const T & n);

//! ��������� ������ �� �����, �������� ��� ����
template <class T>
T sq_root (const T & n);

//! ���������� ���������� ��� � �����
template <class T>
unsigned bits_in_number (T n);

//! ���������� �������� k-�� ���� ����� (���� ���������� � ����)
template <class T>
bool test_bit (const T & n, unsigned k);

//! �������� a *= b (mod n)
template <class T>
void mulmod (T & a, T b, const T & n);

//! ��������� a^k (mod n)
template <class T, class T2>
T powmod (T a, T2 k, const T & n);

//! ��������� ����� n � ����� q*2^p
template <class T>
void transform_num (T n, T & p, T & q);

//! �������� �������
template <class T, class T2>
T gcd (const T & a, const T2 & b);

//! ��������� jacobi(a,b) - ������ �����
template <class T>
T jacobi (T a, T b)

//! ��������� pi(b) ������ ������� �����. ���������� ������ � �������� � � pi - pi(b)
template <class T, class T2>
const std::vector & get_primes (const T & b, T2 & pi);

//! ����������� �������� n �� ��������, ������������ ��� �������� �� m.
//! ���������: 1 - ���� n ����� �������, p - ��� ��������� ��������, 0 - ���� ����������
template <class T, class T2>
T2 prime_div_trivial (const T & n, T2 m);

���� �������-������

� �� ���� ��������� �������� �� ����� �������-������, ��������� �� ����������� �� ������ ����������, � ��� ����� � �� ������� ����� (��������. ��. [5]).

������ ����, ��� �������� ��� ������ ���� O (log3(N)) ������� �������� � ������� ������� ���������� ����� ���������:

template <class T, class T2>
bool miller_rabin (T n, T2 b)
{

	// ������� ��������� ����������� ������
	if (n == 2)
		return true;
	if (n < 2 || even (n))
		return false;

	// ���������, ��� n � b ������� ������ (����� ��� �������� � ������)
	// ���� ��� �� ������� ������, �� ���� n �� ������, ���� ����� ��������� b
	if (b < 2)
		b = 2;
	for (T g; (g = gcd (n, b)) != 1; ++b)
		if (n > g)
			return false;

	// ��������� n-1 = q*2^p
	T n_1 = n;
	--n_1;
	T p, q;
	transform_num (n_1, p, q);

	// ��������� b^q mod n, ���� ��� ����� 1 ��� n-1, �� n ������� (��� �������������)
	T rem = powmod (T(b), q, n);
	if (rem == 1 || rem == n_1)
		return true;

	// ������ ��������� b^2q, b^4q, ... , b^((n-1)/2)
	// ���� �����-���� �� ��� ����� n-1, �� n ������� (��� �������������)
	for (T i=1; i<p; i++)
	{
		mulmod (rem, rem, n);
		if (rem == n_1)
			return true;
	}

	return false;

}

������� ���� ������-���������

������� ���� ������-��������� ������� �� ���� ������: ��������� ��������� ��� ���������� ���������� ���������, � �������� ��������� ������, ������������ � ���� ����������.

�������� ���������

����� ������������������ 5, -7, 9, -11, 13, ... ����� ������ ����� D, ��� �������� J (D, N) = -1 � gcd (D, N) = 1, ��� J(x,y) - ������ �����.

����������� ��������� ����� P = 1 � Q = (1 - D) / 4.

������� ��������, ��� �������� ��������� �� ���������� ��� �����, ������� �������� ������� ����������. �������������, ���� ����� �������� ������ ���������, �� ������� D ����� �� sqrt(N), �� ������� ��������, ��� gcd (D, N) > 1, �.�. �����������, ��� ����� N ���������.

����� ����, ��������� ��������� ����� ��������� ����������� ��� ������ ����� � ��� �������; �������, �������� ���� ������� �� �������� �����.

����� �������, ����� ������� ��������� ������� ���������, ��� ����� N �������� ��������, ������� 2, � �� �������� ������ ���������, ����� (��� ������������ ���� �� ������ �������) ����� ����� ����� �� ��������� � ����������� "���������".

�������, �������, ��� ���� D ��� ���������� ����� N �������� ������� �������, �� �������� � �������������� ����� ������ �������� ������������. ���� �� �������� ������ �������� �� ���� (����������� ������ ���������� 4-�������� �����), ��� �� ����� ����������� ����� ������� �� ������� ���������. �������, ��������, �� ������� [1; 106] max(D) = 47, � �� ������� [1019; 1019+106] max(D) = 67. ����� ����, ����� � ������� � 1980 ���� ������������ �������� ��� ���������� (��. Ribenboim, 1995/96, ���. 142).

������� �������� ������

����������� ��������� ������ �������� ����� D, P � Q �����, ��� D = P2 - 4*Q ? 0, � P > 0.

(�������� ��������, ��� ���������, ����������� �� ��������� ���������, ������������� ���� ��������)

������������������ ������ - ��� ������������������ Uk � Vk, ������������ ��������� �������:

U0 = 0
U1 = 1
Uk = P Uk-1 - Q Uk-2
V0 = 2
V1 = P
Vk = P Vk-1 - Q Vk-2

�����, ����� M = N - J (D, N).

���� N �������, � gcd (N, Q) = 1, �� �����:

UM = 0 (mod N)

� ���������, ����� ��������� D, P, Q ��������� ���������� ���������, �����:

UN+1 = 0 (mod N)

��������, ������ ������, �������. ��� �� �����, ������������� ����� ��� ������ ��������� ����������� �� ����� �����, �� ���, ����������, � ������������ �������� ������.

����, �������� ������ ����������� � ���������� UM � ��������� ��� � ����.

�����, ���������� ����� �����-�� ������ ��������� ���������� UK, �����, �������, �������� ������������� ������ � ���� ��������� �� ���� ��.

�����:

Uk = (ak - bk) / (a - b),
Vk = ak + bk,

��� a � b - ��������� ����� ����������� ��������� x2 - P x + Q = 0.

������ ��������� ��������� ����� �������� �����������:

U2k = Uk Vk (mod N)
V2k = Vk2 - 2 Qk (mod N)

������, ���� ����������� M = E 2T, ��� E - �������� �����, �� ����� ��������:

UM = UE VE V2E V4E ... V2T-2E V2T-1E = 0 (mod N),

� ���� �� ���� �� ���������� ����� ���� �� ������ N.

�������, ��� ���������� ��������� UE � VE, � ��� ����������� ��������� V2E V4E ... V2T-2E V2T-1E ����� �������� ��� �� ���.

����� �������, �������� ��������� ������ ��������� UE � VE ��� ��������� E.

������� ���������� ��������� ������� ��� �������� ������ ������������������� ������:

Ui+j = (Ui Vj + Uj Vi) / 2 (mod N)
Vi+j = (Vi Vj + D Ui Uj) / 2 (mod N)

������� �������� ��������, ��� ������� ����������� � ���� (mod N).

������� ��� ������������ ����� ������, � ����� �� �������������� �������.

������, ������� ��������� ��� �������� � ��� �������� ������ ������������������� ������, ������� � ������ ��������� ���������� UE � VE.

�������������, ���������� �������� ������ ����� E. ������� ������� ��������� - UE � VE - �������, ��������������, U1 � V1. �������� �� ���� ����� ����� E �� ����� ������� � ����� �������, ��������� ������ ����� ������ ��� (��������� ���� ������������������). ��� ������� i-�� ���� ����� ��������� U2 i � V2 i �� ���������� ������ � ������� ������ ��������. ����� ����, ���� ������� i-�� ��� ����� �������, �� � ������ ����� ���������� ������� U2 i � V2 i � ������� ������ ��������. �� ��������� ���������, �������������� �� O (log(E)), �� ������� ������� UE � VE.

���� UE ��� VE ��������� ������� ���� (mod N), �� ����� N ������� (��� �������������). ���� ��� ��� ������� �� ����, �� ��������� V2E, V4E, ... V2T-2E, V2T-1E. ���� ���� �� ���� �� ��� ������� � ���� �� ������ N, �� ����� N ������� (��� �������������). ����� ����� N ���������.

���������� ��������� ���������

������, ����� �� ����������� �������� ������, ����� ����� �������� ������������ �� ��� ���������� D,P,Q, ����� �� �������� ��������� ������� � �������� �������� ���������.

�������� ������� ���������� � ����������:

P > 0,
D = P2 - 4*Q ? 0.

������ ��������� �������� ���� ����������.

D �� ������ ���� ������ ��������� (mod N).

�������������, ����� �������:

D = b2, ������ J(D,N) = 1, P = b + 2, Q = b + 1, ������ Un-1 = (Qn-1 - 1) / (Q - 1).

�.�. ���� D - ������ �������, �� �������� ������ ���������� ����������� ������� ������������� ������.

���� �� ������ �������� �������� ��������� - �����������, ����� J(D,N) = -1.

��������, ����� ������� ������ ����� D �� ������������������ 5, -7, 9, -11, 13, ..., ��� �������� J(D,N) = -1. ����� ����� P = 1. ����� Q = (1 - D) / 4. ���� ������ ��� ��������� ����������.

�������, ������� � ������ ������� ������ D. ����� �������� ��� �� ������������������ 5, 9, 13, 17, 21, ... ����� ����� P - ���������� ��������, ������������� sqrt(D). ����� Q = (P2 - D) / 4.

�������, ��� �� ������ ����������� ������� ���������� ���������� ������ ������� � ��� ��������� - ������������� ����� ���������� ��� ��������� �������� ������ ���������. ��� �������� ��������, ��������, ������������ ����������, �������� ����� �������: ��� ������������� ������-��������� �� �������� �������������� �������-������, �� ������� ����, �� ������ ������������ ������� �� ����.

���������� �������� ��������� ������-���������

������ �������� ������ ����������� ��������:

template <class T, class T2>
bool lucas_selfridge (const T & n, T2 unused)
{

	// ������� ��������� ����������� ������
	if (n == 2)
		return true;
	if (n < 2 || even (n))
		return false;

	// ���������, ��� n �� �������� ������ ���������, ����� �������� ���� ������
	if (perfect_square (n))
		return false;

	// �������� ���������: ������� ������ ����� d �����, ���:
	// jacobi(d,n)=-1 � ��� ����������� ���� { 5,-7,9,-11,13,... }
	T2 dd;
	for (T2 d_abs = 5, d_sign = 1; ; d_sign = -d_sign, ++++d_abs)
	{
		dd = d_abs * d_sign;
		T g = gcd (n, d_abs);
		if (1 < g && g < n)
			// ����� �������� - d_abs
			return false;
		if (jacobi (T(dd), n) == -1)
			break;
	}

	// ��������� ���������
	T2
		p = 1,
		q = (p*p - dd) / 4;
	
	// ��������� n+1 = d*2^s
	T n_1 = n;
	++n_1;
	T s, d;
	transform_num (n_1, s, d);

	// �������� ������
	T
		u = 1,
		v = p,
		u2m = 1,
		v2m = p,
		qm = q,
		qm2 = q*2,
		qkd = q;
	for (unsigned bit = 1, bits = bits_in_number(d); bit < bits; bit++)
	{
		mulmod (u2m, v2m, n);
		mulmod (v2m, v2m, n);
		while (v2m < qm2)
			v2m += n;
		v2m -= qm2;
		mulmod (qm, qm, n);
		qm2 = qm;
		redouble (qm2);
		if (test_bit (d, bit))
		{
			T t1, t2;
			t1 = u2m;
			mulmod (t1, v, n);
			t2 = v2m;
			mulmod (t2, u, n);
			
			T t3, t4;
			t3 = v2m;
			mulmod (t3, v, n);
			t4 = u2m;
			mulmod (t4, u, n);
			mulmod (t4, (T)dd, n);

			u = t1 + t2;
			if (!even (u))
				u += n;
			bisect (u);
			u %= n;

			v = t3 + t4;
			if (!even (v))
				v += n;
			bisect (v);
			v %= n;
			mulmod (qkd, qm, n);
		}
	}

	// ����� ������� (��� ������-�������)
	if (u == 0 || v == 0)
		return true;

	// ����������� ���������� �����
	T qkd2 = qkd;
	redouble (qkd2);
	for (T2 r = 1; r < s; ++r)
	{
		mulmod (v, v, n);
		v -= qkd2;
		if (v < 0) v += n;
		if (v < 0) v += n;
		if (v >= n) v -= n;
		if (v >= n) v -= n;
		if (v == 0)
			return true;
		if (r < s-1)
		{
			mulmod (qkd, qkd, n);
			qkd2 = qkd;
			redouble (qkd2);
		}
	}

	return false;

}

��� BPSW

������ �������� ������ �������������� ���������� ���� 3 ������: �������� �� ��������� ����������� ��������, ���� �������-������, ������� ���� ������-���������.

template <class T>
bool baillie_pomerance_selfridge_wagstaff (T n)
{

	// ������� ��������� �� ����������� �������� - ��������, �� 29
	int div = prime_div_trivial (n, 29);
	if (div == 1)
		return true;
	if (div > 1)
		return false;

	// ���� �������-������ �� ��������� 2
	if (!miller_rabin (n, 2))
		return false;

	// ������� ���� ������-���������
	return lucas_selfridge (n, 0);

}

������ ����� ������� ��������� (�������� + exe), ���������� ������ ���������� ����� BPSW. [77 ��]


������� ����������

����� ���� ����� ����������� ��������� � ����� ���������������, ����������� �� �������� � ��������� ��������������� �������.

const int trivial_limit = 50;
int p[1000];

int gcd (int a, int b) {
	return a ? gcd (b%a, a) : b;
}

int powmod (int a, int b, int m) {
	int res = 1;
	while (b)
		if (b & 1)
			res = (res * 1ll * a) % m,  --b;
		else
			a = (a * 1ll * a) % m,  b >>= 1;
	return res;
}

bool miller_rabin (int n) {
	int b = 2;
	for (int g; (g = gcd (n, b)) != 1; ++b)
		if (n > g)
			return false;
	int p=0, q=n-1;
	while ((q & 1) == 0)
		++p,  q >>= 1;
	int rem = powmod (b, q, n);
	if (rem == 1 || rem == n-1)
		return true;
	for (int i=1; i<p; ++i) {
		rem = (rem * 1ll * rem) % n;
		if (rem == n-1)  return true;
	}
	return false;
}

int jacobi (int a, int b)
{
	if (a == 0)  return 0;
	if (a == 1)  return 1;
	if (a < 0)
		if ((b & 2) == 0)
			return jacobi (-a, b);
		else
			return - jacobi (-a, b);
	int a1=a,  e=0;
	while ((a1 & 1) == 0)
		a1 >>= 1,  ++e;
	int s;
	if ((e & 1) == 0 || (b & 7) == 1 || (b & 7) == 7)
		s = 1;
	else
		s = -1;
	if ((b & 3) == 3 && (a1 & 3) == 3)
		s = -s;
	if (a1 == 1)
		return s;
	return s * jacobi (b % a1, a1);
}

bool bpsw (int n) {
	if ((int)sqrt(n+0.0) * (int)sqrt(n+0.0) == n)  return false;
	int dd=5;
	for (;;) {
		int g = gcd (n, abs(dd));
		if (1<g && g<n)  return false;
		if (jacobi (dd, n) == -1)  break;
		dd = dd<0 ? -dd+2 : -dd-2;
	}
	int p=1,  q=(p*p-dd)/4;
	int d=n+1,  s=0;
	while ((d & 1) == 0)
		++s,  d>>=1;
	long long u=1, v=p, u2m=1, v2m=p, qm=q, qm2=q*2, qkd=q;
	for (int mask=2; mask<=d; mask<<=1) {
		u2m = (u2m * v2m) % n;
		v2m = (v2m * v2m) % n;
		while (v2m < qm2)   v2m += n;
		v2m -= qm2;
		qm = (qm * qm) % n;
		qm2 = qm * 2;
		if (d & mask) {
			long long t1 = (u2m * v) % n,  t2 = (v2m * u) % n,
				t3 = (v2m * v) % n,  t4 = (((u2m * u) % n) * dd) % n;
			u = t1 + t2;
			if (u & 1)  u += n;
			u = (u >> 1) % n;
			v = t3 + t4;
			if (v & 1)  v += n;
			v = (v >> 1) % n;
			qkd = (qkd * qm) % n;
		}
	}
	if (u==0 || v==0)  return true;
	long long qkd2 = qkd*2;
	for (int r=1; r<s; ++r) {
		v = (v * v) % n - qkd2;
		if (v < 0)  v += n;
		if (v < 0)  v += n;
		if (v >= n)  v -= n;
		if (v >= n)  v -= n;
		if (v == 0)  return true;
		if (r < s-1) {
			qkd = (qkd * 1ll * qkd) % n;
			qkd2 = qkd * 2;
		}
	}
	return false;
}

bool prime (int n) { // ��� ������� ����� �������� ��� �������� �� ��������
	for (int i=0; i<trivial_limit && p[i]<n; ++i)
		if (n % p[i] == 0)
			return false;
	if (p[trivial_limit-1]*p[trivial_limit-1] >= n)
		return true;
	if (!miller_rabin (n))
		return false;
	return bpsw (n);
}

void prime_init() { // ������� �� ������� ������ prime() !
	for (int i=2, j=0; j<trivial_limit; ++i) {
		bool pr = true;
		for (int k=2; k*k<=i; ++k)
			if (i % k == 0)
				pr = false;
		if (pr)
			p[j++] = i;
	}
}

������������� ��������������-������������ ���������

�������� � 1984 ���� ��������� ��������� ������������� ��������������.

�����������: ���������� BPSW-������������� �� 1 �� X ������ X1-a ��� ������ a > 0.

��������������.

����� k > 4 - ������������, �� ������������� �����. ����� T - ��������� ������� �����.

����� Pk(T) - ��������� ����� ������� p � ��������� [T; Tk], ��� �������:

(1) p = 3 (mod 8), J(5,p) = -1

(2) ����� (p-1)/2 �� �������� ������ ���������

(3) ����� (p-1)/2 ���������� ������������� �� ������� q < T

(4) ����� (p-1)/2 ���������� ������������� �� ����� ������� q, ��� q = 1 (mod 4)

(5) ����� (p+1)/4 �� �������� ������ ���������

(6) ����� (p+1)/4 ���������� ������������� �� ������� d < T

(7) ����� (p+1)/4 ���������� ������������� �� ����� ������� d, ��� q = 3 (mod 4)

�������, ��� �������������� 1/8 ���� ������� � ������� [T; Tk] ������������� ������� (1). ����� ����� ��������, ��� ������� (2) � (5) ��������� ��������� ����� �����. ������������, ������� (3) � (6) ����� ��������� ��� �������� ��������� ����� ����� �� ������� (T; Tk). �������, ������� (4) �������� ������������ (c (log T)-1/2), ��� �� ��� � ������� (7). ����� �������, �������� ��������� Pk(T) ������������� ����� ��� T -> oo

��� c - ��������� ������������� ���������, ��������� �� ������ k.

������ �� ����� ��������� ����� n, �� ���������� ������ ���������, ������������ �� l ������� �� Pk(T), ��� l ������� � ������ T2 / log(Tk). ���������� �������� ������� ����� ����� n ���� ��������

��� �������� T � �������������� k. ����� ����, ������ ����� ����� n ������ eT2.

��������� ����� Q1 ������������ ������� q < T, ��� ������� q = 1 (mod 4), � ����� Q3 - ������������ ������� q < T, ��� ������� q = 3 (mod 4). ����� gcd (Q1, Q3) = 1 � Q1 Q3 ? eT. ����� �������, ���������� �������� ������� n � ��������������� ���������

n = 1 (mod Q1), n = -1 (mod Q3)

������ ����, ������������, ��� �������

eT 2 (1 - 3 / k) / e 2T > eT 2 (1 - 4 / k)

��� �������� T.

�� ������ ����� n - ��� ����������� � ����� BPSW. �������������, n ����� ������ ��������� (�.�. ������, �� ������� ���� �������-������ ����� ��������� ��� ����� ���������), ������� ��� ������������� ����� ������������� �� ��������� 2. ��������� n = 3 (mod 8) � ������ p | n ����� 3 (mod 8), ��������, ��� n ����� ����� ������� ������������� �� ��������� 2. ��������� J(5,n) = -1, �� ������ ������� p | n ������������� J(5,p) = -1, � ��� ��� p+1 | n+1 ��� ������ �������� p | n, ������ �������, ��� n - ������������� ������ ��� ������ ����� ������ � �������������� 5.

����� �������, �� ��������, ��� ��� ������ �������������� k � ���� ������� T, ����� ��� ������� eT 2 (1 - 4 / k) ������������� � ����� BPSW ����� �����, ������� eT 2. ������, ���� �� ������� x = eT 2, ����� ��� ������� x1 - 4 / k �������������, ������� x. ��������� k - ��������� �����, �� ���� �������������� ��������, ��� ���������� �������������, ������� x, ���� �����, ������� x1-a ��� ������ a > 0.


������������ ��������� ����� BPSW

� ���� ������� ����� ����������� ����������, ���������� ���� � ���������� ������������ ���� ���������� ����� BPSW. ��� ��������� ����������� �� ���������� ���� - 64-������ ����� long long. ������� ���������� �� �������������.

������������ ����������� �� ���������� � ����������� Celeron 1.3 GHz.

��� ������� ���� � ������������� (10 -6 ���).

������� ����� ������ �� ������� ����� � ����������� �� ������� ������������ ��������

������� � ���� ��������, ������������ ������� prime_div_trivial(), ������� � ���� ���� ����� 29.

������� �������� ��������� (�������� � exe-����). [83 ��]

���� ��������� ���� �� ���� �������� ������ �� �������, �� ���������� ���������� ������:

������
�������
�����
�������
������ >
�������� >
0102103104105
11058.14.50.70.70.9
106106+10512.86.87.01.61.6
109109+10528.412.612.117.017.1
10121012+10541.516.515.319.454.4
10151015+10566.724.421.124.858.9

���� ��������� ���� ������ �� ������� ������ �� �������, �� �������� ������ ������:

������
�������
�����
�������
������ >
�������� >
0102103104105
110542.940.83.14.24.2
106106+10575.076.488.813.915.2
109109+105186.5188.5201.0294.3283.9
10121012+105288.3288.3302.2387.91069.5
10151015+105485.6489.1496.3585.41267.4

����� �������, ���������� �������� ������ ������������ �������� ������ 100 ��� 1000.

��� ���� ��������� ������ � ������ ������ 1000.

������� ����� ������ �� ������� �����

������, ����� �� ������� ������ ������������ ��������, ����� ����� ����� �������������� �������� ������ �� ��������� ��������.

������� �������� ��������� (�������� � exe-����). [83 ��]

������
�������
�����
�������
����� ������
�� �������� ������
����� ������
�� ������� ������
11051.24.2
106106+10513.888.8
107107+10516.8115.5
108108+10521.2164.8
109109+10524.0201.0
10101010+10525.2225.5
10111011+10528.4266.5
10121012+10530.4302.2
10131013+10533.0352.2
10141014+10537.5424.3
10151015+10542.3499.8
10161015+10546.5553.6
10171015+10548.9621.1

���, � ���� �������, ��������������� ����� ������ ����� BPSW �� ����� �����:

�� ���� �� ��������, ��� �� ��������, �� ��������� ������ (�� 1017), �������� �������� �� O (log N). ��� ����������� ���, ��� ��� ����������� ���� int64 �������� ������� ����������� �� O(1), �.�. ��������� ������� �� ��������� �� ���������� ����� � �����.

���� �� ��������� ���� BPSW � ������� ����������, �� ���������, ��� �� ����� �������� ��� ��� �� O (log3(N)). [ TODO ]


����������. ��� ���������

������� ��� ��������� �� ������ ������. [242 ��]


����������

�������������� ���� ����������, ��������� ��������� � ���������:

  1. Robert Baillie; Samuel S. Wagstaff
    Lucas pseudoprimes
    Math. Comp. 35 (1980) 1391-1417
    mpqs.free.fr/LucasPseudoprimes.pdf
     
  2. Daniel J. Bernstein
    Distinguishing prime numbers from composite numbers: the state of the art in 2004
    Math. Comp. (2004)
    cr.yp.to/primetests/prime2004-20041223.pdf
     
  3. Richard P. Brent
    Primality Testing and Integer Factorisation
    The Role of Mathematics in Science (1990)
    wwwmaths.anu.edu.au/~brent/pd/rpb120.pdf
     
  4. H. Cohen; H. W. Lenstra
    Primality Testing and Jacobi Sums
    Amsterdam (1984)
    www.openaccess.leidenuniv.nl/bitstream/1887/2136/1/346_065.pdf
     
  5. Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest
    Introduction to Algorithms
    [ ��� ������ ]
    The MIT Press (2001)
     
  6. M. Martin
    PRIMO - Primality Proving
    www.ellipsa.net
     
  7. F. Morain
    Elliptic curves and primality proving
    Math. Comp. 61(203) (1993)
    citeseer.ist.psu.edu/rd/43190198%2C72628%2C1%2C0.25%2CDownload/ftp%3AqSqqSqftp.inria.frqSqINRIAqSqpublicationqSqpubli-ps-gzqSqRRqSqRR-1256.ps.gz
     
  8. Carl Pomerance
    Are there counter-examples to the Baillie-PSW primality test?
    Math. Comp. (1984)
    www.pseudoprime.com/dopo.pdf
     
  9. Eric W. Weisstein
    Baillie-PSW primality test
    MathWorld (2005)
    mathworld.wolfram.com/Baillie-PSWPrimalityTest.html
     
  10. Eric W. Weisstein
    Strong Lucas pseudoprime
    MathWorld (2005)
    mathworld.wolfram.com/StrongLucasPseudoprime.html
     
  11. Paulo Ribenboim
    The Book of Prime Number Records
    Springer-Verlag (1989)
    [ ��� ������ ]
     

������ ������ ������������� ����, ������� ��� �� ������� ����� � ���������:

  1. Zhaiyu Mo; James P. Jones
    A new primality test using Lucas sequences
    Preprint (1997)
     
  2. Hans Riesel
    Prime numbers and computer methods for factorization
    Boston: Birkhauser (1994)