О реализации некоторых операций в конечных полях схемами логарифмической глубины

1.1 История вопроса.

Схема из функциональных элементов является, по существу, параллельной моделью вычислений — ее быстродействие определяется задержкой в цепочке между входом и выходом, а не суммарным временем выполнения всех элементарных операций, как в последовательной модели. В теоретических работах анализ задержки обычно заменяется анализом глубины, когда все элементы имеют единичную задержку и игнорируется задержка на участках цепей между элементами. Но даже в этих допущениях, как показал В. М. Храпченко [32], глубина (максимальное число элементов в цепочке схемы) может существенно отличаться от задержки в ее физическом смысле (минимальное время, исчисляемое в единичных задержках, необходимое для установления окончательного результата на выходах схемы).

Интерес к оптимизации глубины схем для выполнения арифметических операций рос по мере развития схемотехники и уже в 60-е годы отразился в классических работах [25, 14, 31] о реализации сложения и умножения чисел. В целом же, вопросы сложности всегда имели приоритет над вопросами глубины ввиду распространения последовательных моделей вычисления, какими, например, являются компьютерные программы (из теории можно в качестве примера привести одноленточные машины Тьюринга).

Сложность, хоть она явным образом и не влияет на быстродействие схемы, все же является важной характеристикой, определяющей площадь (объем) и, как следствие, потребляемую мощность, 1 которые в реальности накладывают серьезные ограничения на способ синтеза. Поэтому если такая постановка задачи, как оптимизация сложности без учета глубины, выглядит естественной (при использовании последовательной модели вычислений, для которой глубина безразлична), то при оптимизации по глубине практически обусловленной является сопутствующая оптимизация (или хотя бы анализ) сложности.

Теоретически оптимизация по глубине с учетом сложности рассматривается в двух основных постановках: (1) заданную арифметическую операцию реализовать схемой с возможно меньшим порядком глубины и наилучшим известным порядком сложности, либо (2) построить схему с возможно меньшим порядком сложности и наилучшим известным порядком глубины. Первой постановке следует, например, обзор [40, гл. 4], а второй — рабо.

1Хотя, как выяснил О. М. Касим-Заде, связь между сложностью и мощностью не настолько однозначна, см., например, [15]. та [64]. В ряде случаев наилучшие известные решения совпадают для обеих постановок (как, например, для умножения). Отметим, что для операции, которая реализуется схемой с логарифмическим (относительно числа входов) порядком глубины, вторая постановка может быть переформулирована более конкретно как минимизация сложности схемы с логарифмической глубиной.

В рамках последней постановки в настоящей работе рассматриваются арифметические операции в конечных полях: умножение, инвертирование, преобразование координат при переходе между нормальными и стандартными базисами и некоторые другие.

Теория конечных полей была заложена в работах Ферма, Эйлера, Ле-жандра, Гаусса, Галуа, Диксона и других выдающих ученых, и до последней четверти 20-го века развивалась как область чистой математики, но в связи с развитием криптографии, как отмечается в [5], к настоящему времени превратилась едва ли не в прикладной раздел. Сегодня вопросам эффективной реализации арифметики в конечных полях посвящено несколько специальных книг (в основном зарубежных, см. [5]).

Особенность вычислений в конечном поле состоит в необходимости выбора представления элементов — от него существенно зависит способ реализации (и, как следствие, сложность и глубина схемы). При работе с числами или многочленами этот вопрос как будто бы не стоит. Несмотря на то, что потенциально возможны (и описаны в теоретических работах) разные представления, практически используются два, стандартное и нормальное, а также производные от них.

Наиболее универсальным является стандартное представление — элементы поля в нем представляются многочленами, основные арифметические операции с которыми реализуются достаточно просто.

Умножение многочленов выполняется аналогами числовых методов, наиболее известные из которых были разработаны А. А. Карацубой [14], A. JL Тоомом [29] (уточнен Куком [48]), Шёнхаге и Штрассеном [84] в 60-е годы. На последнем методе достигаются одновременно наилучшие по порядку известные оценки глубины O (logn) и сложности О (п log п log log п), где п — разрядность сомножителей.2.

Иначе дело обстоит с делением (или инвертированием, т.к. деление сводится к инвертированию и умножению). Асимптотически быстрые алго.

