Задания к работе №3

Задания к работе №3.

Вариант 1

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=214; б) m=85; в) m=202; г) m=23; д) m=343.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=11; б) m=46; в) m=242; г) m=169; д) m=280.

3. Проверить на простоту число m=299 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=209; б) m=299; в) m=403.

5. Факторизовать 205 ро-методом.

6.Факторизовать 639 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 3(mod 101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 5 (mod 103–1) ро-методом.

9. Вычислить log 5 2 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 71 (mod 73–1) методом исчисления порядка.

Вариант 2

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=298; б) m=146; в) m=127; г) m=74; д) m=169.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=13; б) m=22; в) m=98; г) m=119; д) m=130.

3. Проверить на простоту число m=293 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=451; б) m=323; в) m=253.

5. Факторизовать 361 используя ро-методом.

6. Факторизовать 177 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 5(mod 101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 9 (mod 103–1) ро-методом.

9. Вычислить log 5 3 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 70 (mod 73–1) методом исчисления порядка.

Вариант 3

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=103; б) m=52; в) m=62; г) m=12; д) m=121.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=59; б) m=262; в) m=50; г) m=18; д) m=240.

3. Проверить на простоту число m=289 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=221; б) m=481; в) m=391.

5. Факторизовать 689 используя ро-метод.

6. Факторизовать 1073 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 7(mod 101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 25 (mod 103–1) ро-методом.

9. Вычислить log 5 7 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 69 (mod 73–1) методом исчисления порядка

Вариант 4

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=283; б) m=55; в) m=73; г) m=153; д) m=125.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=17; б) m=6; в) m=27; г) m=250; д) m=122.

3. Проверить на простоту число m=283 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=377; б) m=803; в) m=533.

5. Факторизовать 473, используя ро-метод.

6. Факторизовать 319 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log211(mod101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 26 (mod 103–1) ро-методом.

9. Вычислить log 5 8 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 68 (mod 73–1) методом исчисления порядка.

Вариант 5

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=136; б) m=93; в) m=223; г) m=41; д) m=172.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=7; б) m=58; в) m=81; г) m=202; д) m=245.

3. Проверить на простоту число m=281 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=187; б) m=871; в) m=437.

5. Факторизовать 403 ро-методом.

6. Факторизовать 943 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log213(mod101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 33 (mod 103–1) ро-методом.

9. Вычислить log 5 10 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 67 (mod 73–1) методом исчисления порядка

Вариант 6

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=291; б) m=6; в) m=233; г) m=29; д) m=44.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=17; б) m=38; в) m=14; г) m=49; д) m=158.

3. Проверить на простоту число m=277 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=473; б) m=667; в) m=493.

5. Факторизовать 629 ро-методом.

6. Факторизовать 513 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log217(mod 101-1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 38 (mod 103–1) ро-методом.

9. Вычислить log 5 66 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 11 (mod 73–1) методом исчисления порядка.

Вариант 7

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=259; б) m=97; в) m=186; г) m=67; д) m=36.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=19; б) m=10; в) m=338; г) m=121; д) m=195.

3. Проверить на простоту число m=271 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=247; б) m=713; в) m=527.

5. Факторизовать 247 используя ро-методом.

6. Факторизовать 779 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log219(mod101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 39 (mod 103–1) ро-методом.

9. Вычислить log 5 65 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 12 (mod 73–1) методом исчисления порядка.

Вариант 8

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=250; б) m=91; в) m=262; г) m=81; д) m=68.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=23; б) m=62; в) m=18; г) m=289; д) m=238.

3. Проверить на простоту число m=269 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=551; б) m=517; в) m=221.

5. Факторизовать 817 ро-методом.

6. Факторизовать 561 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log223(mod101–1) методом «шаг младенца–шаг великана».

8. Вычислить log 6 42 (mod 103–1) ро-методом.

9. Вычислить log 5 64 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 13 (mod 73–1) методом исчисления порядка.

Вариант 9

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=253; б) m=179; в) m=204; г) m=87; д) m=49.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=29; б) m=74; в) m=162; г) m=343; д) m=120.

3. Проверить на простоту число m=263 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=583; б) m=589; в) m=559.

5. Факторизовать 517 ро-методом.

