Experimental program estimation for the quantity of prime numbers necessary for elimination of polynomial equations with.pdf В [1] для решения сравненияP(x) = 0 mod N, (1)где P(x) - многочлен с целыми коэффициентами, N - произведение неизвестныхдостаточно больших простых чисел, строятся многочлены Q i(x ) с целыми коэффициентамии целые числа j min(i) ^ j max(i),i = 1,... , т , т - параметр алгоритма, такие,что любое решение Хо сравнения (1) удовлетворяет равенствуQi(xо )= j ■ Nh (2)(где натуральное число h - параметр алгоритма) при некотором неизвестномj е {jmin(i), . . . , jmax(i)}. В связи с этим при больших числах Hi = jmin(i) - jmax(i) + 1актуальна задача: найти те j е { jmin(i),... , j max(i)}, при которых уравнение (2) неимеет целых корней, не решая уравнение (2).Один из способов такого быстрого отсева j указан в [1] и основан на примененииодной теоремы Гаусса. Рассмотрим некоторое обобщение задачи. Пусть f (x ) ,g (x ) -многочлены с целыми коэффициентами, и требуется выяснить, возможно ли равенствоf (x) = j ■ g(x) (3)при некотором целом x и некотором целом j е { jmin(i),... , j max(i)} (jmin, j max - целыечисла), не решая уравнение (3).Предложенный далее метод отсева j, при которых уравнение (3) не имеет целыхкорней, обобщает упомянутый метод из [1]. Для простого числа p определим множествоJp = {у е 0,1,... ,р - 1 : g(y ) = 0 mod p}. Пусть для p выполняется условие: | Jp| < pи если | Jp| > 0, то f (у) = 0 mod p для любого у е Jp. В этом случае, если x = vp + у,где v - целое, у е Jp, равенствоf (vp + у) = j ■ g(vp + у) (4)невозможно при любом целом j.Пусть теперь x = vp + у, у е {0,1, . . . ,p - 1}\Jp, и выполняется равенство (4). Тогдао с т ^ (y),p) = ост(j,p) ■ ост(g(y),p) mod p, где ост(m,p) е {0,1, . . . ,p - 1} - остатокот деления целого m на p. Так как у е Jp, то о с т ^ у )^ ) е {1, . . . ,p - 1}, существуетединственное число z е {1, . . . ,p - 1}, такое, чтоz ■ ост(д(у),р) = 1 mod p (5)(z - обратный элемент к элементу ост(д(у),р) в поле GF(p)).Отсюда следует, что ост(^',р) = ост(z ■ о с т (/(y),p),p). Последнее равенство служитдля отсева j , при которых уравнение (3) не имеет целых корней. Пусть сначала um = 0для m = 0 ,1 ,... ,р - 1. Для каждого у Е {0 ,1 ,... ,р - 1}\Jp найдём z из сравнения (5) изатем число m = ост(z ■ о с т (/(y),p),p); положим um = 1. В результате будет построеномножество U(p) тех m = 0 ,1 ,...,p - 1, при которых um = 0; |U(p)| = r(p), r(p) Е{|Jp |,. . . ,p - 1}.Если для заданного целого j выполняются равенстваост( j , p) = m,Um = 0, (6)то уравнение (3) не имеет целых корней. Заметим, что вместо трудоёмкого алгоритмарешения уравнения (3) здесь используются только две операции (6). Для многочленов/ (x) степени большей 1 обычно выполняется предположение: величина о с т (/(y),p)принимает значения 0 ,1 ,... ,p-1 с равными вероятностями 1/p, когда у = 0 ,1 ,... , p- 1.Естественно предположить, что величина ост^'^) принимает значения 0 ,1 ,... ,p - 1с равными вероятностями 1/p, когда j Е { jmin,. . . , j max}. При этом предположениивероятность не отсеять j с помощью операции (6) равна 1 - (r(p))/p, где r(p) - случайнаявеличина, равная числу пустых ящиков при бросании в p ящиков d(p) = p - | Jp|дробинок с вероятностью 1/p попадания дробинки в k-й ящик при k = 1 ,... ,p.Рассмотрим теперь несколько простых чисел p1, ... ,ps, удовлетворяющих условию,и будем отсеивать j с помощью s равенств вида (6), то есть отсеивать j, если (6)выполняется для одного из чисел p1,. .. ,ps (работаем до первого выполнения (6)).Будем предполагать, что случайные величины о с т ^ '^ ) ,... , о с т ^ '^ ), а также случайныевеличины ri = r(p^), i = 1 ,... , s, независимы. Тогда вероятность не отсеять jс помощью s равенств (6) равна Ps = ПS=1(1 - ri/p i). Пусть Н = j max-j min - случайноечисло случайных j . Положим di = d(pi), i = 1 ,... , s. Если многочлен g(x) фиксирован,а / (x) - случайный многочлен, то можно найти математическое ожидание и дисперсиюдля числа Н0 не отсеянных значений j . Используя формулы (7), (9) из [2] дляматематического ожидания величин ri,ri(ri - 1), найдёмDHoEHo = E (HPs)= h 2 ПH Пi=11 - ( 1 - -pi H Пi=11 - (1 - -piPii=11 + ( 1 - -pi1 - -2 | -pidi2 - -pi1 - -pidi- (EHo)2. (7)Формулы (7) дают возможность ещё до вычисления r1, ... , rs найти s, гарантирующеенебольшое число не отсеянных j (неравенство в (7) даёт эту возможность дажене зная g(x)). Был запрограммирован случай, когда g(x) = Nh, / (x) = Qi(x), p1, ... ,ps- первые простые числа. При этом |J(pi)| = 0,di = pi. Для ускорения перебора целыхj Е { jmin(i) ,... , j max(i)} использовалась китайская теорема об остатках, а именно,перебирались всеП pi + j * i=1dЗдесь j * - очередное число, имеющее при делении на p i ,... ^л остатки j i , . . . , j\ соответственно,где j t G {0 ,1 ,... ,pt - 1}\U(pt) для t = 1 ,... , A, A G {1 ,... , s} - параметралгоритма, v - целое число, v0(j*) = v0 iin 3Пг=1 Pi

Скачать электронную версию публикации