For the tiller, most anything would work, depends on how fancy you want it to be (carved, laminated), what color, grain, etc. Heck, you can make a perfectly good one from a pine 2 x 4. For the prod, unless you've already done several, or were going for a horn/wood/sinew composite, I'd recommend buying one ready made in steel. I started one in red oak, backed with linen, and it just never got not scary. I put it on the shelf and chalked it up to wood working practice.
Any particular time period or version of primitive you were thinking of?
Frode