Modified Algorithm of Shanks with Ordered Blocks


Majority of cryptanalytic methods can be modified due to parallel algorithms. One of them is the method of Shanks solving discrete logarithms problem. The main goal of this article is to construct algorithm, which allows parallel calculating all values from low and high pitch tables, to make this search more directed and to put in order all values of table elements. It will allow applying method of blocks searching, separation on the ordered sub-blocks, accelerate applying method of value indexing (or value hash). Parallel optimization and block parallel radix sorting, which became possible due to fast broadcast in duplex mode and mathematical models of algorithm, are the method of solving this problem. Method of parallel vector calculation, using values from BS table as coordinates, was proposed in this work. Optimal lengths of fine pitch and, as a consequence, high pitch were found for the method, which doesn’t use complete order on the range of elements value of such low pitch. Method of improving Shanks algorithm was proposed.

Publication year: 
С. 46–52., укр., Бібліогр.: 12 назв.

1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с.
2. L. Adleman, “A subexponential algorithm for the discrete logarithm problem with applications to cryptography”, in Proc. 20th Ann. IEEE Symp. Found. Comput. Sci., 1979, pp. 55—60.
3. А. Stein and Teske E., “Optimized baby step-giant step methods”, J. Ramanujan Math. Soc., vol. 20, no. 1, 2005, pp. 1—32.
4. J.S. Coron et al., “A new baby — step gigant — step algorithm and some applications to cryptanalysis”, in Proc. 7th Int. Conf. Cryptographic hardware and embedded system. Springer-Verlag, 2005, pp. 47—60.
5. Основи дискретної математики / Ю.В. Капітонова, С.Л. Кривий, А.А. Летичевський та ін. — К.: Наук. думка, 2002. — 578 с.
6. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов. — М.: Изд-во ИНТУИТ.ру, 2007. — С. 231.
7. Handbook of Graph theory (Discrete Mathematics and its application), J.L. Gross and J. Yellen, Eds. Florida: CRS Press, 2004, 1192 p.
8. Цегелик Г.Г. Методы автоматической обработки информации. — Львов: Вища школа, 1981. — С. 132.
9. Задирака В.К. Олексюк О.А. Компьютерная арифметика многоразрядных чисел. — Тернополь: Підручники і посібники, 2003. — С. 247.
10. D.R. Stinson, “Some baby-step giant-step algorithm for low hamming weight discrete logarithm problem”, Math. Comp., vol. 71, pp. 379—391, 2002.
11. M.J. Wiener, “The Full Cost of Cryptanalytic Attacks”, J. Crypt., vol. 17, no. 2, pp. 105—124, 2004.
12. Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых. — К.: Політехніка, 2004. — 224 с.

2013-5-7.pdf264.81 KB

Тематичні розділи журналу