_>Не понятно как можно реализовать phi(D) в программе.
_>Т.е. считаем если D > 1000, значит будут значения n при которых полином выдаёт дробный результат
_>Если D < 1000, значит подставляем n от (0 до D-1) в полином и анализируем получился ли на этом диапазоне дробный результат
_>??

это я не в ту степь.
про phi это просто гипотеза была о том как примерно устроены такие многочлены. не обращайте внимания.

Помоему для вашей задачи чисто практически достаточно уже приведённого решения =
проверить F в точках [0.. min(K, D-1)] по модулю D.

Если хочется поразнообразней, то можно факторизовать D чтоб получить разложение в простые, но это уже само по себе может быть достаточно громоздким.
И тогда тут уже можно воспользоваться простой проверкой коэффициентов многочлена для каждого простого числа из разложения.
При этом для степеней простых в разложении мне так и непонятна хорошая формула. так что для них всё равно вычислять F в диапазоне придётся.