Another boring modular arithmetic question

[Avocado]

Thanks Wyman,
To be honest I was looking for a magical way to know the answer just looking at b and m [img]/images/graemlins/smile.gif[/img], but it seems that it's impossible.
I did know about the repetitions, but even with this "shortcut", the computation takes too much time for big numbers (specially primes).

Thanks again, I'll see what I can do.

[thylacine]

[ QUOTE ]
Thanks Wyman,
To be honest I was looking for a magical way to know the answer just looking at b and m [img]/images/graemlins/smile.gif[/img], but it seems that it's impossible.
I did know about the repetitions, but even with this "shortcut", the computation takes too much time for big numbers (specially primes).

Thanks again, I'll see what I can do.

[/ QUOTE ]

Do you have a factorization of m and \phi(m) ?

Do you know why I asked this ?

Anyway, Wyman's 1st half sentence gets to the point, assuming b is a unit in Z_m .

[bigpooch]

If either b or m is a prime, it may not take THAT much
time on a computer as long as one is efficient about it. If
either b or m is a prime, a key piece of information is the
prime factorization of phi(m). You know that b^k=1 for some
k<=phi(m) from Euler's theorem and the least such k gives
the number of different values of b^n (which is the "order"
of b (mod m)). For example, if m=100, phi(m)=phi(4)*phi(25)
=2*20=40 and so if b is coprime to m (b is not divisible by
either 2 or 5), b must have an order (mod 100) that is a
divisor of 40. Thus, you first need to check for
"exponents" 40/2 and 40/5:

Calculate b^20, b^8 to see if either is 1 (mod 100).

If not, b has order 40. But if b^20 or b^8 is 1 (mod 100),
you make further checks for smaller exponents. Usually, you
have information where it is redundant to make certain
calculations: e.g., if b^20=1 (mod m) but b^8<>1 (mod m),
although 20/5=4 is an exponent you might check, it's
unnecessary since if the order of b were 4 (mod m), b^8=1
(mod m), so you only need to check the exponent 20/2=10 and
then, if necessary, the exponent 5.

In fact, for m=100, since phi(m)=40=(2^3)*(5^1), you only
need to check for (3+1)(1+1)=4x2=8 exponents (actually, this
includes the check to see if b=1 (mod m)) but of course, you
want to execute this check efficiently.

Also, when evluating b^n (mod m), it is useful to simply
have a squaring function (mod m). You store the result for
b (mod m) (all your results can be an integer in (-m/2,m/2]
or [0,m-1] if you prefer). Once you have b^2 (mod m), you
store that result and continue to make the calculations for
(b^2)^2=b^4 (mod m), (b^4)^2=b^8 (mod m), but you don't
need any exponent 2^j>=phi(m) because if x and y are
congruent mod (phi(m)), then b^x = b^y (mod m) [the only
requirement is that b and m are coprime].

Having these values makes it much easier to compute b^n for
arbitrary n in the future since if you have n in binary,
it's just a matter of multiplications by the appropriate
powers of 2^k of b for the "on-bits" for n. And of course,
every result you get is in (mod m), so you only need to
have the result as an integer in (-m/2,m/2] or [0,m-1].

Are there any restrictions at all on b, n and m?