6. Факторизовать 299 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log229(mod 101–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 45 (mod 103–1) ро-методом.

9. Вычислить log 5 63 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 14 (mod 73–1) методом исчисления порядка.

Вариант 10

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=293; б) m=225; в) m=141; г) m=32; д) m=82.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=31; б) m=82; в) m=578; г) m=81; д) m=194.

3. Проверить на простоту число m=257 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=319; б) m=629; в) m=611.

5. Факторизовать 365 ро-методом.

6. Факторизовать 209 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log231(mod 101–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 49 (mod 103–1) ро-методом.

9. Вычислить log 5 62 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 15 (mod 73–1) методом исчисления порядка.

Вариант 11

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=284; б) m=191; в) m=182; г) m=25; д) m=54.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=37; б) m=86; в) m=54; г) m=25; д) m=132.

3. Проверить на простоту число m=251 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=341; б) m=297; в) m=689.

5. Факторизовать 221 ро-методом.

6. Факторизовать 299 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 5 3(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 61 (mod 103–1) ро-методом.

9. Вычислить log 5 16 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 5 (mod 73–1) методом исчисления порядка.

Вариант 12

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=241; б) m=171; в) m=140; г) m=13; д) m=34.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=41; б) m=94; в) m=18; г) m=49; д) m=183.

3. Проверить на простоту число m=247 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=369; б) m=363; в) m=697.

5. Факторизовать 451 ро-методом.

6. Факторизовать 403 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 5 4(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 58 (mod 103–1) ро-методом.

9. Вычислить log 5 60 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 17 (mod 73–1) методом исчисления порядка.

Вариант 13

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=290; б) m=131; в) m=184; г) m=19; д) m=50.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=43; б) m=106; в) m=250; г) m=343; д) m=221.

3. Проверить на простоту число m=241 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=351; б) m=341; в) m=703.

5. Факторизовать 793 ро-методом.

6. Факторизовать 451методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 5 6(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 61 (mod 103–1) ро-методом.

9. Вычислить log 5 59 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 18 (mod 73–1) методом исчисления порядка.

Вариант 14

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=292; б) m=181; в) m=122; г) m=89; д) m=98.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=47; б) m=118; в) m=54; г) m=121; д) m=198.

3. Проверить на простоту число m=239 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=507; б) m=407; в) m=851.

5. Факторизовать 377 ро-методом.

6. Факторизовать 323 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 7(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 64 (mod 103–1) ро-методом.

9. Вычислить log 5 58 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 19 (mod 73–1) методом исчисления порядка.

Вариант 15

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=251; б) m=168; в) m=231; г) m=99; д) m=43.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=53; б) m=134; в) m=578; г) m=9; д) m=276.

3. Проверить на простоту число m=233 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=583; б) m=87; в) m=459.

5. Факторизовать 649 ро-методом.

6. Факторизовать 253 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 8(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 74 (mod 103–1) ро-методом.

9. Вычислить log 5 57 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 20 (mod 73–1) методом исчисления порядка.

Вариант 16

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=200; б) m=177; в) m=142; г) m=94; д) m=65.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=61; б) m=142; в) m=18; г) m=25; д) m=205.

3. Проверить на простоту число m=229 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=429; б) m=621; в) m=799.

5. Факторизовать 121 ро-методом.

6. Факторизовать 221методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log610(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 83 (mod 103–1) ро-методом.

9. Вычислить log 5 56 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 21 (mod 73–1) методом исчисления порядка.

Вариант 17

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=255; б) m=193; в) m=101; г) m=86; д) m=22.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=67; б) m=146; в) m=162; г) m=49; д) m=219.

3. Проверить на простоту число m=227 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=649; б) m=51; в) m=171.

5. Факторизовать 335 ро-методом.

6. Факторизовать 481методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log611(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 92 (mod 103–1) ро-методом.

9. Вычислить log 5 55 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 22 (mod 73–1) методом исчисления порядка.

Вариант 18

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=285; б) m=173; в) m=138; г) m=7; д) m=17.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=71; б) m=166; в) m=50; г) m=121; д) m=8.

3. Проверить на простоту число m=223 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=793; б) m=689; в) m=93.

