Polynomial factorization calculator

Multiplication of polynomials modulo a prime number can be performed in the usual way by multiplying the different terms of the polynomial and then adding the coefficients of the same degree. Finally the coefficients are reduced modulo that prime.

For example, the product of 3x2 + 5x + 1 and 6x2 + 4x + 3 modulo 7 is 18x4 + (30+12)x3 + (9+20+6)x2 + (15+4)x + 3 modulo 7 which equals 4x4 + 5x + 3

It can be shown that the polynomials modulo a prime can be factored into the leading coefficient and monic prime polynomials in only one way (monic polynomials have the leading coefficient equal to one.)

It can also be shown that if there are no repeated factors, the polynomial can be factored modulo a power of that prime in only one way.

This JavaScript application can evaluate and factor polynomial expressions modulo a prime number or a power of a prime number.

Use the upper input box to enter the polynomial expression and the lower input box to enter a numerical expression for the modulus, which must be an integer number greater than 1 of the form prime number raised to an exponent. You can just evaluate the polynomial or evaluate and factor it, by pressing the corresponding button.

Example: copy any of the expressions below in the upper input box and type the number 211 (a prime number) in the lower input box. Then press the button "Factor expression".

  • 6x^8+x^5+3
  • 2*((x+6)*(x-5)+xx)^4+23x

The exponentiation symbol is not present in some mobile devices, so two asterisks ** can by typed as the exponentiation operator. So, equivalent expressions would be:

  • 6x**8+x**5+3
  • 2*((x+6)*(x-5)+xx)**4+23x

You can type a dot (.) and the application will replace it by "x^". This saves a lot of time in mobile devices because there is no need to switch between alphabetical and numerical keyboards for simple polynomials.

For the first example you would type:

  • 6.8+.5+3

Notice that factoring large degree polynomials will take a lot of time. That's why the applet accepts polynomials of degree up to 1000.

The superscripts checkbox can be used to see the exponents in the usual superscript notation (when the checkbox is checked) or preceded by the caret character (when it is unchecked). The first option is used to see the factorization on the display or print it. The second option is used to copy the data to another application.

After the applet finishes factoring, it multiplies the factors in order to validate if they are equal to the input polynomial.

You can also enter expressions that use the following operators and parentheses:

  • + for addition
  • - for subtraction
  • * for multiplication
  • / for division
  • % for remainder
  • ^ or ** for exponentiation

for the modulus you can use the above operators and also:

  • n!: factorial
  • p#: primorial (product of all primes less or equal than p).
  • B(n): Previous probable prime before n
  • F(n): Fibonacci number Fn
  • L(n): Lucas number Ln = Fn-1 + Fn+1
  • N(n): Next probable prime after n
  • P(n): Unrestricted Partition Number (number of decompositions of n into sums of integers without regard to order).
  • Gcd(m,n): Greatest common divisor of these two integers.
  • Modinv(m,n): inverse of m modulo n, only valid when gcd(m,n)=1.
  • Modpow(m,n,r): finds mn modulo r.

You can use the prefix 0x for hexadecimal numbers, for example 0x38 is equal to 56.

Source code

You can download the source of the current program and the old sum polynomial factorization applet from GitHub. Notice that the source code is in C language and you need the Emscripten environment in order to generate Javascript.

Written by Dario Alpern. Last updated 2 March 2019.

If you find any error or you have a comment, please fill in the form.