mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory > PARI/GP

Reply
 
Thread Tools
Old 2020-03-21, 03:25   #23
Andrew99
 
Aug 2019

11 Posts
Default

1. Is the polynomial constant a prime number?
-No
2. Is the lead coefficient a prime? [or monic]?
-monic
3.If not, are these coefficients special in some way?
-Don't understand this question
Please explain why you need/want to do this.
4. tell us what you want to do if there are no rational solutions.
- If the equation has no rational solution, we don't need the solution.
Andrew99 is offline   Reply With Quote
Old 2020-03-21, 03:30   #24
Andrew99
 
Aug 2019

11 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post

I wonder where the coefficients came from. Are they integers? Exact fractions? What?

The clause "a coefficient of this equation takes 1 megabyte space in a text file" is ambiguous. Does it only apply to one of the coefficients, or do theyall require that much space? Or is, perhaps, the polynomial monic?

Assuming the coefficients are integers, one could also ask what is actually known about them. Are they of some special form?

It comes from elliptic curve, they are either integers or fraction, there are 4 coefficients which has huge number, if you save them, each of them will take 1 MB in a text file, it is that simple, the polynomial is monic, thanks.
Andrew99 is offline   Reply With Quote
Old 2020-03-21, 04:16   #25
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1CFC16 Posts
Default

Quote:
Originally Posted by Andrew99 View Post
3.If not, are these coefficients special in some way?
-Don't understand this question
Please explain why you need/want to do this.
Rational roots thm. Is the constant (say) a perfect power so that it can be factored?
Is it a factorial?
R.D. Silverman is offline   Reply With Quote
Old 2020-03-21, 12:55   #26
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,251 Posts
Default

Quote:
Originally Posted by Andrew99 View Post
- If the equation has no rational solution, we don't need the solution.
You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as R. Gerbicz suggests. In Pari-GP you would have to set realprecision high enough to accommodate your integers first. This approach has the obvious merit that it is guaranteed to work. I will mention that the Pari function polroots() [at least, in my ancient version] returns all complex values, so you have to be a bit careful about distinguishing real from complex roots of the equation (real roots have a "small-as-possible" nonzero complex part).

If you have any a priori knowledge about how many pairs of complex-conjugate roots the equation has, use it. For example, if you know the equation always has only real roots, just take the real part of what polroots() gives you.

Another option is to try to reduce the polynomial (mod p) for small primes p which do not divide any of the denominators. If a mod p factorization does not have any linear factors, neither does the given polynomial, and you're done. Each such mod p reduction and factorization can be done fairly quickly, but, alas I can offer no guarantee this method will work for any really small primes p. It also is of no help in finding a rational root if one exists.
Dr Sardonicus is offline   Reply With Quote
Old 2020-03-21, 15:32   #27
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
You might want to multiply through by the LCM of the denominators to get all integer coefficients, then proceed as R. Gerbicz suggests.
Yes! If you can factor the resulting leading and constant terms, you'll be essentially done.

Quote:
Originally Posted by Dr Sardonicus View Post
I will mention that the Pari function polroots() [at least, in my ancient version] returns all complex values, so you have to be a bit careful about distinguishing real from complex roots of the equation (real roots have a "small-as-possible" nonzero complex part).
Newer versions also have polrootsreal() which return only those roots which are (exactly) real.

Quote:
Originally Posted by Dr Sardonicus View Post
Another option is to try to reduce the polynomial (mod p) for small primes p which do not divide any of the denominators. If a mod p factorization does not have any linear factors, neither does the given polynomial, and you're done. Each such mod p reduction and factorization can be done fairly quickly, but, alas I can offer no guarantee this method will work for any really small primes p. It also is of no help in finding a rational root if one exists.
Absolutely. You can use this method to rule out a rational root: if the polynomial mod p is irreducible, or is the product of two irreducible quadratics, then the original polynomial it does not have a rational root.
CRGreathouse is offline   Reply With Quote
Old 2020-03-21, 16:34   #28
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,251 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes! If you can factor the resulting leading and constant terms, you'll be essentially done.
No -- you don't have to factor them! Good thing, too, since we're talking about coefficients with possibly millions of decimal digits.