5. Факторизовать 493 ро-методом.

6. Факторизовать 391 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log613(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 93 (mod 103–1) ро-методом.

9. Вычислить log 5 54 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 23 (mod 73–1) методом исчисления порядка.

Вариант 19

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=211; б) m=197; в) m=102; г) m=95; д) m=47.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=5; б) m=178; в) m=162; г) m=27; д) m=12.

3. Проверить на простоту число m=221 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=731; б) m=779; в) m=123.

5. Факторизовать 299 ро-методом.

6. Факторизовать 377 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log614(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 6 96 (mod 103–1) ро-методом.

9. Вычислить log 5 53 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 24 (mod 73–1) методом исчисления порядка.

Вариант 20

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=243; б) m=151; в) m=58; г) m=139; д) m=174.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=71; б) m=206; в) m=54; г) m=25; д) m=15.

3. Проверить на простоту число m=211 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=767; б) m=639; в) m=513.

5. Факторизовать 527 ро-методом.

6. Факторизовать 803 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log643(mod 103–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 5 (mod 101–1) ро-методом.

9. Вычислить log 5 52 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 26 (mod 73–1) методом исчисления порядка.

Вариант 21

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=232; б) m=180; в) m=137; г) m=83; д) m=69.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=89; б) m=10; в) m=338; г) m=9; д) m=16.

3. Проверить на простоту число m=199 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=737; б) m=291; в) m=153.

5. Факторизовать 697 ро-методом.

6. Факторизовать 533 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 3(mod 107–1) методом «шаг младенца–шаг великана».

8. Вычислить log 2 9 (mod 101–1) ро-методом.

9. Вычислить log 5 51 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 27 (mod 73–1) методом исчисления порядка.

Вариант 22

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=256; б) m=194; в) m=162; г) m=96; д) m=79.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=89; б) m=214; в) m=250; г) m=289; д) m=20.

3. Проверить на простоту число m=197 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=799; б) m=899; в) m=561.

5. Факторизовать 143 ро-методом.

6. Факторизовать 187 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 5(mod 107–1) методом «шаг младенца–шаг великана».

8. Вычислить log 2 10 (mod 101–1) ро-методом.

9. Вычислить log 5 50 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 28 (mod 73–1) методом исчисления порядка.

Вариант 23

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=221; б) m=199; в) m=128; г) m=71; д) m=38.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=73; б) m=218; в) m=54; г) m=121; д) m=21.

3. Проверить на простоту число m=193 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=779; б) m=561; в) m=299.

5. Факторизовать 325 ро-методом.

6. Факторизовать 871 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 6(mod 107–1) методом «шаг младенца–шаг великана».

8. Вычислить log 2 18 (mod 101–1) ро-методом.

9. Вычислить log 5 49 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 30 (mod 73–1) методом исчисления порядка.

Вариант 24

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=260; б) m=195; в) m=163; г) m=72; д) m=14.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=79; б) m=226; в) m=18; г) m=169; д) m=24.

3. Проверить на простоту число m=191 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=319; б) m=943; в) m=513.

5. Факторизовать 481 ро-методом.

6. Факторизовать 437 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 2 7(mod 107–1) методом «шаг младенца–шаг великана».

8. Вычислить log 2 19 (mod 101–1) ро-методом.

9. Вычислить log 5 48 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 31 (mod 73–1), методом исчисления порядка.

Вариант 25

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=281; б) m=178; в) m=132; г) m=92; д) m=61.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=83; б) m=254; в) m=98; г) m=27; д) m=26.

3. Проверить на простоту число m=181 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=639; б) m=177; в) m=1073.

5. Факторизовать 779 ро-методом.

6. Факторизовать 473 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log219(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 28 (mod 101–1) ро-методом.

9. Вычислить log 5 47 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 32 (mod 73–1) методом исчисления порядка.

Вариант 26

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=249; б) m=198; в) m=143; г) m=77; д) m=51.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=97; б) m=274; в) m=2; г) m=9; д) m=28.

3. Проверить на простоту число m=179 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=209; б) m=299; в) m=403.

5. Факторизовать 407 ро-методом.

