WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дискретний логарифм - Реферат

Дискретний логарифм - Реферат

xi-1, ci-1, di-1 та x2i-2, c2i-2, d2i-2 обчислити значення xi, ci, di та x2i, c2i, d2i використовуючи формули (1), (2), (3).
2.2. if (xi = x2i) then
r (di - d2i) mod n;
if (r = 0) then return (FALSE); // розв'язку не знайдено
x r -1 (ci - c2i) mod n.
return (x).
Якщо алгоритм завершується невдачею (повертає FALSE), то можна запустити його вибравши інші початкові значення c0, d0 з інтервалу [1; n - 1] та поклавши x0 = .
Приклад. Обчислити log29 в групі Z19*.
Побудуємо наступну таблицю значень послідовностей xi, ci, di:
i xi ai bi x2i a2i b2i
1 9 0 1 18 1 1
2 18 1 1 4 4 2
3 17 2 1 4 8 6
4 4 4 2 4 16 14
5 17 4 3 4 32 30
6 4 8 6 4 64 62
На 6 кроці отримали x6 = x12 . Підставивши їх значення, отримаємо:
28 * 96 = 264 * 962 або 28 - 64 = 962 - 6 , 2-56 = 956
Логарифмуємо рівність: -56 * log29 = 56 (mod 18), оскільки |Z19*| = 18.
Враховуючи що -56 (mod 18) 16, 56 (mod 18) 2, перепишемо рівність у вигляді 16 * log29 = 2 (mod 18) або 8 * log29 = 1 (mod 9). log29 = 8-1 (mod 9) = 8.
Відповідь: log29 = 8.
Індексний алгоритм
Алгоритм, базований на обчисленні індексів, є найпотужним при обчисленні дискретного логарифму. Необхідно побудувати відносно невелику підмножину S елементів групи G, яка називається множниковою основою. Ця підмножина повинна обиратисятаким чином, щоб як можна більша частина елементів G могла бути представлена у вигляді добутку її елементів. При обчисленні значення logab (a - генератор G, b G) спочатку обчислюються значення логарифмів елементів з S (які заносяться в тимчасову базу даних), а потім на їх основі обчислюється логарифм числа b.
Алгоритм
Вхід: генератор a циклічної групи G порядка n та елемент b G.
Вихід: дискретний логарифм x = logab.
1. Побудувати множину S - множникову основу. Нехай S = {p1, p2, …, pt}. В якості значень pi можна обрати, наприклад, i - те просте число.
2. Побудувати систему лінійних рівнянь, розв'язком якої будуть значення logapi. Для цього виконаємо наступні кроки:
2.1. Обрати деяке ціле k, 0 k n - 1 та обчислити ak .
2.2. Спробувати представити значення ak у вигляді добутку чисел з S:
ak = , ci 0
Якщо така рівність знайдена, то записати рівняння:
k = (mod n)
2.3. Повторювати кроки 2.1. та 2.2. поки не отримаємо t + c лінійних рівнянь. Невелике ціле число c (1 c 10) обирається таким чином, щоб складена система рівнянь мала єдиний розв'язок з великою ймовірністю (якщо скласти лише t рівнянь з t невідомими, то з великою ймовірністю два з цих рівнянь будуть залежними і тоді система буде мати більше одного розв'язку).
3. Розв'язати утворену систему рівнянь, отримати значення logapi, 1 i t.
4. Обчислення logab.
4.1. Обрати деяке ціле k, 0 k n - 1 та обчислити b * ak .
4.2. Спробувати представити значення b * ak у вигляді добутку чисел з S:
b * ak = , di 0
Якщо такого представлення знайти не вдається, виконати знову 4.1. Інакше прологарифмірувавши останню рівність, отримаємо:
x = logab = ( - k) mod n
Приклад. Обчислити log212 в групі Z19*.
1. Нехай S = {2, 3, 5} - множникова основа.
2. Будуємо систему рівнянь для знаходження значень log2pi, де pi S. Оскільки множина S містить 3 елементи, то достатньо отримати 3 лінійно незалежні рівняння.
k = 5: 25 (mod 19) 13 - не представимо у вигляді добутку чисел з S.
k = 7: 27 (mod 19) 14 - не представимо у вигляді добутку чисел з S.
k = 2: 22 (mod 19) 4 = 22. Перше рівняння: 2 = 2log22.
k = 10: 210 (mod 19) 17 - не представимо у вигляді добутку чисел з S.
k = 15: 215 (mod 19) 12 = 22 * 3. Друге рівняння: 15 = 2log22 + log23.
k = 11: 211 (mod 19) 15 = 3 * 5. Третє рівняння: 11 = log23 + log25.
3. Система рівнянь за модулем 18 (порядок Z19* дорівнює 18) має вигляд:
Її розв'язком буде:
log22 = 1, log23 = 13, log25 = 16
4. Обчислення log212.
k = 3: 12 * 23 (mod 19) 1 - не представимо у вигляді добутку чисел з S.
k = 7: 12 * 27 (mod 19) 16 = 24.
log212 + 7 4log22 (mod 18), log212 (4log22 - 7) (mod 18) = 15.
Відповідь: log212 = 15.
Алгоритм Поліга - Хелмана
Алгоритм Поліга - Хелмана ефективно розв'язує задачу дискретного логарифма в групі G порядка n, якщо число n має лише малі прості дільники.
Нехай g, h G, |G| = ps, p - просте. Тоді значення x = loggh можна подати у вигляді:
x = x0 + x1p + x2p2 + … + xs-1ps-1
Піднесемо рівняння h = gx до степеня ps-1:
= = =
* * * … * = ,
оскільки = 1 (g - генератор групи, ps - її порядок).
Таким чином з рівності = знаходимо x0.
Далі маючи значення x0, x1, …, xi-1 можна обчислити xi з рівняння
=
Приклад. Обчислити log37 в Z17*.
Необхідно розв'язати рівняння 3x = 7 в групі, порядок якої дорівнює 16 = 24.
Представимо x у двійковій системі числення: x = x0 + 2x1 + 4x2 + 8x3.
1. Обчислення x0.
Піднесемо рівняння 3x = 7 до степеня 23 = 8:
= 78, = -1,
* * * = -1.
Оскільки 316 (mod 17) 1, то останнє рівняння прийме вигляд = -1. Враховуючи що 38 (mod 17) -1, маємо: = -1, x0 = 1.
2. Обчислення x1.
Домножимо рівність = 7 на = 3-1 (mod 17) = 6, отримаємо:
= 7 * 6 або = 8.
Піднесемо рівняння до степеня 4: = 84, = -1, x1 = 1.
3. Обчислення x2.
1. D. Shanks. Class number, a theory of factorization and genera. In Proc. Symposium Pure Mathematics, vol.20, pp.415-440. American Mathematical Society, 1970.
Loading...

 
 

Цікаве