Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 95
Текст из файла (страница 95)
Тогда в некотором столбце к» матрицы Ь»» хотя бы половина элементов равна 1. Если вычеркнуть столбец х~ и все строки, элементы которых в этом столбце равны 1, то получится матрица Ь»э со свойствами, подобными свойствам матрицы ЛУ». Повторно выполнив описанную процедуру, можно сформировать матрицу 31„, которая имеет»э' — г столбцов и число строк, меньшее Х/2', и которая содержит не менее !'(»г" — 1) элементов, равных 1. ]См.
РОСЯ 19 (1978), 78.] ]Подобным образом может быть доказано существование е»!иисшеснг»оо бесконечной последовательности к» < хэ <, такой, что число и > 1 будет простым в том и толька в том случае, если его проверка выполнена алгоритмом Р посредством х для х = хм ..., х = х, где т = !'1!8п](1!бп] — 1), Существует ли последовательность, обладающая такими же свойствами, но в случае, когда т = 0(!об и)?] 26. Впервые эта теорема была строго доказана фон Мангольдтом (гоп Мапйо!Ве) (Сге!- !е 114 (1895), 25о-305], который на самом деле показал, что остаточный член 0(!) равен С+ ~' »Й/((à — 1)11пг) минус 1/2Й при условии, что число и равно Ь-й степени простого числа. Постоянная С равна В 2-(п 2 = 7+ 1п!п 2+ 2 „2 (1п 2)"/пп! = О 3520165995 57547475427356767736436568447!+, ]Итоги исследований этой задачи за 100 лет, прошедших после публикации работы фон Мангольдта, подвел А.
Л. Карацуба (А. А. Кагашпба) в книге Со»пр!ех Ала!у»бз»л »эпшЬег ТЬеогу (СКС Ргеез, 1995). В книге Эрика Баха (Епс ВасЬ) и Джеффри Шэллита (»е(1геу БЬа1йе) А)бог»гЛш»с Хпшбег ТЬеогу 1 (М1Т Ргеш, 1996), глава 8, проанализирована связь гипотезы Римана с конкретными задачами теории чисел.] 26. Если число А» не является простым, то оно содержит простой множитель д < э»»э». Согласно условиям задачи каждый простой делитель р числа / содержит целое число кю такое, что порядок числа х„по модулю 9 является делителем числа )У вЂ” 1, но не (1У вЂ” 1)/р. Поэтому, если число р" делит /, порядок числа хр по модулю 9 будет кратным р~.
В упр. 3.2.1.2-15 показано, что существует элемент х порядка / по модулю 9. Однако зто невозможно, поскольку тогда должно быть 4~ > (/+ 1) > (/+ 1) г > !г, и равенство ие может быть выполнено. (Ргос СашЬ. РЬ!!. Яос. 18 (1914), 29-30.) 27. Если число Ь не делится на 3 н если Ь < 2 + 1, то число Ь 2" + 1 будет простым тогда и только тогда, когда 3 гв -1 (по модулю )о2" + 1) (согласно упр. 26). Если же Ь 2" +1— простое число, то согласно закону взаимности квадратичных вычетов число 3 не является квадратичным вычетом по модулю Ь 2" + 1, поскольку (!г 2" + 1) шоб 12 = 5.
(Этот способ проверки был предложен без доказательства Протом (РгогЬ) в Сошргез Леев Асад. аз! Рапз 87 (1878), 926.) Чтобы применять способ проверки Прота с достаточной эффективностью, необходимо обеспечить вычисление значения х~ шос1(Й 2" + 1) с почти такой ж» скоростью, как и вычисление значения хзшоб(2" — 1). Положим, что кз = А 2 + В; тогда хз ш  — (А/Ц + 2" (А шаг)Ь), и в случае, если Ь представляется с однократной точностью, остаток вычисляется легко.
(Несколько сложнее проверить "простоту" чисел вада 3 2" + 1: для этого необходимо сначала применить случайные числа однократной точности, пока одно из них в соответствии с законом квадратичной взаимности не окажется квадратичным без остатка шог( 3 2" + 1. После этого в способе проверки, описанном выше, заменяем "3" этим числом. Если окажется, что ппкк14 74 О, можно использовать число 5. Получается, что число 3 2" + 1 будет простым, когда и = 1,2,5,6,8,12,18„30,36,41,66,189,201,209,276,353,408, 438, 534, 2208, 2816, 3 168, 3189, 3912, 20909, 34350, 42294, 42665, 44685, 48150, 55 182, 59 973., 80190, 157169, 213 321; других таких чисел вплоть до и < 300 000 нет, Число 5 2" + 1 будет простым, когда и = 1,3,7,13, 15,25,39,55,75.85,127,1947,3313,4687,5947,13165, 23473, 26607, 125413, 209 787,240937 (и < 300000). См.
К, М. ВпЬ!пзоп, Ргос. Ашег. Магб, Бес. 9 (1958), 673-681; С. У. СогшагЬ, Н. С, %'!!!!апы, Магй. Сошр. 35 (1980), 1419-1421; Н. ЭвЬпег, %. Ке!!ег, Магб. СогпР. 64 (1995), 397-405; Л, 8. Уоппб, Мазй. СошР. 67 (1998), 1735-1738.) 28. Имеем /(р,реп) = 2/(р + 1) + /(р,4)/р, поскольку 1/(р + 1) †вероятнос того, что число А кратно числу р; если Ы шоб р ф О, то /(р рЫ) = 1/(р+ 1). Твк как А~ — (4(г + 3)В не может быть кратно 4, то /(2, 45+3) = -', Так как А — (85+ 5) В~ не может быть кратко 8, то/(2,81+5) = .
/(2, ба+1) з+з+з+ е+1Ьз+' = Ф. Егли4ш л~шобр= (1, р-1), то соответственно для нечетных р получим /(р,4) = (2р/(р — 1), 0). 29. Количество неотрицательных целых решений х, неравенства х~+ . ч-к < г равно ( „+') > гп"/г!; каждое из этих решений соответствует единственному целому числу р~' р*" < и. (Более точные оценки для специального случая, когда числа р являются 7-ми простыми числами при всех у, приведены в работах Н. С, бе Вгвцп, 1пбаб, МаГЬ. 28 (1966), 240-247; Н, На(Ьегвгаш, Ргос, Ъопс(оп Масб.
Яос. (3) 21 (1970), 102-107.) ЗО. Если р"...р' шхз (по модулю 9), можно найти такие у„что р",...р' ш(жу ) (по модулю д, '); поэтому согласно китайской теореме аб остатках находим 2 значений величины Х, таких, что Хз ш р" ,...р' (по модулю/г'). Количество пар (еь...,е',„;е",,...,г" ), для которых соблюдаются указанные свойства и которым соответствуют такие последовательности (ем.,., е ), не превышает величины („"„). Теперь для каждого из 2~ двоичных Ф чисел а = (аь .. ав)з положим, что и, — количество показателей (е„..., е„,), таких, что (Р,' - р ) и р ш ( — 1)гч (по модулю 9;).
Следовательно, доказано, что требуемое количество целых чисел Х не меньше 2~Я", п~)/(," ). Поскольку т „и, — количество способов замены путем перестановок не более г/2 объектов из множества т объектов, т. е. ( „+"~~ ), получаем 2, и„> ( "~ ) /2 > т" /(2 (г/2)! ).
(Дополнительные сведения, касающиеся тонкостей применения теоремы Э, приведены Шнорром в Х А!6ог!С)тшз 3 (1982), 101-127.] 31. Чтобы показать, что Рг(Х < 2рл) < е Рзр прксвоим и = М, рМ = 4т и УМ = 2т. 32. пусть м = (т/бтрб] и пусть все х, каждого из сообщений ограничены кнтервалом 0 < х < М вЂ” Мз. Если х > М, кодируем его в виде хз шоб)!р', как и ранее, но при х < м изменяем кодирование на (к+ум) шот! рр', где у — случайное число, приназлежащее лнтервалу М~ — М < у < М~, При декодировании сначала вычисляем кубический корень и, если в результате получаем значение М вЂ” М или большее, берем остаток боот! М. з з 34. Пусть Р— вероятность того, что выполняется равенство х шот)р = 1; пусть также Ц вЂ” вероятность того, что выполняется равенство х™ тот! 9 = 1, Вероятность того.
что боб!(Х вЂ” 1, )ТТ) = р или 9, Равна Р(1 — бб!) + 0(1 — Р) = Р + й — 2Р1;). Если Р < -' нлн Т) < 1, данная вероятность > 2(10 е-10 '~), поэтому есть хорошие шансы найти простой множитель после выполнения примерно 10 1об гп арифметических операций по модулю тбб. С другой стороны, если Р > 1 и 0 > 1, то Р и Т<' ы 1, поскатьку есть оснощтая формула Р ы йо1(т, р — 1)/р; поэтому в подобном случае т кротно 1стп(р — 1, 9 — 1), Положим, что т = 2~г, где г нечетко, и построим последовательность х' пют! )р', хы шоб! Х, ..., з* „ х " шот! !т! так же, как и в результате выполпения алгоритма Р, получаем, что впервые 1 появится после значения у, не равного /ТР-1, с вероятностью, ие меньшей 1; следовательно, йод(у — 1, )ТГ) = р или 9.
36. Пусть / = (р' ' — 9' ') шоб Х Поскольку р шоб! 4 = 9 шот! 4 = 3, то (=') = (=-1) = Р О (/) ж -(ь) = -1 н, кроме того, (1) = -(3) = -1. Пусть для данного сообщения х в ч Р О интервале О < х < 1У(Ж вЂ” 5) имеем 2 = 4х+ 2 нли Зх+ 4, любое из которых удовлетворяет условию ( Ут ) м 1. Тогда передаем сообщение йз шоб! !ТР. Чтобы закодировать зто сообщение, сначала используем 84)йТ-блок для нахождения единственного числа у, такого, чтобы выполнялись условия уз щ йз шот! Ю и Щ = 1 и у было четным. Тогда имеем у = х, поскольку три остальных ктщлратных корня из числа йз равны !Тр — й и (х/х) шот! у; первый нз зтнх корней нечетный, два других имеют отрицательные символы Якоби.
Декодирование на этом завершается присвоением х +- (у/4], если у пюб! 4 = 2, и х т- (у/8] — в противном случае. Каждый, кто сможет декодировать такое закодированное сообщение, сможет найти множители числа )Тб„поскольку декодирование ложного сообщения хо пют! Х в случае, когда ( уе) = -1, позволяет обнаружить (х/) шоб! !р' и ((х/) шот! !Р) — 1 имеет нетривиальный наибольший общий делитель с числом !р'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
