12-Мавзу: Дискрет логорифмлаш усуллари Криптология кафедраси

12-Мавзу: Дискрет логорифмлаш усуллари

Криптология кафедраси

кат.ўқит., Мардиев У.Р.

Дискрет Логорифмлаш муаммосини ечиш алгортмлари

• Function field sieve
• Index calculus algorithm
• Number field sieve
• Pohlig-Hellman algorithm
• Pollard’s rho algorithm for logarithms
• Pollard’s kangaroo algorithm
• Quantum Algorithm by Peter Shor

Полиг-Хэлман алгоритми (Pohlig-Hellman)

Эйлер теоремаси:

• Агар, ўзаро туб сонлар бўлса у ҳолда бўлади, бу ерда – Эйлер функцияси.

тенг бўлсин, . ни ечиш учун Полиг-Хелман алгоритми қуйидаги ёндашувга асосланади. тенг бўлсин.

• Бундан
• ва топулгунча, ни танлаш йўли билан топамиз ва топулгунча, кейин
• Худди шу йўл оқали ни ҳам топамиз. Шундан сўнг қолдиқлар ҳақидаги Хитой теоремасидан фойдаланиб ни топамиз.

•  

Полиг-Хэлман алгоритми (Pohlig-Hellman)

Мисол

• ни топиш талаб этилсин.
• Дастлаб Эйлер функциясини ҳисоблаймиз, қайсики факторлари 30=5*6 тенг бўлган.
• Дейлик бўлсин, бундан:

келиб чиқади, ни қийматини танлаш йўли орқали топамиз, бунда

, тенгликдан келиб чиқади.

•  

Полиг-Хэлман алгоритми (Pohlig-Hellman)

Кейинги сон учун:

• бўлсин, бундан:

келиб чиқади, яна танлаш йўли орқали ни қийматини топамиз, бунда

, тенгликдан келиб чиқади.

• Демак

Қолдиқлар ҳақидаги Хитой теоремасидан келиб чиқади.

•  

Полиг-Хэлман алгоритми (Pohlig-Hellman)

топинг?

•  

Асосий ва қўшимча адабиётлар учун тавсиялар

• Асосий адабиётлар
• Christof Paar·Jan Pelzl. Understanding Cryptography: A Textbook for Students and Practitioners. Verlag Berlin Heidelberg 2010.
• Keith M. Martin. Everyday Cryptography Fundamental Principles and Applications. United Kingdom, 2017
• Қўшимча адабиётлар
• Акбаров Д. Е. “Ахборот хавфсизлигини таъминлашнинг криптографик усуллари ва уларнинг қўлланилиши” – Тошкент, 2008 – 394 бет.
• Stamp Mark. Information security: principles and practice. USA, 2011.

Саволлар???