 Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Timeстатья Информация о цитировании статьи получена из Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 4 февраля 2014 г.
• Автор:
• Журнал: Lecture Notes in Computer Science
• Том: 7353
• Год издания: 2012
• Первая страница: 303
• Последняя страница: 312
• DOI: 10.1007/978-3-642-30642-6_28
• Аннотация: We show how to check in linear time if a function f : Z_k^n→Z_k, where k= p^m, p is a prime number, and m ≥2, specified by its values, can be represented by a polinomial in the ring Z_k [x_1,…,x_n]. If so, our algorithm constructs are also (in linear time) its canonical polynomial representation. We also show how to extend our techniques (with linear time) to the cases of an arbitrary composite number k. More precisely, we prove that the circuit-size complexity of solving the problem, if a given function f : Z_k^n→Z_k, where k is a fixed composite number, specified by its values, is represented by a polynomial in the ring Z_k[x_1,…,x_n], and, if so, finding its polynomial, is linear.
• Добавил в систему: Селезнева Светлана Николаевна

Работа с статьей

  Selezneva S. N. Constructing polynomials for functions over residue rings modulo a composite number in linear time // Lecture Notes in Computer Science. — 2012. — Vol. 7353. — P. 303–312. We show how to check in linear time if a function f : Z_k^n→Z_k, where k= p^m, p is a prime number, and m ≥2, specified by its values, can be represented by a polinomial in the ring Z_k [x_1,…,x_n]. If so, our algorithm constructs are also (in linear time) its canonical polynomial representation. We also show how to extend our techniques (with linear time) to the cases of an arbitrary composite number k. More precisely, we prove that the circuit-size complexity of solving the problem, if a given function f : Z_k^n→Z_k, where k is a fixed composite number, specified by its values, is represented by a polynomial in the ring Z_k[x_1,…,x_n], and, if so, finding its polynomial, is linear. [ DOI ]