AOP_Tom2 (1021737), страница 115
Текст из файла (страница 115)
А5. [Множитель найден.» Увеличить 1 на 1 и присвоить р~ с — 4, и +- у. Возвратиться к шагу А2. А6. [Частное мало?) Если д > с1ы увеличить й на 1 и возвратиться к шагу А3. А7. [и — простое число.) Увеличить 1 ва 1, присвоить р, +- п и завершить выполнение алгоритма. $ В качестве примера алгоритма А рассмотрим разложение на простые множители числа Х = 25852. Сразу же находим, что?У = 2. 12926; следовательно, р~ — — 2. Далее, 12926 = 2 6463, так что рз = 2. Но теперь число и = 6463 не делится на числа 2, 3, 5,, 19; находим, что и = 23 281; значит, рз = 23.
В итоге имеем 281 = 12 23+ 5 и 12 < 23, т. е. рх = 281. В рассмотренном примере для определения простых множителей числа 25852 нужно было выполнить 12 операций деления. С другой стороны, при разложении на простые множители чуть меныпего числа 25 849 (которое оказывается простым) пришлось бы затратить не менее 38 операций Я(х) = г! — + 0(хе ч '"~*). Г* д! г (3) (Мет, Соигоппез Асад. Воу. Ве!8!с1ие 59 (1899), 1-74; см. также 3. Надашагд, Вп!1. Яос. МаСЬ. Ргапсе 24 (1896), 199 — 220.) Интегрирование по частям дает х х 2!х г!х ( х л(х)= — + — + ' + . + ' +О(, (4) !п х (!п х)г (!п х)з (!п х) с+' ~, (!о8 х) "+г / для всех фиксированных г > О.
В дальнейшем остаточный член в формуле (3) последовательно уточнялся. Например, его можно заменить следующим выражением: 0(х ехр( —.4(!ой х)гс "/(!о8 !ой х) ссэ)) . [См. А. %а!6эх, Исеу!эсЬе Ехропепг!а!эипипеп т с!ег пепегеп Ъй!епсЬеог!е (Вегйп, 1963), СЬарсег 5.) В 1859 году Бернард Риман (ВегпЬагс! Рдегпапп) предположил, что х(х) =~ — 7.Ях)+0(1) = Цх) — -Цтсх) — -Ц0х)+. +0(1), (5) "' р(й) !с 2 3 деления. Это показывает, что время выполнения алгоритма А приблизительно пропорционально псах(р, ы ~/рс ).
(При 1 = 1 зта формула справедлива, если положить, что рп = 1.) Последовательность дп, д,, дг, ... пробных делителей, используемая в алгоритме А, можно просто считать последовательностью чисел 2, 3, 5, 7, 11, 13, 1?, 19, 23, 25, 29, 31, 35, ..., члены которой, кроме первых трех, получаются посредством попеременного увеличения предыдущих на 2 и 4. Данная последовательность содержит все числа, не являющиеся кратными 2 или 3; при этом она содержит и такие числа, как 25, 35, 49 и т. д., не являющиеся простыми. Тем не менее алгоритм будет давать правильный результат. Если из этой последовательности убрать числа 30пг х 5 при пг > 1, исключая тем самылс как ложные простые все числа, кратные пяти, то можно сэкономить до 20% врелсени выполнения алгоритма.
Исключив из рассмотрения числа, кратные 7, можно сократить список еще на 14Уа и т. д. Для управления выбором пробных делителей можно воспользоваться какой-нибудь компактной таблицей. Если известно, что Ас мвлб, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если Ж меныпе миллиона, то нужно включить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить значение дшв = 1000 как заключительного члена для случая, когда число Х окажется простым, большим 997г). Такую таблицу можно получить прн помощи короткой вспомогательной программы (см., например, алгоритм 1.3.2Р или упр. 8). Сколько пробных делителей необходимо для алгоритма А? Пусть я(х) — количество простых чисел < х, так что я(2) = 1, х(10) = 4. Асимптотическое поведение этой функции интенсивно изучалось многими величайпсими математиками, начиная с Лежандра (Ьсйепдге), который исследовал эту проблему в 1798 году.
Кульгяииацией многочисленных достижений в решении этой проблемы в течение 19 века явилось доказательство в 1899 году Шарлем де Ла Валле Пуссеном (СЬаг!еэ де Ьа Ъ'а!!ее Ропввш) того факта, что для некоторого .4 > 0 где Ь(х) = ] пг/!и Ь Эта формула хорошо согласуется с выполненными расчетами при выборе х в подходящем диапазоне. Формула Римана 168.3 78527.4 50847455.4 37607910542.2 29844570495886.9 2473995428423949 4.4 з х(х) Р33 168 10в 78498 ЬОэ 50847534 10" 37607912018 10" 29844570422669 10га 24739954287740860 Ь(.) 176.6 78626.5 50849233.9 37607950279.8 29844571475286.5 24739954309690414.0 (См.
упр. 41.) Однако проблема распределения простых чисел не так проста, и в 1914 году Дж. Э. Литтлвуд (Я. К. Ь|гс!етчоос)) показал, что существует такая положительная константа С, что неравенство я (х) > Х (х) + С ь?х !о8 1о8 !о8 х/!о8 х / ? г хпг Р(о) = / Е~ — / — при 0 < а < 1; Е(о) = 1 при о > 1. (6) 1 — ! Ход его рассуждений был примерно следующим. Для заданного 0 < ! < 1 количество целых чисел, меньших х, наибольшие простые множители которых расположены между х' и х'+"', равно хР" (!) Ф. Количество простых чисел р в этом интервале равно я(я'+"') — я(х') = я(з~+ (1п х)х' сИ) — я(х') = х' А!/Ь Для каждого такого р количество целых чисел и, таких, что '"'пр < х и наибольший простой множитель числа о не превышает р", равно количеству чисел, для которых п < х' ' справедливо для бесконечно многих значений х, чем опроверг предположение Римана (5), (См.
Набу, Ь!11!ежооо, Асса Май. 41 (1918), 119 — 196.) Результат Литтлвуда показал, что в простых числах заложено что-то мистическое и что для действительного понимания законов их распределения необходимо разработать глубокую математическую теорию. Риман высказал намного более конструктивное предположение, известное как "гипотеза Римана", согласно которому комплексная функция ь(х) равна нулю только тогда, когда ее действительная часть равна 1/2, за исключением тривиальных случаев, когда г есть отрицательное целое число.
Бели этв гипотеза верна, то из нее следует я(х) = Ь(х) + 0(х/х )о8 х); см. упр. 25. Ричард Брент (В!сйагс! Вгеп1) выполнил численную проверку гипотезы Римана для всех "малых" значений х, использовав метод Д. Г. Лемера (й. Н. Ьейшег) и показав, что функция ((х), мнимая часть которой принадлежит интервалу 0 < Зг < 32585736.4, имеет точно 75 000 000 нулей; для всех этих нулей Ях = 1 и ~'(х) ф О, [Ма!Ь. Сошр.
33 (1979), 1361 †?2.] Для анализа поведения алгоритма А в среднем необходилю выяснить, насколько большим может оказаться наибольший простой множитель р,. Этот вопрос был впервые исследован Карлом Дикманом (Каг! Вгс!анап) [Аг!г!г Гог Ма!., Аз!гол.
осй Еув. 22А, 10 (1930), 1-14], который проанализировал вероятность того, что случайное целое число, принимающее значения между 1 и х, будет иметь наибольший простой множитель < х . Дикман показал, что эта вероятность при х -+ оо стремится к предельному значению Г(о), где Е может быть вычислено в результате решения функционального уравнения и наибольший простой множитель не превышает (хг ')'Д~ '~, т. е. х г'(г/(1 — !)).
Следовательно, хГ'(1) й = (х'г(!/!)(х1 'Е(!/(1 — !))) и уравнение (6) получается посредством интегрирования последнего уравнения. Этому эвристическому доводу может быть придана строгость. В. Рамасвамн (ч'. Вашаэпаш1) [Вп!!. Атег. Маго. Яос. 66 (1949), 1122 — 1127) показал, что в случае фиксированных а прн х + оо интересующая нас вероятность асимптотнчески равна г'(а) + 0(1/1обх); анализом этой проблемы занимались и многие другие авторы (см. обзор Карла К. Нортона (Каг1 К. чогсоп), Мета!гэ Атег.
Ма!Ь. Яос. 106 (1971), 9-27!. В случае, еглн — ' < а < 1, формула (6) упрощается: Р() = — ~ Р( —,) ~ = -~ '! =1+! Таким образом, например, вероятность того, что для случайного целого числа < х существует простой множитель > ч/х, равна 1 — Еф = 1п2, что составляет около 69Уо. Во всех этих случаях выполнение алгоритма А сопряжено с определенными трудностями. Обсудим теперь вопрос о том, насколько быстро алгоритм А выдаст результат в случае, когда множитель ограничен шестиразрядным числом.
Заметим, что для больших чисел )ч', если нам не повезет, общее время выполнения процедуры разложения на множители с использованием пробных делителей очень быстро превысит практические возлшжностн алгоритма. Ниже в этом разделе будет показано, что существуют достаточно хорошие способы, позволяющие определить, является ли относительно большое и простым числом, не проверяя все пробные делители до,„/й. Поэтому алгоритм А будет выполняться быстрее, если между шагами А2 и АЗ включить проверку принадлежности числа к простым числам.
Для алгоритма, усовершенствованного таким образом, время выполнении можно в первом приближении считать пропорциональным р~ м т. е. второму по величине простому множителю числа Ат вместо шах(рг м ч/рг ). Используя аргументы, аналогичные аргументам Дикманв (см. упр. 18), можно показать, что с приближенной вероятностью С(В) второй по величине простой множитель случайного целого числа < х будет < х", где о(е=/ (о( ' )-г( ' )) ',р,о и -',. о) Очевидно, что для !7 > — ' эта функция О(!)) = 1 (см. рис. 12). Численное решение уравнений (6) и (7) дает следующие "процентные отношении значений" этих функций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
