How to fix a rocking toilet?
Judging by the photo the toilet is bolted to the floor with two bolts, one on each side of the toilet. That is what holds the toilet in place not some caulk or material. If the floor is just slightly off, ( not flat ) then toilet wedges will help to keep it from rocking. 



Photo source from the Lowe's link. You can find them online or at other home improvement stores. 

The wedges ( one or two ) are installed on one side, rock the toilet to see how it rocking then place the wedges in the void when the toilet is rocked all the way forward. I like to put them on the side less visible. Once you determine where they need to go loosen the bolts just slightly and snug the wedges in place and then tighten down the bolts so that the wedges are pinch in place. ( you can put a dab of caulk on them before you slip them in.)

Once the the bolts are tightened down you trim off the part of the wedge that sticking out and caulk around the base of the toilet. 

If the unevenness of the  floor is significant then you need to remove the toilet and take steps to level the floor. I do not know what the floor is made of so i can advise on that.