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

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

Диплом

Содержание Ответ: log517 ≡ 7 mod 23Вычислить дискретный логарифм методом Полига-Хеллмана

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

• Мозжевилов Максим Александрович Разработка модулей генерации заданий и решений по теме, 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.

X₁₄ = X₆

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

log₃14 ≡ (U[6] - U[14]) * (V[14] - V[6])^-1 mod 30

log₃14 ≡ (0 - 12) * (19 - 10)^-1 mod 30

log₃14 ≡ 18 * 9^-1 mod 30

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

Ответ:

log₃14 ≡ 6 mod 31


в) log₂5 mod 29.

Решение:

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

X₁₁ = X₆

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

log₂5 ≡ (U[6] - U[11]) * (V[11] - V[6])^-1 mod 28

log₂5 ≡ (2 - 10) * (10 - 4)^-1 mod 28

log₂5 ≡ 20 * 6^-1 mod 28

log₂5 ≡ 10 * 3^-1 mod 28

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

Возможные значения логарифма: 22, 36

Ответ:

log₂5 ≡ 22 mod 29


г) log₆27 mod 41.

Решение:

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13
X(i)	1	27	39	29	21	3	18	26	20	31	17	2	4	26
U(i)	0	0	1	2	4	5	6	7	14	28	28	16	32	32
V(i)	0	1	1	1	2	2	2	2	4	8	9	18	36	37
S	S1	S3	S3	S2	S3	S3	S3	S2	S2	S1	S2	S2	S1	S2

X₁₃ = X₇

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

log₆27 ≡ (U[7] - U[13]) * (V[13] - V[7])^-1 mod 40

log₆27 ≡ (7 - 32) * (37 - 2)^-1 mod 40

log₆27 ≡ 15 * 35^-1 mod 40

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

Ответ:

log₆27 ≡ 25 mod 41


д) log₅17 mod 23.

Решение:

I	0	1	2	3	4	5
X(i)	1	17	13	14	12	14
U(i)	0	0	0	0	0	1
V(i)	0	1	2	3	6	6
S	S1	S2	S1	S2	S3	S2

X₅ = X₃

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

log₅17 ≡ (U[3] - U[5]) * (V[5] - V[3])^-1 mod 22

log₅17 ≡ (0 - 1) * (6 - 3)^-1 mod 22

log₅17 ≡ 21 * 3^-1 mod 22

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

Ответ:

log₅17 ≡ 7 mod 23


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


а) log₃8 mod 127-1.

Решение:

n = p — 1 = 126 = 2¹ • 3² • 7¹;

q = 2; α = 1;

γ = 1; l₀ = 0;

g' = 3⁶³ mod 127 = 126;

j = 0 => γ = 1, a' = 8⁶³ mod 127 = 1 => l₀ = log₁₂₆1 mod 127 = 0;

x₀ = 0 • 2⁰ = 0;

q = 3; α = 2;

γ = 1; l₀ = 0;

g' = 3⁴² mod 127 = 107;

j = 0 => γ = 1, a' = 8⁴² mod 127 = 1 => l₀ = log₁₀₇1 mod 127 = 0;

j = 1 => γ = 1, a' = 8¹⁴ mod 127 = 1 => l₁ = log₁₀₇1 mod 127 = 0;

x₁ = 0 • 3⁰ + 0 • 3¹ = 0;

q = 7; α = 1;

γ = 1; l₀ = 0;

g' = 3¹⁸ mod 127 = 4;

j = 0 => γ = 1, a' = 8¹⁸ mod 127 = 32 => l₀ = log₄32 mod 127 = 6;

x₂ = 6 • 7⁰ = 6;

Составим систему:

x ≡ 0 (mod 2¹)

x ≡ 0 (mod 3²)

x ≡ 6 (mod 7¹)

Решая систему получим:

x ≡ 90(mod 126).

Проверка:

3⁹⁰ mod 127 = 8.

Ответ:

log₃8 mod 126 = 90.


б) log₃55 mod 137-1

Решение:

n = p — 1 = 136 = 2³ • 17¹;

q = 2; α = 3;

γ = 1; l₀ = 0;

g' = 3⁶⁸ mod 137 = 136;

j = 0 => γ = 1, a' = 55⁶⁸ mod 137 = 136 => l₀ = log₁₃₆136 mod 137 = 1;

j = 1 => γ = 3, a' = 55³⁴ mod 137 = 1 => l₁ = log₁₃₆1 mod 137 = 0;

j = 2 => γ = 3, a' = 55¹⁷ mod 137 = 136 => l₂ = log₁₃₆136 mod 137 = 1;

x₀ = 1 • 2⁰ + 0 • 2¹ + 1 • 2² = 5;

q = 17; α = 1;

γ = 1; l₀ = 0;

g' = 3⁸ mod 137 = 122;

j = 0 => γ = 1, a' = 55⁸ mod 137 = 119 => l₀ = log₁₂₂119 mod 137 = 10;

x₁ = 10 • 17⁰ = 10;

