3
$\begingroup$

I need to know what libraries (in C++) support polynomial arithmetic specially over a field. So I can give to it an array of coefficients of polynomial over a field and it returns the roots of polynomial over the field. It also should support big integers, as the coefficients and the roots are big integers.

For security reason my polynomial is defined over a finite field of prime order. So it's always possible to convert it to a polynomial whose leading coefficient is 1.

I have tried NTL, but it apparently does not support coefficients of type big integers!

Improve this question
$\endgroup$
6
  • $\begingroup$ possible duplicate of C++: How to find the roots of polynomial modulus N $\endgroup$
    – Christian Clason
    Commented Jul 13, 2015 at 13:38
  • $\begingroup$ Rather than post a new question, you should edit your other question to include the new information. $\endgroup$
    – Christian Clason
    Commented Jul 13, 2015 at 19:49
  • $\begingroup$ @ChristianClason: I marked the other question as a duplicate for the sake of expediency. I agree with your reasoning; this version seems to be clearer, and has better answers. $\endgroup$
    – Geoff Oxberry
    Commented Jul 13, 2015 at 20:41
  • $\begingroup$ @ChristianClason Thank you. When I started I had no idea. But eventually I'm getting more clues and options. However, I am not done yet :) $\endgroup$
    – user13676
    Commented Jul 13, 2015 at 21:03
  • $\begingroup$ @user13676 Yes, StackExchange works very differently from other sites -- that's why it works so well, and also why people who use it regularly are so invested to keep it working. I hope you'll stick around! $\endgroup$
    – Christian Clason
    Commented Jul 14, 2015 at 7:13

2 Answers 2

Reset to default
1
$\begingroup$

A package that can do what you want is Singular. It is written in C++ and it is my understanding that there is a library called libSingular that allows other programs to use its features (among them solving polynomial equations over finite fields and big integer arithmetic).

Another option that may fulfill your requirements is FLINT. It is written in C but I believe they have C++ wrappers for their functionality.

Improve this answer
$\endgroup$
1
$\begingroup$

Root finding of an arbitrary polynomial with degree $\gt 4$ over any field is supposed to be a trial and error process, as far as I know. If you are not dealing with any special type of polynomial, I can't see how any library is going to help you. Fast algorithms of finding roots for polynomial modulo p are there, for example here. You can also try Pari library written in C, which has implementations of this algorithm.

If you can factorize the polynomial into smaller polynomials of lower degrees so that you can search for roots trivially, you can use Chinese Remainder Theorem to combine the results and get roots for original polynomials.

If you have a special property of the polynomials you are using, you can exploit it. I will advise you to be a bit more specific about the problem you are dealing with, rather than posting same problem in different sites again and again.

I should have commented, but I don't have the necessary reputation yet. I'll try to update the answer as soon as I have a clear understanding of what you are dealing with. And please feel free to share your efforts so far in your post and comments. Thank you.

EDIT: You can also check out here for algorithms for finding roots of polynomials. There is always an option of using data structures provided by existing packages and mixing them as you see fit.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I do appreciate Sarker. At the moment I'm trying to use NTL, it seems to be working so far, with some "small" size "big integers". It requires that the polynomial to be monic and I can always provide that as I'm working over a field of prime order. I should mention that I have not tried with a high degree polynomial whose coefficients are so large but I'm planning to do that soon. Getting familiar with NTL takes a bit of time. $\endgroup$
    – user13676
    Commented Jul 13, 2015 at 19:51
  • $\begingroup$ Which are the degrees of the polynomial you are working with? Are they factorizable into polynomials(monic) of lower degree? If they are factorizable, you can find out the roots for each factor, and then use Chinese Reminder Theorem to find out roots of original polynomial. $\endgroup$
    – sarker306
    Commented Jul 13, 2015 at 19:58
  • $\begingroup$ It's not very clear what you mean by "Are they factorizable into polynomials(monic) of lower degree" . however it's a high degree polynomial (e.g. greater than 1000). $\endgroup$
    – user13676
    Commented Jul 13, 2015 at 20:01
  • $\begingroup$ I meant if you can factorize the polynomial expression. For example, you might not be able to factor it into $(x - a_{1})(x - a_{2})...(x-a_{m})$, because you would have easily found the roots... but if you could factor it into some other $P_{1}(x)P_{2}(x)...P_{m}(x)$, you could solve the following system of equations: $P_{i}(x) \equiv 0\ mod\ p$, for i <= m which would be easier to calculate, as they're of lower degree. $\endgroup$
    – sarker306
    Commented Jul 13, 2015 at 20:08
  • $\begingroup$ You can also try out Pari-GP, their core library is written in C++, and they have implementation of Cantor-Zassenhaus algorithm for finding roots of polynomial modulo p. See link $\endgroup$
    – sarker306
    Commented Jul 13, 2015 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.