9, gives the familiar division rule you list for 3. But this is not too helpful, since it may only reduce our problem to p-1 digits. So I started to search for division rules that work as follows. Find a division rule with the smallest value of d, and for k values in the range -5 to 5. Now we can reverse the process.
Any smaller reductions produce more difficult multiplication needed.
If you have an 8-digit calculator, a rule that reduces things to 7 digits may be good enough. Note there is an interesting feature of these rules. Any rule generated may work for more than one number. For instance, take 59. The rule is take the last four digits and multiply by -2.