Составим систему:

x ≡ 5 (mod 2³)

x ≡ 10 (mod 17¹)

Решая систему получим:

x ≡ 61(mod 136).

Проверка:

3⁶¹ mod 137 = 55.

Ответ:

log₃55 mod 136 = 61.


в) log₅41 mod 307-1.

Решение:

n = p — 1 = 306 = 2¹ • 3² • 17¹;

q = 2; α = 1;

γ = 1; l₀ = 0;

g' = 5¹⁵³ mod 307 = 306;

j = 0 => γ = 1, a' = 41¹⁵³ mod 307 = 1 => l₀ = log₃₀₆1 mod 307 = 0;

x₀ = 0 • 2⁰ = 0;

q = 3; α = 2;

γ = 1; l₀ = 0;

g' = 5¹⁰² mod 307 = 289;

j = 0 => γ = 1, a' = 41¹⁰² mod 307 = 17 => l₀ = log₂₈₉17 mod 307 = 2;

j = 1 => γ = 25, a' = 41³⁴ mod 307 = 17 => l₁ = log₂₈₉17 mod 307 = 2;

x₁ = 2 • 3⁰ + 2 • 3¹ = 8;

q = 17; α = 1;

γ = 1; l₀ = 0;

g' = 5¹⁸ mod 307 = 81;

j = 0 => γ = 1, a' = 41¹⁸ mod 307 = 24 => l₀ = log₈₁24 mod 307 = 3;

x₂ = 3 • 17⁰ = 3;

Составим систему:

x ≡ 0 (mod 2¹)

x ≡ 8 (mod 3²)

x ≡ 3 (mod 17¹)

Решая систему получим:

x ≡ 224(mod 306).

Проверка:

5²²⁴ mod 307 = 41.

Ответ:

log₅41 mod 306 = 224.


г) log₅191 mod 193-1

Решение:

n = p — 1 = 192 = 2⁶ • 3¹;

q = 2; α = 6;

γ = 1; l₀ = 0;

g' = 5⁹⁶ mod 193 = 192;

j = 0 => γ = 1, a' = 191⁹⁶ mod 193 = 1 => l₀ = log₁₉₂1 mod 193 = 0;

j = 1 => γ = 1, a' = 191⁴⁸ mod 193 = 192 => l₁ = log₁₉₂192 mod 193 = 1;

j = 2 => γ = 25, a' = 191²⁴ mod 193 = 1 => l₂ = log₁₉₂1 mod 193 = 0;

j = 3 => γ = 25, a' = 191¹² mod 193 = 1 => l₃ = log₁₉₂1 mod 193 = 0;

j = 4 => γ = 25, a' = 191⁶ mod 193 = 1 => l₄ = log₁₉₂1 mod 193 = 0;

j = 5 => γ = 25, a' = 191³ mod 193 = 1 => l₅ = log₁₉₂1 mod 193 = 0;

x₀ = 0 • 2⁰ + 1 • 2¹ + 0 • 2² + 0 • 2³ + 0 • 2⁴ + 0 • 2⁵ = 2;

q = 3; α = 1;

γ = 1; l₀ = 0;

g' = 5⁶⁴ mod 193 = 84;

j = 0 => γ = 1, a' = 191⁶⁴ mod 193 = 84 => l₀ = log₈₄84 mod 193 = 1;

x₁ = 1 • 3⁰ = 1

Составим систему:

x ≡ 2 (mod 2⁶)

x ≡ 1 (mod 3¹)

Решая систему получим:

x ≡ 130(mod 192).

Проверка:

5¹³⁰ mod 193 = 191.

Ответ:

log₅191 mod 192 = 130.


д) log₂50 mod 419-1

Решение:

n = p — 1 = 418 = 2¹ • 11¹ • 19¹;

q = 2; α = 1;

γ = 1; l₀ = 0;

g' = 2²⁰⁹ mod 419 = 418;

j = 0 => γ = 1, a' = 50²⁰⁹ mod 419 = 418 => l₀ = log₄₁₈418 mod 419 = 1;

x₀ = 1 • 2⁰ = 1

q = 11; α = 1;

γ = 1; l₀ = 0;

g' = 2³⁸ mod 419 = 334;

j = 0 => γ = 1, a' = 50³⁸ mod 419 = 300 => l₀ = log₃₃₄300 mod 419 = 6;

x₁ = 6 • 11⁰ = 6

q = 19; α = 1;

γ = 1; l₀ = 0;

g' = 2²² mod 419 = 114;

j = 0 => γ = 1, a' = 50²² mod 419 = 215 => l₀ = log₁₁₄215 mod 419 = 13;

x₂ = 13 • 19⁰ = 13;

Составим систему:

x ≡ 1 (mod 2¹)

x ≡ 6 (mod 11¹)

x ≡ 13 (mod 19¹)

Решая систему получим:

x ≡ 127(mod 418).

Проверка:

2¹²⁷ mod 419 = 50.

Ответ:

log₂50 mod 418 = 127.