Как написать функцию расшифровки этого алгоритма?
А не факт что это вообще обратимо, так как при умножении на 31663 гарантированно произойдёт переполнение 16-разрядного целого, и старшие разряды будут потеряны.

Можешь попробовать так, конечно: создай массив всех возможных 16-разрядных чисел: 0, 1, 2, ..., 65535.
Затем каждый элемент этого массива зашифруй этим алгоритмом.
Если в полученном массиве какие-то элементы повторяются, то полностью обратить операцию невозможно - только частично, только для уникальных элементов в массиве. 
Если же все элементы массива уникальны, то можно обратить операцию, просто определив индекс входной пары байт в этом массиве. Этот индекс и будет исходным значением. Тут уже есть простор для оптимизации.
Нужно обратить все операции и делать их задом наперед.

Шифрование делает 34567890 итераций, вам надо сделать столько же. Внутри порядок операций надо развернуть, чтобы отмены выполнялись в обратном порядке. Если в строке 2 операции, например умножение и вычитание, то сначала надо выполнить обратное к вычитанию и только потом обратное к умножению.

Обратные к вычитанию и сложению - сложение и вычитание соответственно. Если шифрование прибавляет 12345, то вам надо 12345 вычитать в дешифраторе. Побитовое исключающее ИЛИ обратно само себе, ведь если его применить 2 раза, то получится исходное число.

С умножением все гораздо сложнее. Я предполагаю, что тип state - unsigned int. Если он знаковый, то умножение с переполнением - это undefined behavior вообще. В безнаковых целых умножение с переполнением есть просто умножение и взятие по модулую 2^32. Т.е вам нужно найти операцию, обратную умножению по модулю 2^32.

Это будет умножение на обратное по модулю.

Для его нахождения вам надо будет использовать расширенный алгоритм эвклида (в статье по ссылке выше оно расписано). Его можно или реализовать отдельно для нахождения обратных к 31663 (и другим множителям). Или можно его руками на бумажке прогнать. 

Отдельно вам надо разобратсья с отрицательным множителем. Вам надо найти положительный множитель, который будет давать точно такой же результат шифрования. Подсказка.

Edit, только заметил в вопросе, что state - двубайтовый. Значит, все происходит по модулю 2^16.