6. Факторизовать 667 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log237(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 31 (mod 101–1) ро-методом.

9. Вычислить log 5 46 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 33 (mod 73–1) методом исчисления порядка.

Вариант 27

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=252; б) m=190; в) m=167; г) m=90; д) m=46.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=101; б) m=278; в) m=289; г) m=250; д) m=30.

3. Проверить на простоту число m=173 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=451; б) m=323; в) m=253.

5. Факторизовать 187 ро-метод.

6. Факторизовать 493 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log247(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 35 (mod 101–1) ро-методом.

9. Вычислить log 5 45 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 34 (mod 73–1) методом исчисления порядка.

Вариант 28

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=286; б) m=196; в) m=157; г) m=88; д) m=5.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=103; б) m=298; в) m=22; г) m=343; д) m=32.

3. Проверить на простоту число m=169 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=221; б) m=481; в) m=391.

5. Факторизовать 310 ро-методом.

6. Факторизовать 551 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log253(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 38 (mod 101–1) ро-методом.

9. Вычислить log 5 44 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 35 (mod 73–1) методом исчисления порядка.

Вариант 29

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=287; б) m=192; в) m=133; г) m=84; д) m=4.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=3; б) m=202; в) m=50; г) m=49; д) m=33.

3. Проверить на простоту число m=167 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=377; б) m=803; в) m=533.

5. Факторизовать 667 ро-методом.

6. Факторизовать 517 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log259(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 42 (mod 101–1) ро-методом.

9. Вычислить log 5 43 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 36 (mod 73–1) методом исчисления порядка.

Вариант 30

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=227; б) m=189; в) m=176; г) m=80; д) m=3.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=107; б) m=4; в) m=242; г) m=27; д) m=34.

3. Проверить на простоту число m=163 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=187; б) m=871; в) m=437

5. Факторизовать число 731ро-методом.

6. Факторизовать 221 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log261(mod 107–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 52 (mod 101–1) ро-методом.

9. Вычислить log 5 42 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 37 (mod 73–1) методом исчисления порядка.

Вариант 31

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=261; б) m=188; в) m=135; г) m=78; д) m=8.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=109; б) m=214; в) m=338; г) m=81; д) m=35.

3. Проверить на простоту число m=157 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=473; б) m=667; в) m=493.

5. Факторизовать 437ро-методом.

6. Факторизовать 583 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 2(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 67 (mod 101–1) ро-методом.

9. Вычислить log 5 41 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 38 (mod 73–1) методом исчисления порядка.

Вариант 32

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=244; б) m=187; в) m=130; г) m=76; д) m=9.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=113; б) m=218; в) m=162; г) m=125; д) m=36.

3. Проверить на простоту число m=151 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=247; б) m=713; в) m=527.

5. Факторизовать 319 ро-методом.

6. Факторизовать 589 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 3 (mod 109–1)методом «шаг младенца-шаг великана».

8. Вычислить log 2 76 (mod 101–1) ро-методом.

9. Вычислить log 5 40 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 39 (mod 73–1) методом исчисления порядка.

Вариант 33

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=247; б) m=185; в) m=123; г) m=75; д) m=11.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=127; б) m=226; в) m=50; г) m=289; д) m=39.

3. Проверить на простоту число m=149 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=551; б) m=517; в) m=221.

5. Факторизовать 533 ро-методом.

6. Факторизовать 559 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 5(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 77 (mod 101–1) ро-методом.

9. Вычислить log 5 39 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 40 (mod 73–1) методом исчисления порядка.

Вариант 34

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=207; б) m=183; в) m=113; г) m=53; д) m=31.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=131; б) m=194; в) m=18; г) m=361; д) m=40.

3. Проверить на простоту число m=139 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=583; б) m=589; в) m=559.

5. Факторизовать 767 ро-методом.

6. Факторизовать 319 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 7(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 91 (mod 101–1) ро-методом.

9. Вычислить log 5 38 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 41 (mod 73–1) методом исчисления порядка.

Вариант 35

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=209; б) m=159; в) m=114; г) m=48; д) m=18.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=137; б) m=178; в) m=250; г) m=343; д) m=42.

3. Проверить на простоту число m=137 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=319; б) m=629; в) m=611.

5. Факторизовать 551 ро-методом.

