1
$\begingroup$

I'm studying the Zippel algorithm for computing multivariate polynomial GCDs, which is probabilistic in the sense that it uses some random numbers, and assumes that if a polynomial coefficient is zero, then it is actually zero (as opposed to only zero at the randomly chosen values).

In [Zi79], the author makes the following claim:

Since the results for GCD and factorization can be checked by division, one is guaranteed to obtain the correct answer, if need be, by performing the calculation twice.

I can certainly see how we can check if a polynomial is a common divisor, but how can we be sure it is a greatest common division?

I just don't understand how "results for GCD... can be checked by division".

Can anybody help me?

[Zi79] Richard Zippel, PROBABILISTIC ALGORITHMS FOR SPARSE POLYNOMIALS, Laboratory for Computer Science, Massachusetts Institute of Technology

$\endgroup$

1 Answer 1

Reset to default
-1
$\begingroup$

If $d$ divides both $a$ and $b$, then $d=\gcd(a.b)$ iff $\gcd ({a\over d}, {b\over d})=1.$

$\endgroup$
1
  • 1
    $\begingroup$ That's true, but the logic is a little too circular for me. My problem is that I don't trust the gcd algorithm, because it's probabilistic, so I don't trust using it to test if the answer is correct! $\endgroup$
    – Brent Baccala
    May 9, 2021 at 5:41

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.