In this article we report on our experience in computing resultants of bivariate polynomials on Graphics Processing Units (GPU). Following the outline of Collins' modular approach [6], our algorithm starts by mapp...
详细信息
In this article we report on our experience in computing resultants of bivariate polynomials on Graphics Processing Units (GPU). Following the outline of Collins' modular approach [6], our algorithm starts by mapping the input polynomials to a finite field for sufficiently many primes m. Next, the GPU algorithm evaluates the polynomials at a number of fixed points x is an element of Z(m), and computes a set of univariate resultants for each modular image. Afterwards, the resultant is reconstructed using polynomial interpolation and Chinese remaindering. The GPU returns resultant coefficients in the form of Mixed Radix (MR) digits. Finally, large integer coefficients are recovered from the MR representation on the CPU. All computations performed by the algorithm (except for, partly, Chinese remaindering) are outsourced to the graphics processor thereby minimizing the amount of work to be done on the host machine. The main theoretical contribution of this work is the modification of Collins' modular algorithm using the methods of matrix algebra to make an efficient realization on the GPU feasible. According to the benchmarks, our algorithm outperforms a CPU-based resultant algorithm from 64-bit Maple 14 by a factor of 100. (C) 2012 Elsevier Inc. All rights reserved.
Let f (X, Y) is an element of Z[X, Y] be an irreducible polynomial over Q. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope off, or more precisely, off modulo some prime inte...
详细信息
Let f (X, Y) is an element of Z[X, Y] be an irreducible polynomial over Q. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope off, or more precisely, off modulo some prime integer p. The same idea of choosing a p satisfying some prescribed properties together with LLL is used to provide a new strategy for absolute factorization of f (X, Y). We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to construct the algebraic extension containing one absolute factor of a polynomial of degree up to 400. (C) 2010 Elsevier Ltd. All rights reserved.
作者：
Cipu, MihaiRomanian Acad
Simion Stoilow Inst Math Res Unit 5 POB 1-764 RO-014700 Bucharest Romania
The triples (x, y, z) = (1,z(z) - 1,z), (x, y, z) = (z(z) - 1,1,z), where z N, satisfy the equation x(y) + y(x) = z(z). In this paper it is shown that the same equation has no integer solution with min{x,y,z} > 1, ...
详细信息
The triples (x, y, z) = (1,z(z) - 1,z), (x, y, z) = (z(z) - 1,1,z), where z N, satisfy the equation x(y) + y(x) = z(z). In this paper it is shown that the same equation has no integer solution with min{x,y,z} > 1, thus a conjecture put forward by Z. Zhang, J. Luo, P. Z. Yuan (2013) is confirmed.
computations over the rational numbers often suffer from intermediate coefficient swell. One solution to this problem is to apply the given algorithm modulo a number of primes and then lift the modular results to the ...
详细信息
ISBN:
(纸本)9783319424323;9783319424316
computations over the rational numbers often suffer from intermediate coefficient swell. One solution to this problem is to apply the given algorithm modulo a number of primes and then lift the modular results to the rationals. This method is guaranteed to work if we use a sufficiently large set of good primes. In many applications, however, there is no efficient way of excluding bad primes. In this note, we describe a technique for rational reconstruction which will nevertheless return the correct result, provided the number of good primes in the selected set of primes is large enough. We give a number of illustrating examples which are implemented using the computer algebra system SINGULAR and the programming language JULIA. We discuss applications of our technique in computational algebraic geometry.
Injecting faults into an arithmetic device is a way of attacking cryptographic devices. The proof by 2(m-1) is a method to detect arithmetic errors induced by this attack without having to duplicate the computations. ...
详细信息
ISBN:
(纸本)038725658X
Injecting faults into an arithmetic device is a way of attacking cryptographic devices. The proof by 2(m-1) is a method to detect arithmetic errors induced by this attack without having to duplicate the computations. This method is simple and not too expensive, in terms of computation power when the arithmetic in software and in terms of both silicon surface and power consumption when the arithmetic operations are performed by a hard-wired operator. In that the proof by 2(m-1) is well-suited for martcards, in which these resources are limited. The proof by 2(m-1) is scalable, in that the designer can choose the parameter in, which determines the level of protection offered and the resources needed for the verification.
暂无评论