How do you find the smallest value of $a$ where:
$b^a \equiv 1 \pmod{p}$
$b$ is not divisible by $p$, and $p$ is a prime number.
Fermat's little theorem works, but it doesn't ensure that $a$ is minimised.
What else could be used?
Asked
Active
Viewed 53 times
0
-
Unless you're given more information about $b$, you would have to check every factor of $p-1$. – Ben Grossmann Nov 18 '13 at 05:16
-
You need to find multiplicative order $(d)$(http://mathworld.wolfram.com/MultiplicativeOrder.html) & one of the clues is that $d$ must divide $\phi(p)=p-1$ – lab bhattacharjee Nov 18 '13 at 05:16
-
If you are lucky and you know the prime divisors of $p-1$, and there are not many, there is a fairly quick algorithm. – André Nicolas Nov 18 '13 at 05:19
-
do you mean p is not divisible by b, because 1 to the power of anything will equal 1 mod anything – EpicGuy Nov 18 '13 at 06:08
-
@Omnomnomnom: What is the technique you mentioned called? – green Nov 18 '13 at 06:44
-
@green I am not aware of it having any name in particular. I suppose you could call it an application of Lagrange's theorem if you have to call it something. As Andre indicates, you can save some computation by using the prime factors of $p-1$ – Ben Grossmann Nov 18 '13 at 06:53