На метод лупанова |
| Уравнения | ||
| << 8 Интегрирование иррациональных и тригонометрических выражений | Логарифмический мир >> |
Презентация: «На метод лупанова». Автор: ISS. Файл: «На метод лупанова.ppt». Размер zip-архива: 37 КБ.
На метод лупанова
содержание презентации «На метод лупанова.ppt»| № | Слайд | Текст |
| 1 |  |
Реализация арифметических операций в конечных полях схемамилогарифмической глубины Implementation of arithmetic in Finite Fields using logarithmic depth circuits |
| 2 |  |
GF(qn) Базисы BasesСтандартный (полиномиальный) базис Standard (polynomial) basis SB = { 1, ?, ?2, ?3, . . ., ?n-1 } Нормальный базис Normal basis NB = { ?, ?q, ?q2, ?q3, . . ., ?qn-1 } |
| 3 |  |
Преимущество стандартного базиса Standard basis benefit : быстроеумножение – fast multiplication Преимущество нормального базиса Normal basis benefit : быстрое возведение в степень qk (операция Фробениуса) – fast exponentiation to power qk (Frobenius operation) |
| 4 |  |
SB Умножение MultiplicationL = O(n log n log log n) D = O(log n) Sch?nhage, Stra?en 1971 Stra?en 1973 Sch?nhage 1977 |
| 5 |  |
SB Инвертирование и деление Inversion and divisionСтандартные методы Usual methods Метод аддитивных цепочек Addition chains’ method Brauer 1939 L = O(n1,67) D = O(log2 n) Расширенный алгоритм Евклида Extended Euclid algorithm Sch?nhage 1971 Moenk 1973 Brent, Gustavson, Yun 1980 Stra?en 1983 L = O(n log2 n log log n) D = O(n) |
| 6 |  |
SB Инвертирование и деление Inversion and divisionСпециальные методы Special methods Litow, Davida 1988 von zur Gathen 1990 L = nO(1) D = O(log n) |
| 7 |  |
SB Инвертирование и деление Inversion and divisionПредлагаемый метод Proposed method L = O(n1,67) D = O(log n) более точно more precisely : L = O(r n1/r(nw + n1,5 log n log log n)) D = O(r log n) r Є – параметр parameter w – экспонента умножения прямоугольных матриц типа rectangular matrix multiplication exponent of type (?n, ?n, n) ( w < 1,67 Huang, Pan 1998 ) N |
| 8 |  |
SB Инвертирование и деление Inversion and divisionПредлагаемый метод Proposed method L = O((nw + n1,5 log n log log n)r n1/r ) D = O(r log n) Для сравнения: в методе аддитивных цепочек Compare with additive chains’ method: L = O((nw + n log n log log n) log n) D = O(log2 n) |
| 9 |  |
NB Умножение MultiplicationСтандартный метод Usual method L = O(n3) L = ?(n2) D = O(log n) Massey, Omura 1986 |
| 10 |  |
Операция Фробениуса Frobenius operationNB : L = 0 Для сравнения Compare with : SB : L = O(n1,67) D = O(log n) Brent, Kung 1978 |
| 11 |  |
NB Умножение MultiplicationИдея Idea : NB ? SB ? X ? NB Kaltofen, Shoup 1998 А.А. Болотов, С.Б. Гашков (Bolotov, Gashkov) 2001 |
| 12 |  |
SB ? NBСтандартный метод General method L = O(n2/ logq n) D = O(log n) О.Б. Лупанов (Lupanov) 1956 Предлагаемый метод Proposed method L = O(n1,81) D = O(log n) (SB?NB : L = O(n1,81) Kaltofen, Shoup 1998) |
| 13 |  |
NBУмножение Multiplication Инвертирование Inversion Деление Division L = O(n1,81) D = O(log n) |
| 14 |  |
SBПроверка базисности нормальной системы Testing normal basis generator von zur Gathen, Giesbrecht 1990 von zur Gathen, Shoup 1992 L = O(n2 log3 n log2 log n) Основан на алгоритме Евклида Euclid-based method Предлагаемый метод Proposed method L = O(n1,81) D = O(log n) ( SB ? NB ? X ? SB ) |
| 15 |  |
SB, NB Инвертирование InversionТранзитивная сложность Transitive complexity : T(n) = L(SB?NB) D(SB?NB) = O(log n) Предлагаемый метод Proposed method L = O(r c n1+2/r + r n1/r T(n)) D = O(r log n) r Є – параметр parameter , r = o(log n / log log n) , c < 2,12 N |
| 16 |  |
GNB Инвертирование InversionГауссов нормальный базис k-го типа Gauss normal basis of type k ? = ? + ?d + … + ?dk-1 kn+1 Є , ? Є GF(qkn) , ?kn+1 = 1 , d Є GF(kn+1) , dk = 1 , # { dx } = k , <d, q >* = GF*(kn+1) T’(n) = O(k n) Предлагаемый метод Proposed method L = O(? -c n1+?) D = O(? -1 log n) k = o(log n) P |
| 17 |  |
Также использовались идеи из работ Also used ideas from Hstad, Leighton 1986 Eberly 1989 Reif, Tate 1990 |
| «На метод лупанова» | ||
