jack

In that case I'd be inclined to think it's simplest just to pick one good fixed prime (my 65267 above is the largest safe prime less than 2^16), compute k as (p+N-2)/N (i.e. ceil rather than floor of the probable-non-integer (p-1)/N), and live with the small imbalance, which will be of the order of N/2^16, i.e. not noticeable.