MAXimal | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
���������: 10 Jun 2008 18:18 ���������� [������] ���� 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 ���� �������-������� �� ���� ��������� �������� �� ����� �������-������, ��������� �� ����������� �� ������ ����������, � ��� ����� � �� ������� ����� (��������. ��. [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 ��] ���� ��������� ���� �� ���� �������� ������ �� �������, �� ���������� ���������� ������:
���� ��������� ���� ������ �� ������� ������ �� �������, �� �������� ������ ������:
����� �������, ���������� �������� ������ ������������ �������� ������ 100 ��� 1000. ��� ���� ��������� ������ � ������ ������ 1000. ������� ����� ������ �� ������� �����������, ����� �� ������� ������ ������������ ��������, ����� ����� ����� �������������� �������� ������ �� ��������� ��������. ������� �������� ��������� (�������� � exe-����). [83 ��]
���, � ���� �������, ��������������� ����� ������ ����� BPSW �� ����� �����:
�� ���� �� ��������, ��� �� ��������, �� ��������� ������ (�� 1017), �������� �������� �� O (log N). ��� ����������� ���, ��� ��� ����������� ���� int64 �������� ������� ����������� �� O(1), �.�. ��������� ������� �� ��������� �� ���������� ����� � �����. ���� �� ��������� ���� BPSW � ������� ����������, �� ���������, ��� �� ����� �������� ��� ��� �� O (log3(N)). [ TODO ] ����������. ��� ���������������� ��� ��������� �� ������ ������. [242 ��] ������������������������ ���� ����������, ��������� ��������� � ���������:
������ ������ ������������� ����, ������� ��� �� ������� ����� � ���������:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||