|
Математические заметки, 1987, том 42, выпуск 6, страницы 886–894
(Mi mzm5053)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Быстрое параллельное вычисление степеней в факторкольце многочленов над конечным полем
П. Н. Голованов, В. И. Солодовников
Аннотация:
Показывается, что вычисление степеней в фактор-кольце многочленов от одной переменной над конечным полем сводится к умножению матриц над этим полем, и на основе этого доказывается следующая оценка сложности: если $F=GF(q)$, $\omega(F)$ – показатель матричного умножения
над $F$, $\alpha>\omega(F)$, $f\in F[x]$, $\deg f=n$, то возведение в $m$-ю степень в кольце $F[x]/f$ возможно с временной сложностью
$$
O((\log_2(qn\log_qm))\log_2n)
$$
на
$$
O\biggl(\frac{\max(q,\sqrt{\log_qmn^{\alpha-2}},\log_qm)}{\log_2(qn\log_qm)}\frac{n^2}{\log_2n}\biggr)
$$
процессорах. Библиогр. 11 назв.
Поступило: 24.06.1986
Образец цитирования:
П. Н. Голованов, В. И. Солодовников, “Быстрое параллельное вычисление степеней в факторкольце многочленов над конечным полем”, Матем. заметки, 42:6 (1987), 886–894; Math. Notes, 42:6 (1987), 987–992
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm5053 https://www.mathnet.ru/rus/mzm/v42/i6/p886
|
Статистика просмотров: |
Страница аннотации: | 369 | PDF полного текста: | 130 | Первая страница: | 1 |
|