(а2. п=1?

A3. Разделить

А5. Множитель найден

А4. Остаток равен нулю?

<Л Нет (А6. Частное\ у \ мало? J

Рис. 11. Простой алгоритм разложения на множители.

Алгоритм А {Разложение на простые множители путем деления). По данному положительному целому числу N этот алгоритм (рис. 11) находит простые множители pi < р2 < • • • < Р( числа N в соответствии с равенством (1). В этом методе используется вспомогательная последовательность пробных делителей

2 = rfo < di < Й2 < < • • •, (2)

которая включает в себя все простые числа < у/N (и, если это удобно, может содержать числа, не являющиеся простыми). Последовательность чисел di должна также содержать по крайней мере одно значение, такое, что dk >

Al. [Начальная установка.] Присвоить t <г- Q, к +- Q, п N. (В ходе выполнения алгоритма переменные t, к, п подчинены следующим условиям: "п = N/pi. ..pt и п не имеет простых множителей, меньших d".)

А2. [п = 1?] Если п = 1, алгоритм заканчивается.

A3. [Разделить.] Присвоить q [n/dJ, г n mod dk- (Здесь q и г - соответственно частное и остаток от деления числа п на d.)

А4. [Остаток равен нулю?] Если г О, то перейти к шагу А6.

А5. [Множитель найден.] Увеличить t на 1 и присвоить pi +- dk, п +- q. Возвратиться к шагу А2.

А6. [Частное мало?] Если q > dk, увеличить Jt на 1 и возвратиться к шагу A3.

А7. [п - простое число.] Увеличить t на 1, присвоить р п и завершить выполнение алгоритма.

В качестве примера алгоритма А рассмотрим разложение на простые множители числа N = 25852. Сразу же находим, что N = 2 12 926; следовательно, pi = 2. Далее, 12 926 = 2-6 463, так что р2 = 2. Но теперь число п = 6 463 не делится на числа 2, 3, 5, ..., 19; находим, что п = 23 • 281; значит, рз = 23. В итоге имеем 281 = 12 • 23 -Ь 5 и 12 < 23, т. е. р4 = 281. В рассмотренном примере для определения простых множителей числа 25852 нужно было выполнить 12 операций деления. С другой стороны, при разложении на простые множители чуть меньшего числа 25 849 (которое оказывается простым) пришлось бы затратить не менее 38 операций

деления. Это показывает, что время выполнения алгоритма А приблизительно пропорционально ma.x{pt-i,\/pt)- (При t = 1 эта формула справедлива, если положить, что ро = 1.)

Последовательность do, di, с?2, • • пробных делителей, используемая в алгоритме А, можно просто считать последовательностью чисел 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, ..., члены которой, кроме первых трех, получаются посредством попеременного увеличения предыдущих на 2 и 4. Данная последовательность содержит все числа, не являющиеся кратными 2 или 3; при этом она содержит и такие числа, как 25, 35, 49 и т. д., не являющиеся простыми. Тем не менее алгоритм будет давать правильный результат. Если из этой последовательности убрать числа ЗОтп ± 5 при тп > 1, исключая тем самым как ложные простые все числа, кратные пяти, то можно сэкономить до 20% времени выполнения алгоритма. Исключив из рассмотрения числа, кратные 7, можно сократить список еще на 14% и т. д. Для управления выбором пробных делителей можно воспользоваться какой-нибудь компактной таблицей.

Если известно, что N мало, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если N меньше миллиона, то нужно включить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить значение di68 = 1000 как заключительного члена для случая, когда число N окажется простым, большим 997). Такую таблицу можно получить при помощи короткой вспомогательной программы (см., например, алгоритм 1.3.2Р или упр. 8).

Сколько пробных делителей необходимо для алгоритма А? Пусть я(а;) -количество простых чисел < х, так что я(2) = 1, я(10) = 4. Асимптотическое поведение этой функции интенсивно изучалось многими величайшими математиками, начиная с Лежандра (Legendre), который исследовал эту проблему в 1798 году. Кульминацией многочисленных достижений в решении этой проблемы в течение 19 века явилось доказательство в 1899 году Шарлем де Ла Балле Пуссеном (Charles de La Vallee Poussin) того факта, что для некоторого А > О

я(а;) = Г + 0{хе-/). J2 ш t

[Мёт. Couronnes Acad. Roy. Belgique 59 (1899), 1-74; см. также J. Hadamard, Bull. Soc. Math. France 24 (1896), 199-220.] Интегрирование no частям дает

. . x X 2\x rlx / X \

~ h (ii (h"" (lna;)+i \{logxy+y

для всех фиксированных г > 0. В дальнейшем остаточный член в формуле (3) последовательно уточнялся. Например, его можно заменить следующим выражением: 0(a;exp(-A(loga;)/V(logloga;)/)). [См. А. Walfisz, WeyPsche Exponentialsummen in der neueren Zahlentheorie (Berlin, 1963), Chapter 5.] В 1859 году Бернард Риман (Bernhard Riemann) предположил, что

ф) L() +0(1) = Цх) - 1Ц) - iL() + .. . + 0(1), (5)

где L{x) = dt/lnt. Эта формула хорошо согласуется с выполненными расчетами при выборе X в подходящем диапазоне.

(См. упр. 41.) Однако проблема распределения простых чисел не так проста, и в 1914 году Дж. Э. Литтлвуд (J. Е. Littlewood) показал, что существует такая положительная константа С, что неравенство

тт{х) > L{x) + Ci/xlogloglogi/loga;

справедливо для бесконечно многих значений х, чем опроверг предположение Римана (5). (См. Hardy, Littlewood, Acta Mati. 41 (1918), 119-196.) Результат Лит-тлвуда показал, что в простых числах заложено что-то мистическое и что для действительного понимания законов их распределения необходимо разработать глубокую математическую теорию. Риман высказал намного более конструктивное предположение, известное как "гипотеза Римана", согласно которому комплексная функция С(г) равна нулю только тогда, когда ее действительная часть равна 1/2, за исключением тривиальных случаев, когда z есть отрицательное целое число. Если эта гипотеза верна, то из нее следует я(а;) = L{x) -Ь 0(i/xloga;); см. упр. 25. Ричард Брент (Richard Brent) выполнил численную проверку гипотезы Римана для всех "малых" значений z, использовав метод Д. Г. Лемера (D. Н. Lehmer) и показав, что функция C,{z), мнимая часть которой принадлежит интервалу О < 9г < 32585736.4, имеет точно 75 ООО ООО нулей; для всех этих нулей Ш = \-а C(z) ф 0. [Math. Сотр. 33 (1979), 1361-1372.]

Для анализа поведения алгоритма А в среднем необходимо выяснить, насколько большим может оказаться наибольший простой множитель pt- Этот вопрос был впервые исследован Карлом Дикманом (Karl Dickman) [Arkiv for Mat., Astron. och Fys. 22A, 10 (1930), 1-14], который проанализировал вероятность того, что случайное целое число, принимающее значения между 1 и х, будет иметь наибольший простой множитель < а;". Дикман показал, что эта вероятность при а; -> оо стремится к предельному значению F{a), где F может быть вычислено в результате решения функционального уравнения

F{a) = [ f(--) - при О < а < 1; F{a) = 1 при а > 1. (6) Jo \1 - t / t

Ход его рассуждений был примерно следующим. Для заданного О < t < 1 количество целых чисел, меньших х, наибольшие простые множители которых расположены между а;* и а;****, равно xF{t)dt. Количество простых чисел р в этом интервале равно г{x*) - я(а;*) = я(а;* -Ь (In а;)а;* dt) - я(а;*) = а;* dt/t. Для каждого такого р количество целых чисел п, таких, что "пр < а; и наибольший простой множитель числа п не превышает р", равно количеству чисел, для которых п < х~*