Finding i Given F[i] for a Given Equation

[ged25]

I have the following equation

F = (F[i-1] * a) % b,
F[0] = 1;

Values of a and b are given. My question is whether it is possible to mathematically determine the value of i if you are given F.

 

[HallsofIvy]

Well first of all, we would have to know what that means! In some computer languages "a % b" is used to mean "the integer part of a divided by b". Is that what you mean?

It looks to me like there are going to be some values of n so that F<i>\ne n</i> for any i so if you mean "solve F= n", then in general there is no solution. Assuming that F is, in fact, some value of F, then you could use that recursive relation to keep calculating F[1], F[2], etc. until you finally get the given F.

 

[willem2]

the F must obviously repeat after at most b steps, since there are at most b values F can have.

This is a Linear congruential random number generator, and you can find lots about them.
The general equation for such a generator is F = (F[i-1] * a + c) % b.

If you have c = 0, you get F<i> \equiv F[0] a^i </i> (mod b)

If you want to calculate possible i's for an F, you'll need Eulers theorem:
If a and n are coprime then:

a^{\phi(n)} \equiv 1 (mod n)

\phi(n) is the totient function, the number of positive integers, less than n that are coprime to n.