08.04.09.Печать_edit

75.Доказать, что для простых чисел вида p 2k rz 1, где r, z и — простые числа, вероятность случайного выбора числа ( < p), относящегося по модулю p к показателю ( < p 1), не содержащему делитель , равна

1/ .

76.Доказать, что нечетное число a является первообразным корнем по модулю 2p тогда и только тогда, когда a является первообразным корнем по модулю p.

77.Сколько существует различных первообразных корней по модулю 2p?

78.Доказать, что нечетное число a является первообразным корнем по мо-

дулю 2p тогда и только тогда, когда a является первообразным корнем по модулю p .

79. Доказать, что нечетное число a относится по модулю 2p , где ≥ 1, к

показателю | p –1(p 1) тогда и только тогда, когда a относится по мо-

дулю p к показателю .

80.Показать, что число классов, относящихся по модулю 2p к показате-

лю | p (p 1), равно числу классов, относящихся к как к показателю по модулю p .

81.Сколько существует различных чисел, относящихся по модулю 2p к показателю | (p 1)?

82.Числа a и b относятся по модулю n к показателям и , соответственно.

Показать, как можно найти число x, относящееся к показателю

= НОД ( , ).

83.Числа a и b относятся по модулю n к показателям и , соответственно.

Показать, как можно найти число x, относящееся к показателю =

=НОК[ , ].

84.Показать, что для значения b, являющегося взаимно простым с n, вы-

полняется соотношение a/b ab (n) –1 mod n, где (n) — функция Эйлера.

91

85.Вывести формулу (p ) = p 1(p 1) для значения функции Эйлера от числа p , где p — простое число.

86.Сколько в множестве последовательных натуральных чисел {1, 2, …, 5000} имеется таких чисел, которые являются взаимно простыми с числом

50?

87.Сколько в множестве последовательных натуральных чисел {1, 2, …, 30000} имеется таких чисел, которые не являются взаимно простыми с числом 50?

88.Предложить способ генерации простого числа p длины |p|, такого что

p 1 содержит заданный простой множитель длины | | 1 | p | .

4

89.Доказать, что число a, относящееся по модулю p , где > 1, к простому показателю ≠ p, относится к этому же показателю и по модулю p.

90.Доказать, что первообразный корень по простому модулю p относится по модулю p , где > 1, к показателю p – i (p – 1), где i {1, 2, …, }.

91.Показать, что число a, относящееся по модулю p к простому показате-

лю , не всегда относится к этому же показателю и по модулю p , где α > 1.

Указать число a, такое что 1 mod p и mod p 1.

92.	Показать, что для числа a, относящегося по модулю p к показателю
= p i, где i = 1, 2, …, – 1, выполняется сравнение a ≡ 1 mod p.
93.	Показать, что для числа a, относящегося по модулю p к показателю

= p i , где — простой делитель числа p 1 и i = 1, 2, …, – 1, выполня-

ется сравнение a ≡ 1 mod p, т. е. a относится по модулю p к показателю .

94.Доказать, что при простом p число p 1 относится по модулю p к пока-

зателю 2. Существуют ли числа другого вида, относящиеся по простому модулю к показателю 2?

95. По какому из модулей 13, 79 и 89 существует больше чисел, относящихся к показателю 3?

92

96. Доказать следующее утверждение. Если существует квадратный корень из a по модулю m = p1 ∙ p2 ∙…∙ ps , то a — квадратичный вычет по каждому из простых модулей p1, p2, …, ps.

97. Найти все числа, относящиеся к показателю 2 одновременно по модулю 13 и по модулю 43.

98. Найти все числа, относящиеся к показателю 2 одновременно по модулю 77 и по модулю 119.

99. Показать, что для простых чисел p и q задача дискретного логарифмирования по RSA-модулю n = pq эквивалентна по сложности задаче дискретного логарифмирования по модулям p и q.

100. Решить систему сравнений x a mod m1 (1) и x b mod m2 (2) для случая НОД (m1, m2) = 1.

101. Вычислить значение 357127 mod 19 .

x 17 mod 39,

102. Решить систему сравнений

x2 19 mod 79.

x 11 mod 51,

103. Решить систему сравнений

x3 11 mod 47.

x 11 mod 51,

104. Решить систему сравнений

x2 11 mod 47.

x 37 mod1 37,

105. Решить систему сравнений

x10 37 mod 127.

106. Сколько решений имеют сравнения x4 ≡ 37 mod 79 (1); x4 ≡ 76 mod 79

(2) и x4 ≡ 9 mod 79 (3)?

107. Определить, какие из чисел 1034, 1234, 1959, 2477, 3074 и 4179 явля-

ются квадратичными вычетами по RSA-модулю n = 5963.

108. Вычислить значение функции Эйлера и обобщенной функции Эйлера для чисел 2301; 900 и 10965.

93

109.Вычислить значение функции Эйлера и обобщенной функции Эйлера для чисел 2(216 + 1); 254; 2k, где k — натуральное число.

110.Найти линейное представление с целыми коэффициентами для наибольшего общего делителя чисел a = 13; b = 87.

111.Найти линейное представление для наибольшего общего делителя чи-

сел а = 11; b = 97.

112.Найти линейное представление для наибольшего общего делителя чи-

сел а = 23; b = 121.

113.Найти линейное представление для наибольшего общего делителя чи-

сел а = 35; b = 169.

114.Найти все целочисленные решения уравнения 34x + 289y = 187.

115.Извлечь кубический корень из чисел 5, 21, 31, 32, 36, 37 и 39 по моду-

лю 41.

116.Извлечь квадратный корень из чисел 11, 17, 51, 99, 105, 121 и 132 по модулю 139.

117.Извлечь корень четвертой степени по модулю 137 из числа 81.

118.Решить сравнение x3 8 mod 19.

119.Решить сравнение x5 32 mod 101.

120.Пусть x0 есть корень сравнения nx a mod p, где a ≠ 1, и n | p – 1. Описать процедуру нахождения всех остальных корней.

121.Сколько решений имеют сравнения x3 89 mod 139 (1), x3 33 mod 139

(2)и x3 89 mod 137 (3)?

x a mod 139,

122. При каких значениях a система сравнений x3 45 mod 139 имеет реше-

ния?

123.По каким простым модулям число 1521 является квадратичным вычетом?

124.По каким простым модулям число N p12s1 p22s2 ... pk2sk , где p1, p2,

…, pk — простые числа, является квадратичным вычетом?

94

125.Корни каких степеней n (n ≤ 66) из числа 58 существуют по модулю

67?

126.Доказать, что первообразный корень по простому модулю является невычетом по любой степени.

Cписок литературы

1.Бухштаб А. А. Теория чисел. — М.: Просвещение. — 1966. — 384 с.

2.Виноградов И. М. Основы теории чисел. — М.: Наука. — 1972. — 167 с.

3.Молдовян Н. А., Молдовян А. А. Введение в криптосистемы с открытым ключом.- СПб: БХВ – Петербург, 2005.-286 с.

4.Молдовян Н. А. Практикум по криптосистемам с открытым ключом.- СПб: БХВ – Петербург, 2007.-298 с.

95