2Недавно Фюрер [55] показал, что умножение чисел можно выполнять со сложностью n2°('og n' logn и глубиной 0(lognlog* п), где log*п определяется из соотношения log2. log2 nj = 1.

4-ч,-' log* П ритмы деления чисел3 основаны на методе Кука [48] и имеют такую же, но порядку сложность, как и умножение. Однако логарифмический порядок глубины на этих методах не достигается — наилучшая известная оценка глубины таких схем имеет вид O (lognloglogn) [79]. Для сложности схем с глубиной O (logn) известна оценка 0(п1+£) из работы [64].

Упомянутые методы деления переносятся на степенные ряды, но не при-ложимы прямо к делению в конечном поле (когда деление производится по модулю неприводимого многочлена, результат вычисляется точно). Быстрый способ деления (инвертирования) в конечном поле состоит в применении алгоритма Евклида — наилучшая известная для него оценка сложности, 0(п log2 п log log п), достигается в методе Кнута—Шёнхаге [81]. Для глубины соответствующей схемы можно указать оценку О (п). Схема сложности 0(nw logn), где w < 1,667 — экспонента умножения матриц размера у/п х у/п и у/Б х п, может быть построена методом аддитивных цепочек (приведенная оценка вытекает из работ [42, 44, 67]). Глубина в этом методе оценивается как 0(log2n).

Схемы логарифмической глубины для инвертирования в конечном поле впервые были построены в работах [73, 57] в конце 80-х годов. Сложность этих схем оценивалась авторами как, а глубина — как O (logn). Анализ показывает, что для сложности и глубины предложенных схем нельзя привести лучшие оценки, чем 0(п5) и 15Iog2n соответственно. Улучшение этого результата являлось стимулом для настоящей работы.

В нормальном представлении конечного поля можно быстро выполнять возведение в степень определенного вида, однако другие основные операции (прежде всего, умножение) в специально разработанной для нормальных базисов технике выполняются существенно сложнее, чем в стандартных базисах (речь идет об общем случае, поскольку на практике используются конкретные базисы, в которых необходимые операции реализуются эффективно). В последнее время (например, [70, 4]) была высказана идея о том, что для ускорения реализации многих операций в нормальном представлении, а также некоторых операций в стандартном, целесообразно (как с практической точки зрения, так и для получения теоретических оценок) использовать переходы между нормальными и стандартными базисами. Оценки вида 0{па), а < 2, для сложности перехода в общем случае, по-видимому, до сих пор не были известны. Получение таких оценок также являлось стимулом для данной работы.

З3адача деления двух чисел состоит в нахождении частного с некоторой точностью (обычно с той же, с которой заданы делимое и делитель).

1. Алексеев В. В., Сложность умножения матриц. // Кибернетический сборник. Вып. 25. — М.: Мир, 1988. — С. 189−236.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Проектирование и анализ вычислительных алгоритмов. — М.: Мир, 1979.

3. Берлекемп Э. Алгебраическая теория кодирования. — М.: Мир, 1971.

4. Болотов А. А., Гашков С. Б. О быстром умножении в нормальных базисах конечных полей. // Дискретная математика. — 2001. — Вып. 13, т. С. 3−31.

5. Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Элементарное введение в эллиптическую криптографию: алгебраические и алгоритмические основы. — М.: КомКнига, 2006.

6. Бурцев А. А., Гашков И. В., Гашков С. Б. О сложности булевых схем для арифметики в некоторых башнях конечных полей // Вестник МГУ. Серия 1. Математика. Механика. 2006. — № 5. — С. 10−16.

7. Гашков С. Б. Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли.// Дискретная математика. — 2000. — Вып. 12, № 3. С. 124−153.

8. Гашков С. Б. Замечание о минимизации глубины булевых схем. // Вестник МГУ. Серия 1. Математика. Механика. — 2007. — № 2.

9. Гашков С. Б., Гашков И. Б. О сложности вычисления дифференциалов и градиентов. // Дискретная математика. — 2005. — Вып. 17, № 3. — С. 45−67.

10. Гашков С. Б., Гринчук М. И., Сергеев И. С. О построении схем сумматоров малой глубины. // Дискретный анализ и исследование операций. Серия 1. 2007. — Том 14, № 1. — С. 27−44.

11. Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней. // Методы дискретного анализа в теории графов и сложности. — 1992. — Том 52. — С. 22−40.

12. Гашков С. Б., Сергеев И. С. О применении метода аддитивных цепочек к инвертированию в конечных полях. // Дискретная математика. — 2006. Вып. 18, т. — С. 56−72.

13. Гашков С. Б., Хохлов Р. А. О глубине логических схем для операций в полях GF (2n). // Чебышевский сборник. 2003. — Т. 4, вып. 4(8). -С. 59−71.

14. Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах. // Доклады АН СССР. 1962. — Т. 145(2). — С. 293−294.

15. Касим-Заде О. М. Об одной мере сложности схем из функциональных элементов. // Проблемы кибернетики. Вып. 38. — М.: Наука, 1981. — С. 117−179.

16. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. — М.: Вильяме, 2004.

17. Коблиц Н. Курс теории чисел и криптографии. — М.: ТВП, 2001.

18. Коновальцев И. В. Об одном алгоритме решения линейных уравнений в конечных полях. // Проблемы кибернетики. Вып. 19. — М.: Наука, 1967. С. 269−274.

19. Лидл Р., Нидеррайтер X. Конечные поля. — М.: Мир, 1988.

20. Ложкин С. А. О связи между глубиной и сложностью эквивалентных формул и о глубине монотонных функций алгебры логики. // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. — С. 269−271.

21. Лупанов О. Б. О вентильных и контактно-вентильных схемах. // Доклады АН СССР. 1956. — Т. 111(6). — С. 1171−1174.

22. Лупанов О. Б. О синтезе некоторых классов управляющих систем. // Проблемы кибернетики. Вып. 10. — М.: Физматлит, 1963. — С. 63−97.

23. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. М.: Изд-во МГУ, 1984.

24. Ноден П., Китте К. Алгебраическая алгоритмика. — М.: Мир, 1999.

25. Офман Ю. П. Алгоритмическая сложность дискретных функций. // Доклады АН СССР. 1962. — Т. 145(1). — С. 48−51.

26. Пан В. Я. О схемах вычисления произведений матриц и обратной матрицы. // Успехи мат. наук. 1972. — 27, № 5. — С. 249−250.

27. Серпинский В. 250 задач по элементарной теории чисел. — М.: Просвещение, 1968.

28. Столяров Г. К. Способ параллельного умножения в цифровых вычислительных машинах и устройство для осуществления способа. Авт. свид-во кл. 42 т 14, № 126 668, 1960.

29. Тоом A. JI. О сложности схемы из функциональных элементов, реализующей умножение целых чисел. // Доклады АН СССР. — 1963. — Т. 150(3). С. 496−498.

30. Хохлов Р. А. Реализация логическими схемами операций умножения и инвертирования в конечных полях характеристики два. — Канд. дисс., МГУ, 2005.

31. Храпченко В. М. Об асимптотической оценке времени сложения параллельного сумматора. // Проблемы кибернетики. Вып. 19. — М.: Наука, 1967. С. 107−120.

32. Храпченко В. М. Различие и сходство между задержкой и глубиной. // Проблемы кибернетики. Вып. 35. — М.: Наука, 1979. — С. 141−168.

33. Яблонский С. В.

Введение

в дискретную математику. — М.: Высшая школа, 2002.

34. Agnew G. В., Beth Т., Mullin R. С., Vanstone S. A. Arithmetic operations in GF (2m). // J. of Crypt. 1993. — V. 6. — P. 3−13.

35. Ash D., Blake I., Vanstone S. Low complexity normal bases. // Discrete Applied Math. 1989. — V. 25. — P. 191−210.

36. Eberly W. Very fast parallel polynomial arithmetic. // SIAM J. Comput. — 1989. V. 18, № 5. — P. 955−976.

37. Feisel S., von zur Gathen J., Shokrollahi M. A. Normal bases via general Gauss periods. // Math. Comput. 1999. — V. 68, № 225. — P. 271−290.

38. Fiduccia С. M. On the algebraic complexity of matrix multiplication. — Ph. D. thesis, Brown Univ., 1973.

39. Fiirer M. Faster integer multiplication. — 2007. — http://www.cse.psu.edu/~furer/Papers/mult.pdf.

40. Grove E. Proofs with potential. Ph.D. thesis, U.C. Berkeley, 1993.

41. Hastad J., Leighton T. Division in O (logn) depth using 0(n1+e) processors. — 1986. — http://www.nada.kth.se/~yohanh/paraldivision.ps.

42. Hoover H., Klawe M., Pippenger N. Bounding fan-out in logical networks. // J. ACM. 1984. — V. 31, M. — P. 13−18.

43. Hopcroft J. E., Kerr L. R. On minimizing the number of multiplications necessary for matrix multiplication. // SIAM J. Appl. Math. — 1971. — V. 20, M. P. 30−36.

44. Huang X., Pan V. Fast rectangular matrix multiplication and applications. // J. Complexity. 1998. — V. 14. — P. 257−299.

45. Itoh Т., Tsujii S. A fast algorithm for computing multiplicative inverses in GF (2n) using normal basis. // Inform, and Сотр. — 1988. — V. 78. — P. 171−177.

46. Jungnickel D. Finite fields: structure and arithmetics. — Mannheim: Wissenschaftsverlag, 1995.

47. Kaltofen E., Shoup V. Subquadratic-time factoring of polynomials over finite fields. // Math. Comput. 1998. — V. 67, № 223. — P. 1179−1197.

48. Kaltofen E., Singer M. Size efficient parallel algebraic circuits for partial derivatives. // IV ICCAPR Conf. (Singapore, 1991). P. 133−145.

49. Knuth D. The analysis of algorithms. // Proc. Intern. Congress of Math. (Nice, France). 1970. — V. 3. — P. 269−274.

50. Litow В., Davida G. O (logn) parallel time finite field inversion. // Proc. Aegean Workshop on Computing. Lecture Notes in Сотр. Sci. — 1988. — V. 319. P. 74−80.

51. Massey J. L., Omura J. K., Apparatus for finite fields computation. //US patent application. 1986. — № 4 587 627.

52. Moenk R. Fast algorithm of GCD’s. // Proc. 5th Ann. ACM Symp. on Theory of Computing. 1973. — P. 142−151.

53. Mullin R., Onyszchuk I., Vanstone S., Wilson R. Optimal normal bases in GF (pn). // Discrete Applied Math. 1988/89. — V. 22. — P. 149−161.

54. Pan V. Y. Complexity of parallel matrix computations. // Theor. Сотр. Sci. 1987. — V. 54. — P. 65−85.

55. Paterson M., Zwick U. Shallow circuits and concise formulae for multiple addition and multiplication. // Comput. Complexity. — 1993. — V. 3. — P. 262−291.

56. Reif J., Tate S. Optimal size integer division circuits. // SIAM J. Comput. 1990. — V. 19, № 5. — P. 912−925.

57. Rosser J., Schoenfeld L. Approximate formulas for some functions of prime numbers. // 111. J. Math. 1962. — V. 6 — P. 64−94.

58. Schdnhage A. Schnelle berechnung von kettenbruchentwicklungen. // Acta Inf. 1971. — V. 1. — P. 139−144.

59. Schonhage A. A lower bound for the length of addition chains. // Theor. Сотр. Sci. 1975. — V. 1. — P. 1−12.

60. Schonhage A. Schnelle multiplikation von polynomen iiber korpern der charakteristik 2. // Acta Inf. 1977. — V. 7. — P. 395−398.

61. Schonhage A., Strassen V. Schnelle multiplikation grofier zahlen. // Computing. — 1971. — V. 7. — P. 271−282. Русский перевод: Шёнхаге A., Штрассен В. Быстрое умножение больших чисел. // Кибернетический сборник. Вып. 10. М.: Мир, 1973. С. 87−98.].

62. Strassen V. Gaussian elimination is not optimal. // Numer. Math. — 1969. B. 13, № 4. — P. 354−356. Русский перевод: Штрассен Ф. Алгоритм Гаусса не оптимален. // Кибернетический сборник. Вып. 7. М.: Мир, 1971. С. 67−70.].

63. Strassen V. Die berechnungskomplexitat von elementarsymmetrischen funktionen und von interpolationskoeffizienten. // Numer. Math. — 1973. B. 20 — P. 238−251.

64. Strassen V. Vermeidung von divisionen. // J. reine u. angew. Math. — 1973. V. 264. — P. 182−202.

65. Strassen V. The computational complexity of continued fractions. // SIAM J. Comput. 1983. — V. 12. — P. 1−27.

66. Takagi N., Yoshiki J., Takagi K. A fast algorithm for multiplicative inversion in GF (2n) using normal basis. // IEEE Trans, on Сотр. — 2001. V. 50, № 5. — P. 394−398.

67. Yao A. C. On the evaluation of powers. // SIAM J. Comput. 1976. -V. 5. — P. 100−103.Работы автора по теме диссертации.

68. Сергеев И. С. Об инвертировании в конечных полях характеристики 2 с логарифмической глубиной. // Вестник МГУ. Серия 1. Математика. Механика. 2007. — № 1. — С. 28−33.

69. Сергеев И. С. О схемах логарифмической глубины для инвертирования в конечных полях характеристики два. // Математические вопросы кибернетики. Вып. 15. — М.: Физматлит, 2006. — С. 35−64.