The method R. Gerbicz outlined for a poly with integer coefficients only requires computing real roots r to within 1/(2*a(n)) where a(n) is the lead coefficient, and then checking whether round(r*a(n))/a(n) is a root.

That's still potentially a lot of real precision, along with the large coefficients, but that should be no problem. Since we're only dealing with quartics, this approach seems quite practicable.
Dr Sardonicus is offline   Reply With Quote
Old 2020-03-21, 17:01   #29
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·7·53 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
No -- you don't have to factor them! Good thing, too, since we're talking about coefficients with possibly millions of decimal digits.

The method R. Gerbicz outlined for a poly with integer coefficients only requires computing real roots r to within 1/(2*a(n)) where a(n) is the lead coefficient, and then checking whether round(r*a(n))/a(n) is a root.

That's still potentially a lot of real precision, along with the large coefficients, but that should be no problem. Since we're only dealing with quartics, this approach seems quite practicable.
Very practical since the OP said the polynomial is monic. But there is something
that I don't understand. The OP seems to know at least some math since he/she is
playing with elliptic curves. However, it puzzles me why he/she would ask for
rational roots when he/she would know that the root is an integer........

It would be nice to know where the problem comes from.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-21, 17:19   #30
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,251 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Very practical since the OP said the polynomial is monic.
But there is something that I don't understand. The OP seems to know at least some math since he/she is playing with elliptic curves. However, it puzzles me why he/she would ask for rational roots when he/she would know that the root is an integer........
(my emphasis)
Quote:
Originally Posted by Andrew99 View Post
Quote:
Originally Posted by Dr Sardonicus View Post
<snip>
Assuming the coefficients are integers, one could also ask what is actually known about them. Are they of some special form?
It comes from elliptic curve, they are either integers or fraction, there are 4 coefficients which has huge number, if you save them, each of them will take 1 MB in a text file, it is that simple, the polynomial is monic, thanks.
So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.
Dr Sardonicus is offline   Reply With Quote
Old 2020-03-21, 17:23   #31
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·7·53 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
(my emphasis)

So it seems to me that, although the polynomial as given is monic, the coefficients might not be integers.
Ah. Of course.
R.D. Silverman is offline   Reply With Quote
Old 2020-03-21, 18:07   #32
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,251 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It would be nice to know where the problem comes from.
Indeed. With my very limited knowledge of elliptic curves, only one possibility occurs to me: If the quartic f(x) has a rational zero r, then (0, r) is a ready-made rational point on the curve

y2 = f(x)

which can be used to transform the curve into an elliptic curve

y^2 = F(x), F cubic.

If f(x) has no rational zero, there is no rational point (0, r) on the curve.

Of course if f(x) has no rational zeroes, it is still possible AFAIK that y2 = f(x) could have some rational point with y <> 0.

EDIT: Of course, with y <> 0 , there would be two rational points (y, r) and (-y, r) whereas with y = 0 you only get one ratonal point.

Last fiddled with by Dr Sardonicus on 2020-03-21 at 18:13 Reason: As indicated
Dr Sardonicus is offline   Reply With Quote
Old 2020-03-21, 19:36   #33
Andrew99
 
Aug 2019

138 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Rational roots thm. Is the constant (say) a perfect power so that it can be factored?
Is it a factorial?
We have no such information.
Andrew99 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
reduce number of coefficient for polynomial selection with msieve on GPU aein Factoring 3 2017-02-25 16:42
Don't fear the quartic fivemack Factoring 6 2011-12-12 05:08
Spearman's rank correlation coefficient Unregistered Homework Help 2 2009-03-03 19:56
Quartic: Parameters R.D. Silverman Factoring 9 2009-02-18 23:24

All times are UTC. The time now is 17:32.

Sat Jun 6 17:32:41 UTC 2020 up 73 days, 15:05, 1 user, load averages: 1.54, 2.17, 2.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.