Проверка чисел на простоту. Метод Фробениуса.

Наименьший квадратичный невычет. Индекс Фробениуса

Символы Якоби и Лежандра

Определение. Для простого p и целого a определим символ Лежандра следующим образом:

Квадратичный закон взаимности. Пусть p,q - нечётные числа. Тогда

Частные случаи.

Нам потребуется похожее, но чуть другое понятие, "наименьший по абсолютной величине квадратичный невычет".

Определение. Пусть n – нечетное натуральное число, не являющееся полным квадратом. Его индексом Фробениуса Ind_F(n) будем называть наименьшее среди чисел [–1,2,3,4,5,6,...] такое, что символ Якоби jacobi(c/n) =–1.

Замечание 1. Из мультипликативности символа Якоби следует, что если индекс Фробениуса Ind_F(n) положителен, то он прост.

Замечание 2. Если jacobi(-1/n) =+1, то jacobi(-c/n) = jacobi(c/n) для всех c.

Нетрудно выяснить, когда индекс Фробениуса принимает маленькие значения:

• Если n ≡ 3 mod 4, то Ind_F(n)=-1.
• Если n ≡ 5 mod 8, то Ind_F(n)= 2.
• Если n ≡ 17 mod 24, то Ind_F(n)= 3.
• Если n ≡ 1 mod 24, то Ind_F(n) ≥ 5.

jacobi(c/n) = jacobi(n/c)

Таким образом, индекс Фробениуса для большинтва чисел невелик, -1,2,3,5. Однако, для некоторых чисел он может оказаться довольно большим:

Для чисел, меньших 2⁶⁴ наибольший индекс Фробениуса имеют числа

13 371 308 337 168 834 529 = 15671 * 42 509 111 * 20 072 209, и

10 198 100 582 046 287 689 = 277 * 1091 * 1151 * 29 318 344 777,

Их индекс Фробениуса равен 277.

Приведем полный список чисел, меньших 2⁶⁴ с индексом Фробениуса ≥ 241:

Количество чисел, меньших 2⁶⁴ с данным индексом Фробениуса таково

Всего среди чисел, меньших 2⁶⁴ индекс Фробениуса больший 128 имеют 458 069 912 чисел. Это количество велико, однако все эти числа вполне можно перебрать на современных (2015) компьютерах за приемлемое время.

Как же найти все такие числа? Очевидно, полный перебор слишком велик, даже если рассматривать только числа сравнимые с 1 по модулю 24.

Сформулируем ещё раз задачу.

Требуется найти все нечётные натуральные числа n < 2⁶⁴ не являющиеся полными квадратами такие, что символы Якоби

jacobi(-1/n)= jacobi(2/n)= jacobi(3/n)= ... = jacobi(127/n)=+1.

Числа, для которых

jacobi(-1/n)= jacobi(2/n)= jacobi(3/n)= +1

это в точности числа, сравнимые с 1 по модулю 24. Таким образом, надо найти числа n ≡ 1 mod 24, меньшие 2⁶⁴ такие, что

jacobi(5/n)= jacobi(7/n)= jacobi(11/n)= ... = jacobi(127/n)=+1.

Обозначим через

N=5 · 7 · ... · 47 = 102481630431415235

произведение 15-ти простых чисел, при этом 2⁶⁴ ≈ 7.5 · 24 · N.

Для каждого простого p=5,7,..., 47 обозначим через X_p множество вычетов t по модулю p таких, что

jacobi( 1 + 24 · N/p · t   /p ) =1,

Множество X_p состоит из (p-1)/2 элементов. Выберем из каждого X_p по одному элементу x_p. Тогда для числа

n = 1 + 24(N/5) x₅ + ... + 24(N/47) x₄₇

будет выполнено

jacobi(5/n)= jacobi(7/n)= ... = jacobi(47/n)=+1.

(5-1)/2 * ... *(47-1)/2 = 5 205 549 888 000.

Для каждого такого n рассматриваем все числа

n, n+24N, n+2 · 24N, ...

меньшие 2⁶⁴, их будет либо 7, либо 8 в зависимости от n. Для каждого такого числа надо проверить символы Якоби

jacobi(53/n), ..., jacobi(127/n)

и если все они равны 1 и n не является полным квадратом, то выводим такое число в выходной файл.

Отметим, что все n сравнимы с 1 по модулю 4, поэтому

jacobi(p/n) = jacobi(n/p) ,

поэтому вычисление символов Якоби можно свести к обращению к таблице, и выполнить достаточно быстро.

Результатом работы является текстовый файл, из 458 069 912 строк, в каждой лежит по одному числу, удовлетворяющему условиям

jacobi(-1/n)= jacobi(2/n)= jacobi(3/n)= ... = jacobi(127/n)=+1.

и не являющиеся полным квадратом.

Далее: Проверка чисел на простоту. Метод Фробениуса.