Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Related Publications
(16)
Parallel Solution of Toeplitz and ToeplitzLike Linear Systems Over Fields of Small Positive Characteristic1
Efficient computation of minimal polynomials in algebraic extensions of finite fields
Fast construction of irreducible polynomials over nite elds
Faster solution of the key equation for decoding BCH errorcorrecting codes
Some integer factorization algorithms using elliptic curves
Subscribe
Academic
Publications
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials,10.1137/0202007,Siam Journal on Computing,Michael S. Paterson,Larry J. St
Edit
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
(
Citations: 57
)
BibTex

RIS

RefWorks
Download
Michael S. Paterson
,
Larry J. Stockmeyer
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 2, no. 1, pp. 6066, 1973
DOI:
10.1137/0202007
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
link.aip.org
)
Citation Context
(24)
...The most expensive operation during encryption is evaluating the degree(n − 1) polynomial u at the point r. Polynomial evaluation using Horner’s rule takes n − 1 multiplications, but it is known that for small coefficients we can reduce the number of multiplications to only O( √ n), see [1,
10
]...
Craig Gentry
,
et al.
Implementing Gentry's FullyHomomorphic Encryption Scheme
...We can cite, for example, Knuth and Eve’s [10], [11] or Paterson and Stockmeyer’s [
12
] algorithms...
Christophe Mouilleron
,
et al.
Automatic Generation of Fast and Certified Code for Polynomial Evaluat...
...The values of xj do not need to be stored, so storage requirements are O(r) even if s r. Moreover, by use of rational preconditioning [
22
, 29] it is easy to evaluate (9.1) in (r + O(logr))s/2 multiplications...
Richard P. Brent
.
Some integer factorization algorithms using elliptic curves
...‐ we observe, following [
PaSt73
], that any polynomial of degree d can be computed from {x }∪ Z by a {+, −, ×}circuit using 2( √ d + 1) product gates;...
...Proposition 2. [
PaSt73
] Any degreed polynomial f (x) ∈ Z[x] can be computed by a {+, −, ×}circuit having at most 2 √ d +1 product gates...
Bernd Borchert
,
et al.
Few Product Gates But Many Zeros
...This class contains all schemes of practical interest, which include Horner’s method, evaluation by explicit powers, and the Paterson and Stockmeyer method [
16
] (all of which are described in [6, section 4.2]), as well as more ad hoc schemes such as those described below...
Awad H. AlMohy
,
et al.
Computing the Fréchet Derivative of the Matrix Exponential, with an Ap...
Sort by:
Citations
(57)
Implementing Gentry's FullyHomomorphic Encryption Scheme
(
Citations: 6
)
Craig Gentry
,
Shai Halevi
Conference:
Theory and Application of Cryptographic Techniques  EUROCRYPT
, pp. 129148, 2011
Multiscale fatigue crack observations on Ti–6Al–4V
Bernd Oberwinkler
,
Anton Lettner
,
Wilfried Eichlseder
Journal:
International Journal of Fatigue  INT J FATIGUE
, vol. 33, no. 5, pp. 710718, 2011
Efficient orthogonal matrix polynomial based method for computing matrix exponential
Jorge Sastre
,
J. Ibáñez
,
Emilio Defez
,
Pedro A. Ruiz
Journal:
Applied Mathematics and Computation  AMC
, vol. 217, no. 14, pp. 64516463, 2011
Automatic Generation of Fast and Certified Code for Polynomial Evaluation
Christophe Mouilleron
,
Guillaume Revy
Conference:
IEEE Symposium on Computer Arithmetic  ARITH
, pp. 233242, 2011
Some integer factorization algorithms using elliptic curves
(
Citations: 48
)
Richard P. Brent
Journal:
Computing Research Repository  CORR
, vol. abs/1004.3, 2010