Методические указания Для выполнения лабораторной работы следует ознакомиться с теоретическим - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Методические указания к лабораторной работе 7 для студентов по специальности... 1 280.05kb.
Н. Э. Баумана Методические указания для лабораторной работы по курсам... 3 491.09kb.
Методические указания для выполнения курсовой работы студентами IV-V... 3 703.53kb.
Перед решением каждой задачи следует ознакомиться с исходными данными... 1 239.23kb.
Ветеринарная вирусология 3 395.38kb.
Администрирование в информационных сетях: Методические указания к... 1 177.85kb.
Методические указания для выполнения контрольной работы по дисциплине 1 105.46kb.
Методические указания по выполнению лабораторной работы «Оказание... 1 511.04kb.
Учебно-методические указания к выполнению лабораторной работы по... 1 209.52kb.
Методические указания по выполнению контрольной работы для направлений... 1 138.13kb.
Методические указания для выполнения контрольной работы студентами... 1 370.66kb.
Использование тестовых технологий на уроках литературы в школе 1 172.11kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Методические указания Для выполнения лабораторной работы следует ознакомиться с теоретическим - страница №1/1

Лабораторная работа №1. Тесты разложимости и тесты простоты



1. Цель лабораторнойработы

Целью лабораторной работы является практическое ознакомление с тестами разложимости и тестами простоты чисел, а также с методами построения больших простых чисел.




  1. Методические указания

Для выполнения лабораторной работы следует ознакомиться с теоретическим введением Тесты простоты и тесты разложимости и ответить на Контрольные вопросы. Предполагается также, что усвоены разделы Назначение, Инструкция и Вычисления (в кольцах Z и Zn) страницы Алгебраический процессор.

Вычисления осуществлять в разделе Вычисления, используя операции в кольцах Z и Zn.

Результаты выполнения лабораторной работы представьте в отчете, в котором должны также присутствовать определения всех использованных в формулировке задания терминов, реализованных при выполнении задания тестов простоты и разложимости, а также результаты вычислений в соответствии с приведенными в заданиях указаниями или примерами.

В отчете следует также представить имена использованных алгебраических операций, имена с соответствующих функций библиотеки и описания соответствующих алгоритмов (с использованием функции Помощь алгебраического процессора).


2.Задания

Задание 1. Тест разложимости Ферма. Определите свидетелей разложимости Ферма и лжесвидетелей Ферма простоты числа n=21, для чего постройте таблицу значений a20mod 21 и НОД(a,n) для чисел a{2,…,20}.

Задание 2. Тест разложимости Ферма. Числа Кармайкла. Определите лжесвидетелей простоты Ферма числа Кармайкла n=561, лежащих в интервале [N(k), N(k)+17]. Обратите внимание, что в данном случае все числа, взаимно простые с n, являются лжесвидетелями простоты Ферма числа n.

Число N(k) взять из таблицы (k - номер по журналу группы или число, указанное преподавателем).



k

1

2

3

4

5

6

7

8

9

10

N(k)

51

93

138

185

234

285

338

2

59

118

k

11

12

13

14

15

16

17

18

19

20

N(k)

179

242

307

374

52

123

196

271

348

36

k

21

22

23

24

25

26

27

28

29

30

N(k)

117

200

285

372

70

161

254

349

55

154

k

31

32

33

34

35

36

37

38

39

30

N(k)

255

358

72

179

288

8

121

236

353

81

Пример. k=35, N(35)=288.



a

288

289

290

291

292

293

294

295

296

a560

mod 561


375

34

1

375

1

1

375

1

1

(a,561)

3

17

1

3

1

1

3

1

1




a

297

298

299

300

301

302

303

304

305

a560

mod 561


528

1

1

375

1

1

375

1

1

(a,561)

33

1

1

3

1

1

3

1

1

В указанном интервале имеется 11 лжесвидетелей Ферма простоты числа 561: 290, 292,293, 295,296,298,299, 301, 302, 304, и 305.



Задание 3. Тест Соловея-Штрассена. Определите свидетелей разложимости Эйлера и лжесвидетелей Эйлера простоты числа Кармайкла n=561, лежащих в интервале [N( k ), N( k )+17].

Пример. k=35, N(35)=288.



a

288

289

290

291

292

293

294

295

296

a280

mod 561


375

34

1

375

67

1

441

67

67



0

0

560

0

1

1

0

560

560




a

297

298

299

300

301

302

303

304

305

a280

mod 561


528

1

67

166

463

1

276

67

1



0

1

560

0

560

560

0

560

1

Как видим, в этом интервале имеется только 3 лжесвидетеля Эйлера простоты числа 561.


Задание 4. Тест Миллера-Рабина. Определите, есть ли сильные лжесвидетели простоты числа Кармайкла n=561, лежащие в интервале [N( k), N( k )+17].
Пример. k=35, N(35)=288. n-1=24 35. s=4, r=35

