Zobrazeno 1 - 7
of 7
pro vyhledávání: '"Cray, Armelle Perret du"'
Publikováno v:
ISSAC '24: Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, pp. 437--446
We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing
Externí odkaz:
http://arxiv.org/abs/2402.10139
Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate the total running time. We propose a new variant of the classic D5 alg
Externí odkaz:
http://arxiv.org/abs/2202.12073
Given a way to evaluate an unknown polynomial with integer coefficients, we present new algorithms to recover its nonzero coefficients and corresponding exponents. As an application, we adapt this interpolation algorithm to the problem of computing t
Externí odkaz:
http://arxiv.org/abs/2202.08106
We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The
Externí odkaz:
http://arxiv.org/abs/2202.05955
Publikováno v:
Proceedings of ISSAC 2021
No polynomial-time algorithm is known to test whether a sparse polynomial G divides another sparse polynomial $F$. While computing the quotient Q=F quo G can be done in polynomial time with respect to the sparsities of F, G and Q, this is not yet suf
Externí odkaz:
http://arxiv.org/abs/2102.04826
Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for
Externí odkaz:
http://arxiv.org/abs/2101.02142
Publikováno v:
Proc. ISSAC'20, pp 202-209, ACM, 2020
We present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of character
Externí odkaz:
http://arxiv.org/abs/2001.11959