1
$\begingroup$

Suppose I have two numbers in Fp that are multiplied together: r*s

Is there anything special that needs to be done when prime factorizing since this is a finite field (i.e., is this what is referred to as polynomial factorization?)

Example:

525 * 408 = 214200 = 357 (mod 599)

I'd like to be able to derive all of the prime factors: 2*2*2*3*3*5*5*7*17.

If I know r and s, then I would naively try to factor each one independently. But, is this method valid over Fp?

And what is the approach if I only know the result (357)?

Thanks in advance! This knowledge from my college days has long been replaced by other concepts over the years...

$\endgroup$
  • $\begingroup$ You cannot recover the prime factorization of your original number from the remainder $357$ and the modulus $599$. $\endgroup$ – André Nicolas Jan 3 '14 at 23:32
  • 1
    $\begingroup$ In the context of polynomial factorization, the number $357$ (or for that matter $214200$) would be considered to be already fully factored. $\endgroup$ – Erick Wong Jan 4 '14 at 0:45
2
$\begingroup$

As André Nicolas pointed out in his comment, even knowing both the result ($357$) and the modulus ($599$) is not sufficient to find the original factors or even just their prime factorization.

The main reason is that taking just the remainder in division (modulo) throws away quite a lot of information. For example, how would you determine if the original factors in your example were $3\times 7\times 17=357$ or $2\times 5^2\times 7\times 13=357+7\times 599$ or any of the many other possibilities?

In fact, since $\mathbb{F}_{599}$ is a finite field, it is possible, for any given $1\leq a<599$, to find number $1\leq b<599$ such that their product is equal to $357$ modulo $599$! The reason why (standard integer) prime numbers are a non-trivial concept is precisely because $\mathbb{Z}$, the ring of integers, is not a field.

The polynomial factorization over the finite field is an entirely different beast. In this case, we're looking at polynomials whose coefficients are from the finite field and trying to find out whether the polynomial can be written as a product of polynomials of smaller degree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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