a

288

289

290

291

292

293

294

295

296

a35

mod 561


186

34

188

144

10

98

516

199

428

a70

mod 561


375

34

1

540

100

67

342

331

298

a140

mod 561


375

34

1

441

463

1

276

166

166

a280

mod 561


375

34

1

375

67

1

441

67

67




a

297

298

299

300

301

302

303

304

305

a35

mod 561


495

100

65

243

232

89

483

43

560

a70

mod 561


429

463

298

144

529

67

474

166

1

a140

mod 561


33

67

166

540

463

1

276

67

1

a280

mod 561


528

1

67

441

67

1

441

1

1

Как видим, все рассмотренные числа являются строгими свидетелями разложимости числа n=561. Обратите внимание, что наименьшим строгим свидетелем разложимости этого числа является число a=2: 235mod 561=300, 270mod 561=166, 2140mod 561=67, 2280mod 561=1.

Задание 4. Тест простоты чисел Мерсенна. Определите, есть ли простые числа Мерсенна среди чисел в интервале [(1[k(n)]5)10 , (1[k(n)]5) 10+4], где n  Ваш номер по журналу, k(n)] - Ваш ключ.

Пример. n=37, k(n)= k(37)= k(37)= (100011011010100101)Þ [(1[k(n)]5) 10 , (1[k(n)]5) 10+4]=[17,21].

Число 19  простое и M(19)= 524287 может быть простым. Составим отрезок рекуррентной последовательности u2=0, uk+1=( uk2-2) mod M(19) = ( uk2-2) mod 524287 для k=0,…, 17

k

0

1

2

3

4

5

6

7

8

9

uk

4

14

194

37634

218767

510066

386344

323156

218526

504140




k

10

11

12

13

14

15

16

17

uk

103469

417706

307417

382989

275842

85226

523263

0

Получили u15=0 mod M(19), значит, число Мерсенна M(19)= 524287- простое.

Задание 5 Порождение больших простых чисел. Пусть s есть простое число Мерсенна, найденное в предыдущем задании. Используя тест Нестеренко, найти простое число n=sr+1.

Пример. s= M(19)= 524287- простое. Выберем четное r в интервале [s, 4S+2]=[524287, 2097150]. Пусть r=2097100, проверим число

sr+1=1099482267701 вероятностным тестом простоты Миллера-Рабина. Число составное.

r=2097102, sr+1=1099483316275 – составное (делится на 5)

(при данном s не следует брать числа r, закачивающиеся двойкой).

R=2097090, SR+1=1099477024831 – составное.

R=2097000, SR+1=1099429839001 – составное.

R=2090000, SR+1=1095759830001 – составное.

R=2080000, SR+1=1090516960001 – составное.

R=524288, SR+1=274877382657 – составное.

R=524290, SR+1=274878431231 – составное.

R=524294, SR+1=274880528379 – составное.

R=524296, SR+1=274881576953 – составное.

R=524298, SR+1=274882625527 – составное.

R=524300, SR+1=274883674101 – составное.

R=524304, SR+1=274885771249 – составное.

R=524306, SR+1=274886819823 – составное.

R=524310, SR+1=274888916971 – составное.

R=524314, SR+1=274891014119 – составное.

R=524316, SR+1=274892062693 – составное.

R=524318, SR+1=274893111267 – составное.

R=524320, SR+1=274894159841 – составное.

R=524326, SR+1=274897305563– составное.

R=524328, SR+1=274898354137– составное.

R=524330, SR+1=274899402711– составное.

R=524334, SR+1=274901499859– составное.

R=524336, SR+1=274902548433– составное.

R=524338, SR+1=274903597007– составное.

R=524340, SR+1=274904645581– составное.

R=524344, SR+1=274906742729– составное.

R=524346, SR+1=274907791303– составное.

R=524348, SR+1=274908839877– составное.

R=524350, SR+1=274909888451– составное.

R=524354, SR+1=274911985599– составное.

R=524356, SR+1=274913034173– составное.

R=524358, SR+1=274914082747– составное.

R=524360, SR+1=274915131321– составное.

R=524364, SR+1=274917228469– составное.

R=524366, SR+1=274918277043– составное.

R=524368, SR+1=274919325617– составное.

R=524370, SR+1=274920374191– псевдопростое.

Теперь попытаемся доказать простоту найденного числа 274920374191.

Возьмем a=2.

2274920374190 mod 274920374191 =1.



(2524370–1 mod274920374191, 274920374191)=(81294380659, 274920374191)=1. Простота найденного числа 274920374191 доказана.
4. Защита лабораторной работы
Для защиты лабораторной работы следует представить отчет о лабораторной работе, соответствующий требованиям Методических указаний, продемонстрировать результаты вычислений и подтвердить знание теоретических оснований выполненной работы.


izumzum.ru