Ideal Membership without Certificate?
This should really be a comment. But since I dont't have enough reputation I have to write it here.
If you only want to check ideal membership you "just" have to compute a Gröbner basis and check if all S-polynomials reduce to $0$. (the above mentioned computer algebra systems check ideal member ship in this way)
If you want to compute the $g_i$ you need to compute the syzygies. (I think this is just bookkeeping during the Gröbner basis computation)
Edit: I think the CAS Singular is able to compute the $g_i$ using the command "lift". https://www.singular.uni-kl.de/Manual/4-0-3/sing_513.htm
My recollection of the Gröbner engine of Macaulay 2 is that it's rather black-boxed. Surely others here know better than I how to access its parts directly.
The first step is to extend to a Gröbner basis $G$. But without reimplementing the Buchberger algorithm I don't know how to express the new generators in terms of the old.
Then, you can $\rm scan()$ through ${\rm flatten\ entries\ generators}\ G$, replacing p by p%G, and if they're different print out (G, (p-p%G)/G). Continue cycling through until $p=0$.