The computation
t = (d*(t - txt[i]*h) + txt[i+M])%q;
can overflow. The maximal value of txt[i]
is d-1
, and h
can be as large as q-1
. So if (q-1)*(d-1)*d > INT_MAX
, there is the possibility of integer overflow. That limits the size of the prime that can be safely chosen to INT_MAX/(d*(d-1)) + 1
.
If q
is larger than that, that poses restrictions on the admissible values for M
, namely M
must be such that
h <= INT_MAX/(d*(d-1))
to safely prevent overflow.
With q = 683303
and M = 80
, you get h = 182084
, and
h*d*(d-1) = 182084 * 256 * 255 = 11886443520
is larger than INT_MAX
if int
is 32 bits wide as it usually is.
If your int
s are 32 bits wide, you have overflow for the example from the beginning, because h*256*97 = 4521509888 > 2147483647
.