Rossiya Federatsiyasi Ta'lim va fan vazirligi Oliy kasbiy ta'lim davlat ta'lim muassasasi

- 1 gjma(gim)

( ) E'tibor bering , i va j raqamlari topiladi, chunki = 0, m - 1, j = 1, K, jm - = 1, Km va Km > p. Ya'ni jm - i ko'rinishidagi barcha sonlar orasida 0 < x p shartli ravishda o'z ichiga oladi.
Eslatma: Bu usuldan n tartibli istalgan siklik guruhdagi diskret logarifmlarni topish mumkin.
1; yechimning quyidagi bosqichlarini qisqacha tavsiflash mumkin:
va ∈ G ning hosil qiluvchi elementi.
l-bosqich. m = va b = q ^{t ni hisoblang}
2-bosqich. U = b%vj = adj ketma-ketliklarini hisoblang, bu erda i,j = 1, ya'ni.
3-qadam. i,j ni toping , ui = vj,x = (mi -j)mod p
X natijani olamiz
Eng katta murakkablik shunday i, y NIMA ni izlashdir
Ro'yxatga olishning bir nechta alternativalari mavjud:

1. 
   P( ) jadvalning tuzilishi (i, u), ikkinchi komponent bo‘yicha saralanishi va vj komponentlari sifatida keyingi taqqoslash topiladi.
   
2. 
   Ikkita (i, u) va (j, vj) jadvallarini qurish, ularning har birini saralash va mosliklarni qidirish.
   
3. 
   va, v ni bir jadvalga birlashtirish (tartib raqamlari va ikkita ketma-ketlikning biriga tegishli bit bilan), qo'shma saralashni amalga oshirish.
   

Bu algoritmning ketma-ketligi modulli ko'paytirish va 0(n log n) taqqoslash amallaridir.
Keling, algoritm qanday ishlashini misol qilib olaylik.
n=229 (tut son), q=b, a=12 bo‘lsin.

^P qachon m=16 va b= y ^{a modn} =6 ¹² mod 229 183

Elementlarni qidirishning birinchi usulini tanlab , 1-jadvalni tuzamiz, so'ngra moslik topilmaguncha vj komponentlarini hisoblaymiz.

		2	3	to'rtta	5	6	7	sakkiz	9		o'n bir	12	13	o'n to'rt	o'n besh	16
	183	55	218	48	82	121	159	o'n to'rt	43	83	75	214	h	91	16	196
	72	203	73	209	109	196

G1 olish = 16, j = 6. x = mi-j modn = 250 mod 228 = 22
Buyurtmani hisoblash algoritmi. Diskret logarifmlarni hisoblash uchun yaqinda mashhur bo'lgan yana bir algoritm "Buyurtma hisobi algoritmi" dir.
y = a ^x mod p bo'lsin
Agar u faqat p dan kichik yoki unga teng tub omillarga ajralsa, u p-silliq deb nomlanadi.
Yechim bosqichlari:
Birinchi t tub sonlardan tashkil topgan S = {R1, R2, ... , pt} tayanch omillar to‘plamini hosil qilamiz .
2-bosqich. Biz t + (E - kichik butun son) - silliq sonlar a ^k mod p ni topamiz, K bo'lganda - S to'plam elementlariga bo'lish orqali silliqlikni tekshirish. Olingan pt - silliq sonlarning har biri ko'paytmasi sifatida yoziladi. shakldagi tayanch omillar
va ^modp = , 0,
( K ning har bir qiymati uchun biz q raqamlar to'plamini olamiz)
3-bosqich. 2-bosqich tenglamasida biz logarifmlarga o'tamiz

har biri uchun silliq raqam.
Shunday qilib, t noma'lumli K = Et=1 Ci logaPi ko'rinishdagi t + E tenglamalar tizimini olamiz. Noma'lumlar logapj qiymatlari.
4-bosqich. Biz chiziqli algebra usullari yordamida tizimni yechamiz (barcha hisob-kitoblar moduli p - 1) va S to'plamidan raqamlarning logarifmlari qiymatlarini olamiz: logap1, logap2, logap•
5-bosqich. Biz istalgan m ni tanlaymiz va pt - silliq sonni (y • a ^r ) topamiz:
y • a ^t modp = Pe 1 re, ei 2 0.
6-bosqich. Logarifmlarni olib, yakuniy natijaga erishamiz
x = logay = (Ef=1 masalan, logaPi - m) mod (p - 1).