6. Факторизовать 629 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log 6 8(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 96 (mod 101–1) ро-методом.

9. Вычислить log 5 37 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 42 (mod 73–1) методом исчисления порядка.

Вариант 36

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=203; б) m=164; в) m=104; г) m=66; д) m=37.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=139; б) m=166; в) m=338; г) m=289; д) m=44.

3. Проверить на простоту число m=131 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=341; б) m=297; в) m=689.

5. Факторизовать 323 ро-методом.

6. Факторизовать 611 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log610(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 97 (mod 101–1) ро-методом.

9. Вычислить log 5 36 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 43 (mod 73–1) методом исчисления порядка.

Вариант 37

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=206; б) m=175; в) m=106; г) m=57; д) m=39.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=149; б) m=158; в) m=162; г) m=169; д) m=45.

3. Проверить на простоту число m=127 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=369; б) m=363; в) m=697.

5. Факторизовать 611 ро-методом.

6. Факторизовать 341 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log611(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 98 (mod 101–1) ро-методом.

9. Вычислить log 5 35 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 44 (mod 73–1) методом исчисления порядка.

Вариант 38

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=248; б) m=165; в) m=129; г) m=64; д) m=27.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=151; б) m=146; в) m=54; г) m=361; д) m=48.

3. Проверить на простоту число m=113 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=507; б) m=407; в) m=851.

5. Факторизовать 391 ро-методом.

6. Факторизовать 297 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log613(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 10 (mod 107–1) ро-методом.

9. Вычислить log 5 34 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 45 (mod 73–1) методом исчисления порядка.

Вариант 39

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=217; б) m=166; в) m=118; г) m=70; д) m=59.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=157; б) m=142; в) m=250; г) m=81; д) m=51.

3. Проверить на простоту число m=109 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=507; б) m=407; в) m=851.

5. Факторизовать 559 ро-методом.

6. Факторизовать 689 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log614(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 28 (mod 107–1) ро-методом.

9. Вычислить log 5 33 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 46 (mod 73–1) методом исчисления порядка.

Вариант 40

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=219; б) m=149; в) m=134; г) m=59; д) m=26.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=163; б) m=122; в) m=242; г) m=338; д) m=52.

3. Проверить на простоту число m=107 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=583; б) m=87; в) m=459.

5. Факторизовать 583 ро-методом.

6. Факторизовать 803 методом случайных квадратов с базой {2,3,5,7}.

7. Вычислить log615(mod 109–1) методом «шаг младенца-шаг великана».

8. Вычислить log 2 38 (mod 107–1) ро-методом.

9. Вычислить log 5 32 (mod 97–1) методом Полига-Хэллмана.

10. Вычислить log 5 47 (mod 73–1) методом исчисления порядка.

Решение варианта 40 работы №3

1. Сколько порождающих элементов в Z*m? Найти порождающий элемент, если они существуют.

а) m=219; б) m=149; в) m=134; г) m=59; д) m=26.

Решение:

а) 219=3·73 – составное, не 2, 4, pα, 2 pα .

Ответ: Порождающих нет.

б) 149 – простое число. Количество порождающих составляет φ(φ(149))=φ(148)=φ(22·37)=1·2·36=72 элемента. Найдем какой-нибудь порождающий для Z*149.

φ(149)=148=22·37.

2: 24 mod 149=16 mod 149=16≠1;

274 mod 149=148≠1.

Ответ: 2 – порождающий элемент Z*149, количество порождающих – 72.

в) 134=2·67. Количество порождающих есть φ(φ(134))=φ(66)=φ(2·3·11)= =1·2·10=20 . Найдем какой-нибудь порождающий для Z*134.

φ(134)=66=2·3·11.

3: 36 mod 134=723 mod 149=53≠1;

322 mod 134=1. 3 – не порождающий элемент Z*134.

5: 56 mod 134=81≠1;

522 mod 134=1. 5 – не порождающий элемент Z*134.

7: 76 mod 134=131≠1;

722 mod 134=29≠1;

733 mod 134=133≠1; 7 – порождающий элемент Z*134

Ответ: 7 – порождающий элемент Z*134, количество порождающих – 20.

