Thread: How to decrease the value of resultant of two randomly generated polynomials?

1. How to decrease the value of resultant of two randomly generated polynomials?

Hi,

I have an algorithm, where I use the resultant of two randomly generated polynomials (of quite a high degree, say 1000) to perform operations. The coefficents of one of the polynomials can vary randomly. For example,

N=1000 (say)

F(x) = polynomial of degree N (with any random coefficients)

G(x) = polynomial of degree N (with coefficients between -2^(sqrt(N)) and 2^(sqrt(N))

p = resultant of F(x) and G(x)

I continue to generate random G(x) until I get a 'p' that is prime.

One of the major drawbacks of the algorithm is that the resultant is a VERY large number (say around 500 bit number). I want to reduce the value of the resultant as much as possible, without being able to guess/brute force the value of F(x) and G(x) from 'p'.

I feel we cannot tweak around too much with G(x) as the coefficients of G(x) is within a range. A way of doing this (atleast I thought it was a way ) is to reduce the size of F(x), i.e. keep most of the coefficients of F(x) as zero, and then the resultant (determinant of the sylvester matrix) will result in quite a small number as most of the numbers in the sylvester matrix is zero. But if I do this, then there is a possiblility that more than a unique F(x) can result with the same resultant 'p' with G(x). The aim is that the brute force must must be difficult, but still keeping the value of 'p' small.

Even If I'm able to achieve a 50 bit resultant for two 1000 degree polynomials, it's very good (when compared to the 500 bit previous resultant) as I'm reducing the size of the resultant by 90%.

So, my question is how do we tweak the two polynomials such that the resultant is a small number? Is there a relation/property in the sylvester matrix that we can use to achieve small resultants?

2. Ok, from the zero responses I guess there is no optimization possible :-/

3. Originally Posted by hrishi
Ok, from the zero responses I guess there is no optimization possible :-/
No, you conclude that no one on MHF has any ideas, may be don't even know what you are really asking.

CB

4. Oops, okay