|
Пусть n – нечетное натуральное число, не являющееся полным квадратом. Обозначим через c наименьшее среди чисел [-1,2,3,5,7,11,...] такое, что символ Якоби jacobi(c/n) =-1. Если c ≤ 2, то положим z=2+sqrt(c), иначе z=1+sqrt(c). Назовем число n простым по Фробениусу, если Неизвестно ни одного числа, на котором метод ошибается. Доказано, что ошибок нет при n < 260. Фактически, метод объединяет методы Ферма и Lucas-Lemer'a. |
a + b sqrt(c) → (a + b · g, a - b · g )
где g2 = c mod p.
Теорема. Пусть n псевдопросто по Фробениусу, z = a + b sqrt(c) и p - Ф-положительный простой делитель n, n=p·q, c ≡ d 2 mod p. Введем обозначения (два элемента из Zp):
z1 = a+b·d mod p,
z2 = a-b·d mod p.
Тогда
z1q = z2 mod p,
z2q = z1 mod p,
Доказательство. По определению имеем:
(a + b sqrt(c))pq = a - b sqrt(c) mod p
В случае, когда jacobi(c/n) = +1 имеем:z p = z,
а значит(a + b sqrt(c)) q = a - b sqrt(c) mod p
Применяя изоморфизм Rp = Zp[sqrt(c] → Zp × Zp , описанный выше, получаем требуемое.Программа /W/C/Eratosfen3/ExeReady/f_positiv.exe для данного c находит все возможные Ф-положительные множители (до некоторого предела), то есть простые числа p, удовлетворяющие условию теоремы.
Выполнимость условий теоремы зависит только от значения q mod p-1, то есть если условия выполняются для некоторых (p,q), то они будут выполняться для всех пар вида (p,q + α(p-1)).
Перемножив равенства
z1q = z2 mod p,
z2q = z1 mod p,
получим: N q = N mod p, где N = N(z) = a*a-b*b*c. Другими словами, N q-1 = 1 mod p.
Порядок элемента N mod p является делителем p-1, пусть
ord(N, p) = (p-1)/s.
Тогда q = 1 mod ord(N, p), то есть q mod (p-1) - одно из чисел
1 + ord(N, p), 1 + 2*ord(N, p), ..., 1 + (s-1)*ord(N, p).
Алгоритм проверки:
Полученные результаты.
c=-1, z=2+i.
При c=-1, z=2+i и p < 7.637 · 109
получаем следующие пары (p,q):
( 2276629, 1665203)
( 30906409, 20254651)
( 806361541, 175883959)
( 806361541, 444671139)
( 806361541, 713458319)
c=2, z=2+ sqrt(2).
При c=2, z=2+ sqrt(2) и p < 5.235 · 109 получаем следующие пары (p,q): ( 8191, 5669) и при p=2147483647=232-1 всего 63 пары c q равным
28589131, 62676173, 96763215, 130850257, 164937299, 199024341, 233111383, 267198425, 301285467
335372509, 369459551, 403546593, 437633635, 471720677, 505807719, 539894761, 573981803, 608068845
642155887, 676242929, 710329971, 744417013, 778504055, 812591097, 846678139, 880765181, 914852223
948939265, 983026307, 1017113349, 1051200391, 1085287433, 1119374475, 1153461517, 1187548559, 1221635601
1255722643, 1289809685, 1323896727, 1357983769, 1392070811, 1426157853, 1460244895, 1494331937, 1528418979
1562506021, 1596593063, 1630680105, 1664767147, 1698854189, 1732941231, 1767028273, 1801115315, 1835202357
1869289399, 1903376441, 1937463483, 1971550525, 2005637567, 2039724609, 2073811651, 2107898693, 2141985735
c=3, z=1+ sqrt(3).
При c=3, z=1+ sqrt(3) не существует Ф-положительных простых множителей, меньших 4.539 · 109.
c=5, z=1+ sqrt(5).
При c=5, z=1+ sqrt(5) и p < 4.804 · 109 подходящие q имеются лишь при
p = 61681, 363101449, 4278255361, 4562284561, 4582537681
однако во всех этих случаях p mod 24 = 1, но для всех найденных q mod 24 ≠ 1, поэтому
n mod 24 = p(q+α · (p -1)) mod 24 ≠ 1.
Таким образом у псевдопростых по Фробениусу чисел при индексе Фробениуса c=5 не существует Ф-положительных простых множителей, меньших 4.804 · 109.c=7, z=1+ sqrt(7).
При c=7, z=1+ sqrt(7) и p < 3.713 · 109 получаем следующие пары (p,q): ( 31, 19) и ( 3923, 741). Из первой пары получаем кандидаты в FPP вида
n = 31 · (79+120 · u),
где u ≡ 0 или 2 или 6 mod 7.
Из второй пары - числа вида
n = 3923 · (43883+47064 · u).
c=11, z=1+ sqrt(11).
При c=11, z=1+ sqrt(11) и p < 4.093 · 109 получаем следующие шесть пар (p,q):
( 98641, 1369), ( 98641, 21097), ( 98641, 40825), ( 98641, 60553), ( 98641, 80281),
( 3760411, 1444181),
Рассмотрим подробнее. Пусть p=98641, q=1369. Тогда p mod 24 = q mod 24 = 1, поэтому n=p(q+α · (p -1)) mod 24 = 1 - все в порядке.
p mod 5 = 1, q mod 5 = 4, поэтому n mod 5 = 4 - все в порядке.
p mod 7 = 4, q mod 7 = 4, - все в порядке.
p mod 11 = 4, q mod 11 = 5 - все в порядке.
Далее, пусть p=98641, q=21097. Тогда p mod 24 = q mod 24 = 1, поэтому n=p(q+α · (p -1)) mod 24 = 1 - все в порядке.
p mod 5 = 1, q mod 5 = 2, поэтому n mod 5 = 2 - квадратичный не вычет, противоречие.
Пусть p=98641, q=40825. Тогда p mod 24 = q mod 24 = 1, поэтому n=p(q+α · (p -1)) mod 24 = 1 - все в порядке.
p mod 5 = 1, q mod 5 = 0, противоречие.
Пусть p=98641, q=60553. Тогда p mod 24 = q mod 24 = 1, поэтому n=p(q+α · (p -1)) mod 24 = 1 - все в порядке.
p mod 5 = 1, q mod 5 = 3, поэтому n mod 5 = 2 - квадратичный не вычет, противоречие.
Пусть p=98641, q=80281. Тогда p mod 24 = q mod 24 = 1, поэтому n=p(q+α · (p -1)) mod 24 = 1 - все в порядке.
p mod 5 = 1, q mod 5 = 1, все в порядке.
p mod 7 = 4, q mod 7 = 5, все в порядке.
p mod 11 = 4, q mod 11 = 3, все в порядке.
Пусть p=3760411, q=1444181. Тогда p mod 24 = 19, q mod 24 = 5, поэтому
n=p(q+α · (p -1)) mod 24 = 23 + 6 α mod 24
что никогда не может равняться 1 mod 24.Таким образом, при c=11 и p < 4.093 · 109 подходящих пар (p,q) для FPP всего две:
( 98641, 1369) и ( 98641, 80281).