Уравнения
<<  8 Интегрирование иррациональных и тригонометрических выражений Логарифмический мир  >>
Реализация арифметических операций в конечных полях схемами
Реализация арифметических операций в конечных полях схемами
GF(qn) Базисы Bases
GF(qn) Базисы Bases
Преимущество стандартного базиса Standard basis benefit : быстрое
Преимущество стандартного базиса Standard basis benefit : быстрое
SB Умножение Multiplication
SB Умножение Multiplication
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
SB Инвертирование и деление Inversion and division
NB Умножение Multiplication
NB Умножение Multiplication
Операция Фробениуса Frobenius operation
Операция Фробениуса Frobenius operation
NB Умножение Multiplication
NB Умножение Multiplication
SB ? NB
SB ? NB
NB
NB
SB
SB
SB, NB Инвертирование Inversion
SB, NB Инвертирование Inversion
GNB Инвертирование Inversion
GNB Инвертирование Inversion
Также использовались идеи из работ Also used ideas from H
Также использовались идеи из работ Also used ideas from H

Презентация: «На метод лупанова». Автор: ISS. Файл: «На метод лупанова.ppt». Размер zip-архива: 37 КБ.

На метод лупанова

содержание презентации «На метод лупанова.ppt»
СлайдТекст
1 Реализация арифметических операций в конечных полях схемами

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

логарифмической глубины

Implementation of arithmetic in Finite Fields using logarithmic depth circuits

2 GF(qn) Базисы Bases

GF(qn) Базисы Bases

Стандартный (полиномиальный) базис Standard (polynomial) basis SB = { 1, ?, ?2, ?3, . . ., ?n-1 } Нормальный базис Normal basis NB = { ?, ?q, ?q2, ?q3, . . ., ?qn-1 }

3 Преимущество стандартного базиса Standard basis benefit : быстрое

Преимущество стандартного базиса Standard basis benefit : быстрое

умножение – fast multiplication Преимущество нормального базиса Normal basis benefit : быстрое возведение в степень qk (операция Фробениуса) – fast exponentiation to power qk (Frobenius operation)

4 SB Умножение Multiplication

SB Умножение Multiplication

L = 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

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

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

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

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

NB Умножение Multiplication

Стандартный метод Usual method L = O(n3) L = ?(n2) D = O(log n) Massey, Omura 1986

10 Операция Фробениуса Frobenius operation

Операция Фробениуса Frobenius operation

NB : L = 0

Для сравнения Compare with : SB : L = O(n1,67) D = O(log n) Brent, Kung 1978

11 NB Умножение Multiplication

NB Умножение Multiplication

Идея Idea : NB ? SB ? X ? NB Kaltofen, Shoup 1998 А.А. Болотов, С.Б. Гашков (Bolotov, Gashkov) 2001

12 SB ? NB

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

NB

Умножение Multiplication Инвертирование Inversion Деление Division L = O(n1,81) D = O(log n)

14 SB

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

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

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 H

Также использовались идеи из работ Also used ideas from H

stad, Leighton 1986 Eberly 1989 Reif, Tate 1990

«На метод лупанова»
http://900igr.net/prezentacija/algebra/na-metod-lupanova-264470.html
cсылка на страницу

Уравнения

49 презентаций об уравнениях
Урок

Алгебра

35 тем
Слайды