Майзаков Максим Александрович Разработка модулей автоматической генерации заданий с решениями по теме «Дискретное логарифмирование» диплом

Вид материала

Диплом

Содержание Приложение 3. Примеры генерируемых заданий.

Подобный материал:

• Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме, 891.19kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 7 7 7 7 7 7 7 7 56 диплом, 189.17kb.
• Дидин Максим Александрович Переславль-Залесский Гимназия 10 8 3 10 10 15 8 64 диплом, 103.28kb.
• Разработка урока по теме: «Развитие мышления через постановку проблемно творческих, 84.71kb.
• Отчет о выполеннии ниокр по теме Разработка унифицированных функциональных модулей, 219.08kb.
• Методы подготовки тестов по информатике и программированию, 55.02kb.
• Лоскутов Савва Александрович г. Асбест >26,5 диплом, 483.81kb.
• От двоичного кодирования к системам автоматической генерации кода, 2820.18kb.
• Тест №1 (из 6 заданий); Тест №2 (из 5 заданий); Тест №3 (в двух вариантах из 10 заданий);, 336.57kb.
• Название проекта, 6.03kb.

Приложение 3. Примеры генерируемых заданий.

Вычислить дискретный логарифм методом Шаг-младенца. Шаг-великана:


а) log₂2 mod 19-1.

Решение:

a = 2; p = 19; g = 2; m = 5;

U[0] = 2; V[0] = 1; b=g^m mod p = 2⁵ mod 19 = 13;

i,j	1	2	3	4	5
U[i]	4	8	16	13	7
V[j]	13	17	12	4	14

i = 1, j = 4; x=m*i-j mod (p-1) = 1;

Ответ:

log₂2 mod 18 = 1.



б) log₃69 mod 113-1.

Решение:

a = 69; p = 113; g = 3; m = 11;

U[0] = 69; V[0] = 1; b=g^m mod p = 3¹¹ mod 113 = 76;

i,j	1	2	3	4	5	6	7	8	9	10	11
U[i]	94	56	55	52	43	16	48	31	93	53	46
V[j]	76	13	84	56	75	50	71	85	19	88	21

i = 4, j = 2; x=m*i-j mod (p-1) = 42;

Ответ:

log₃69 mod 112 = 42.


в) log₆72 mod 229-1.

Решение:

a = 72; p = 229; g = 6; m = 16;

U[0] = 72; V[0] = 1; b=g^m mod p = 6¹⁶ mod 229 = 183;

i,j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
U[i]	203	73	209	109	196	31	186	200	55	101	148	201	61	137	135	123
V[j]	183	55	218	48	82	121	159	14	43	83	75	214	3	91	165	196

i = 2, j = 9; x=m*i-j mod (p-1) = 23;

Ответ:

log₆72 mod 228 = 23.


г) log₆22 mod 109-1

Решение:

a = 22; p = 109; g = 6; m = 11;

U[0] = 22; V[0] = 1; b=g^m mod p = 6¹¹ mod 109 = 39;

i,j	1	2	3	4	5	6	7	8	9	10	11
U[i]	23	29	65	63	51	88	92	7	42	34	95
V[j]	39	104	23	25	103	93	30	80	68	36	96

i = 3, j = 1; x=m*i-j mod (p-1) = 32;

Ответ:

log₆22mod108 = 32.


д) log₃46 mod 281-1

Решение:

a = 46; p = 281; g = 3; m = 17;

U[0] = 46; V[0] = 1; b=g^m mod p = 3¹⁷ mod 281 = 150;

i,j	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
U[i]	138	133	118	73	219	95	4	12	36	108	43	129	106	37	111	52	156
V[j]	150	20	190	119	147	132	130	111	71	253	15	2	19	40	99	238	13

i = 8, j = 15; x=m*i-j mod (p-1) = 121/

Ответ:

log₃46mod280 = 121

Вычислить дискретный логарифм Ро-методом Полларда:


а) log₃29 mod 31.

Решение:

I	0	1	2	3	4	5
X(i)	1	29	4	23	2	4
U(i)	0	0	0	0	0	0
V(i)	0	1	2	3	6	12
S	S1	S2	S1	S2	S2	S1

X₅ = X₂

Теперь вычисляем логарифм:

log₃29 ≡ (U[2] - U[5]) * (V[5] - V[2])^-1 mod 30

log₃29 ≡ (0 - 0) * (12 - 2)^-1 mod 30

log₃29 ≡ 0 * 10^-1 mod 30

log₃29 ≡ 0 * 1^-1 mod 30

Сравнение имеет 10 решений..

Возможные значения логарифма: 0, 3, 6, 9, 12, 15, 18, 21, 24, 27

Ответ:

log₃29 ≡ 9 mod 31


б) log₃14 mod 31.

Решение:

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
X(i)	1	14	10	16	7	5	25	9	27	19	18	23	2	4	25
U(i)	0	0	0	0	0	0	0	0	1	2	2	3	6	12	12
V(i)	0	1	2	3	4	5	10	11	11	11	12	12	24	18	19
S	S1	S2	S1	S1	S1	S2	S1	S3	S3	S1	S3	S2	S2	S1	S1