"Your task is to make the largest number of the Great Discoveries and maximally to delay the doomsday."

Notice, that we are not only maximazing the period, but also the k^period. So we have to find strictly maximal "generator"/"primitive"/"первообразная"/"образующая".
There can be problem with understanding the way of minimizing these values. But as period it divisor of (mod - 1), and there are many generator, and they are quite uniformly distributed, probably k^(mod - 1) will always be better, than some p^((mod - 1) / q), where p > k.