# Factoring over prime fields

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...

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

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.