Let X and Y be a couple of integers such that 2n’-1•X•2n-1 and 0•Y•2L-1. A new algorithm which computes rapidly Y mod X is presented. When the algorithm is executed for the first time a constant K (depending on X and L) is computed. This K is saved for future recalls of the procedure with other Y’s smaller than 2L-1. The computation of K requires one division but in later jumps to the procedure only two multiplications, three right-shifts and at most three subtractions will be needed, provided that X remained unchanged. The following note presents the corresponding scheme.
