Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
verfasst von : Svetlana N. Selezneva
Erschienen in: Computer Science – Theory and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show how to check in linear time if a function
$f:{\mathbb Z}_k^n \to{\mathbb 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 ℤ
k
[
x
1
, …,
x
n
]. If so, our algorithm also constructs (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:{\mathbb Z}_k^n \to{\mathbb Z}_k$
, where
k
is a fixed composite number, specified by its values, is represented by a polynomial in the ring ℤ
k
[
x
1
, …,
x
n
] and, if so, finding its polynomial, is linear.