г) 59 – простое число. Количество порождающих есть φ(φ(59))=φ(58)= =φ(2·29)=1·28=28. Найдем какой-нибудь порождающий для Z*59.

φ(59)=58=2·29.

2: 22 mod 59=4≠1;

229 mod 59=58≠1; 2 – порождающий элемент Z*59.

Ответ: 2 – порождающий элемент Z*59, количество порождающих – 28.

д) 26=2·13. Количество порождающих есть φ(φ(26))=φ(12)=φ(22·3)= =1·2·2=4 . Найдем какой-нибудь порождающий для Z*26.

φ(26)=12=22·3.

3: 36 mod 26=1. 3 – не порождающий элемент Z*26.

5: 56 mod 26=25≠1;

54 mod 26=1. 5 – не порождающий элемент Z*26.

7: 76 mod 26=25≠1;

74 mod 26=9≠1; 7 – порождающий элемент Z*26.

Ответ: 7 – порождающий элемент Z*26, количество порождающих – 4.

2. Какие из чисел 2, 3, 4, m-2, m-3, m-4 являются порождающими элементами Z*m?

а) m=163; б) m=122; в) m=242; г) m=338; д) m=52.

Решение:

а) 163 – простое число. Порождающие элементы в Z*163 существуют.

φ(163)=162=2·34. Проверим, являются ли 2, 3, 4, -2, -3, -4 порождающими элементами Z*163.

2: 281 mod 163=162≠1; (-2): (-2)81 mod 163=1.

254 mod 163=104≠1.

3: 381 mod 163=162≠1; (-3): (-3)81 mod 163=1.

354 mod 163=58≠1.

4: 481 mod 163=1. (-4): (-4)81 mod 163=162≠1;

(-4)54 mod 163=58≠1.

Ответ: 2, 3, -4 являются порождающими элементами Z*163, -2,-3, 4 – нет.

б) 122=2·61. Порождающие элементы в Z*122 существуют.

φ(122)=60=22·3·5.

2, -2, 4, -4 не принадлежат Z*122, поэтому порождающими не являются. Проверим, являются ли 3 и (-3) порождающими элементами Z*122.

3: 312 mod 122=9≠1; (-3): (-3)12 mod 163=9≠1;

320 mod 122=1. (-3)20 mod 122=1.

Ответ: ни одно из заданных чисел не является порождающим элементом Z*122.

в) 242=2·112. Порождающие элементы в Z*242 существуют.

φ(242)=110=2·5·11.

2, -2, 4, -4 не принадлежат Z*242, поэтому порождающими не являются. Проверим, являются ли 3 и (-3) порождающими элементами Z*242.

3: 310 mod 242=1. (-3): (-3)10 mod 242=1.

Ответ: ни одно из заданных чисел не является порождающим элементом Z*242.

г) 338=2·132. Порождающие элементы в Z*338 существуют.

φ(338)=156=22·3·13.

2, -2, 4, -4 не принадлежат Z*338, поэтому порождающими не являются. Проверим, являются ли 3 и (-3) порождающими элементами Z*338.

3: 312 mod 338=105≠1; (-3): (-3)12 mod 163=105≠1;

352 mod 338=315≠1; (-3)52 mod 338=315≠1;

378 mod 338=1. (-3)78 mod 338=1.

Ответ: ни одно из заданных чисел не является порождающим элементом Z*338.

д) 52=22·13. Порождающих элементов нет.

Ответ: ни одно из заданных чисел не является порождающим элементом Z*52.

3. Проверить на простоту число m=107 тестом Поклингтона. Число итераций = 3. Основания a выбирать произвольно.

Решение:

107-1=106=2·53. —1<11. F=53, R=2.

Проверка условий:

a=2.

1) 2106 mod 107=1.

2)22 mod 4021=4≠1.

Поскольку первая же проверка дала положительный результат, то нет смысла проводить другие проверки.

Ответ: 107 – простое число.

4. Факторизовать m методом квадратичного решета с решетами по модулям 4, 5, 7. а) m=583.

а) m=583. Построим решёта по модулям 4, 5 и 7:

x	0	1	2	3
x2mod 4	0	1	0	1
Z=x2–583 mod 4	1	2	1	2
S4		X		X

