Results 1 to 4 of 4

Math Help - How to decrease the value of resultant of two randomly generated polynomials?

  1. #1
    Newbie hrishi's Avatar
    Joined
    Nov 2010
    From
    Bangalore, India
    Posts
    4

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie hrishi's Avatar
    Joined
    Nov 2010
    From
    Bangalore, India
    Posts
    4
    Ok, from the zero responses I guess there is no optimization possible :-/
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hrishi View Post
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie hrishi's Avatar
    Joined
    Nov 2010
    From
    Bangalore, India
    Posts
    4
    Oops, okay
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Randomly chosen family
    Posted in the Advanced Statistics Forum
    Replies: 13
    Last Post: October 12th 2011, 10:06 AM
  2. plotting a randomly generated weibull distribution values
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 1st 2011, 03:34 AM
  3. Probability of 6 randomly selected
    Posted in the Statistics Forum
    Replies: 4
    Last Post: July 19th 2010, 11:57 AM
  4. Probability with randomly generated numbers
    Posted in the Statistics Forum
    Replies: 8
    Last Post: June 9th 2010, 02:22 PM
  5. randomly picking balls
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 11th 2010, 05:36 AM

Search Tags


/mathhelpforum @mathhelpforum