On the minimum expected duration of a coin tossing game

The following coin tossing game is analyzed: a store of N fair coins is given and it is desired to achieve M heads in a round of tosses of the coins. To allow for unfavorable sequences of tails, restarts are permitted at any epoch in the game where, in any restart, all coins are returned to store and tosses are begun anew from tabula rasa. A restart strategy is a prescription that specifies when a restart should be made. It is desired to estimate the minimum expected duration of the game over all restart strategies, and to find an optimal strategy that minimizes the expected duration of the game. This simple coin tossing game, proposed by R.L. Rivest, has cryptographic roots and is linked to issues in the factoring of integers