x	0	1	2	3	4
x2mod 5	0	1	4	4	1
z=x2–583 mod 5	2	3	1	1	3
S5	X	X			X

x	0	1	2	3	4	5	6
x2mod 7	0	1	4	2	2	4	1
z=x2–583 mod 7	5	6	2	0	0	2	6
S7	X	X					X

Наложим решёта на последовательность чисел от +1=25 до (m+1)/2=292.

Поскольку 25 mod 4 = 1, то наложение решета S4 начнем с S4(1),

25 mod 5 = 0, то наложение решета S5 начнем с S5(0),

25 mod 7 = 4, то наложение решета S7 начнем с S7(4).

x

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

S4

X

X

X

X

X

X

X

X

X

S5

X

X

X

X

X

X

X

X

X

X

X

S7

X

X

X

X

X

X

X

X

Проверим оставшиеся невычеркнутыми числа::

x=32, x2=1024, z=x2—m=441=212. y=21.

Тогда a=x+y=53, b=x—y=11.

Ответ: 583=53·11.

5. Факторизовать 583 ро-методом.

Решение:

В качестве циклической функции возьмем f(x)=(x2+1) mod 583 и составим последовательность, где x1 и x2 вычисляются рекурсивно (x1=f(x1), x2=f(f(x2)).

Шаг	0	1	2
x1	2	5	26
x2	2	26	92
a=|x1-x2|	-	21	66
d=НОД(a,583)	-	1	11

f(2)=(22+1) mod 583=5: f(5)=(52+1) mod 583=26; f(26)=(262+1) mod 583=94; f(94)=(942+1) mod 583=92.

Поскольку нашлось d:1<d<583, то заключаем, что d\583, а значит 583=11·53.

Ответ: 583=11·53.

6. Факторизовать 803 методом случайных квадратов с базой {2,3,5,7}.

Решение:

Найдем 5 пар ai, bi, где bi=(ai2 mod 803) раскладываются по факторной базе:

a=39, b=1521 mod 803=718=2·359;

a=40, b=1600 mod 803=797 – простое;

a=41, b=1681 mod 803=75=3·52;

a=42, b=1764 mod 803=158=2·79;

a=43, b=1849 mod 803=243=35;

a=44, b=1936 mod 803=330=2·3·5·11;

a=45, b=2025 mod 803=419 – простое;

a=46, b=2116 mod 803=510=2·3·5·17;

a=47, b=2209 mod 803=603=32·67;

a=48, b=2304 mod 803=698=2·349;

a=49, b=2401 mod 803=795=3·5·53;

a=50, b=2500 mod 803=91=7·13;

a=51, b=2601 mod 803=192=26·3;

a=52, b=2704 mod 803=295=5·59;

a=53, b=2809 mod 803=400=24·52;

a=54, b=2916 mod 803=507=3·132;

a=55, b=3025 mod 803=616=23·7·11;

a=56, b=3136 mod 803=727-простое;

a=57, b=3249 mod 803=37 – простое;

a=58, b=3364 mod 803=152=23·19;

a=59, b=3481 mod 803=269 – простое;

a=60, b=3600 mod 803=388=22·97;

a=61, b=3721 mod 803=509 – простое;

a=62, b=3844 mod 803=632=23·79;

a=63, b=3969 mod 803=757 – простое;

a=64, b=4096 mod 803=81=34.

Итак, найдены 5 пар ai, bi. Теперь составим и решим систему сравнений относительно сi:

Система имеет множесво решений, одно из которых: с1=с2=1, с3=с4=с5=0.

Вычислим x и y для данного решения:

x==41·43=1763,

y==2(0+0)/2·3(1+5)/2·5(2+0)/2·7(0+0)/2=33·5=135.

НОД(803,x-y)=НОД(803,1628)=11 Þ11\803.

Ответ: 803=11·73.

7. Вычислить log615(mod 109–1) методом «шаг младенца-шаг великана».

Решение:

a=15, g=6, p=109. m=éÖpù=11.

Вычислим последовательности ui=(agi)mod p и vj=(gmj) mod p, где i, j от 1 до m.

i, j	1	2	3	4	5	6	7	8	9	10	11
ui	90	104	79	38	10	60	33	89	98	43	40
vj	39	104	23	25	103	93	30	80	68	36	96

Надем совпадающие элементы. Имеем u2=v2=104, полученные при i=2, j=2. Тогда log615≡mj-i≡11·2-2≡20(mod 109–1).

Проверка: 620 mod 109=15. Верно.

Ответ: log615≡20(mod 109–1).

8. Вычислить log 2 38 (mod 107–1) ро-методом.

Решение:

a=38, g=2,p=107.

Вычислим последовательность xi=, относя xi к множеству Sm, если xi≡m(mod 3) и приняв x0=1. Также вычислим последовательности ui и vi, члены которых суть кратность g и a в xi соответственно.

i	0	1	2	3	4	5
xi	1	38	53	27	54	1
ui	0	0	0	0	1	2
vi	0	1	2	4	4	4
S	S1	S2	S2	S3	S3	S1

В последовательности хi встретилось повторение: x0=x5=1. Дискретный логарифм найдем, решив сравнение (v0—v5)log238≡(u5—u0) (mod p-1).

(0-4)log238≡(2—0) (mod 106) Þ 4log238≡-2 (mod 106).

Правая, левая части и модуль данного сравнения делятся на 2, поэтому сравнение имеет 2 решения.

2log238≡-1 (mod 5≡27(mod 53)Þ log238≡-27≡26 (mod 53).

Отсюда получаем 2 решения исходного сравнения: log238≡26 (mod 106), либо log238≡79 (mod 106). Определим, которое из них является значением логарифма: 226 mod 107=69, 279 mod 107=38.

Ответ: log238≡79 (mod 106).

9. Вычислить log 5 32 (mod 97–1) методом Полига-Хэллмана.

Решение:

a=32, g=5, p=97, n=p-1=96=25·3.

i=1: q=2, α=5, γ=1, l-1=0, =548 mod 97=96.

j=0: γ= γ·=1·50=1, =(32·1-1)48 mod 97=1,

l0==log961=0;

j=1: γ= 1·50=1 , =(32·1-1)24 mod 97=96, l1=log9696=1;

j=2: γ= 1·51·2=25 , =(32·25-1)12 mod 97=1, l2=log961=0;

j=3: γ= 25·50=25 , =(32·25-1)6 mod 97=96, l3=log9696=1;

j=4: γ= 25·51·8 mod 97=53 , =(32·53-1)3 mod 97=1, l4=log961=0.

x1= l0+l1q+…+lα—1qα—1=0+2+0+8+0=10.

i=2: q=3, α=1, γ=1, l-1=0, =532 mod 97=35.

j=0: γ=1·50=1, =(32·1-1)32 mod 97=61, l0=log3561=2.

x2= l0+l1q+…+lα—1qα—1=2.

Теперь составим и решим систему:

x≡74(mod 96). Решение этой системы и будет значением искомого дискретного логарифма.

Ответ: log532≡74(mod 97-1).

10. Вычислить log 5 47 (mod 73–1) методом исчисления порядка.

Решение:

a=47, g=5, p=73. Выберем факторную базу S={2,3,5}.

Будем перебирать всевозможные значения loggp<k<p-1 и пытаться разложить по факторной базе значения gkmod p:

k=3, 53mod 73=52=22·13;

k=4, 54mod 73=41 - простое;

k=5, 55mod 73=59 - простое;

k=6, 56mod 73=3;

k=7, 57mod 73=15=3·5;

k=8, 58mod 73=2.

Поскольку факторная база состоит из 3-х элементов, достаточно 3-х таких разложений. Имеем сравнения с неизвестными-логарифмами:

6≡log5 3 (mod 72);

7≡log5 3+ log5 5 (mod 72);

8≡log5 2 (mod 72).

Откуда, после очевидных преобразований, имеем: log52≡8(mod 72), log53≡6(mod 72), log55≡1(mod 72).

Перебираем всевозможные 0<k<p и пытаться разложить по факторной базе значения (agk)mod p:

k=1, (47·51) mod 73=16=24.

Первая же попытка оказалась удачной. Теперь можем получить искомое значение дискретного логарифма: log547≡4·log52-1≡4·8-1≡31(mod 72).

Ответ: log547≡31(mod 72).