How to solve a^x mod b = c?

**name** · November 26th 2011, 07:14 AM

How to solve $a^x$ $mod$ $b = c$ for $x$ minimum integer solution.

With known integers $a$ , $b$ , and $c$ .

**apatch** · December 3rd 2011, 04:34 AM

If $b=1,2,4,p^\alpha,2p^\alpha$ with $\alpha\ge 1$ and $p$ an odd prime, then $b$ has a primitive root $g \mod b$ .
If $(a,b)=(c,b)=1$ then $x$ ind $_g a\equiv$ ind $_g c \pmod {\phi(b)}$ a linear congruence in $x$ .
If $d=($ ind $_g a,\phi(b))|$ ind $_g c$ then there are exactly $d$ solutions.

Then start by factoring $b$ . If $b$ has a factor $2^f$ with $f\ge 3$ then solve the equation $\mod 2^f$ first.

Thread: How to solve a^x mod b = c?

LinkBack

Thread Tools

Display

How to solve a^x mod b = c?

Re: How to solve a^x mod b = c?

Similar Math Help Forum Discussions

need to solve summation equation to solve sum(x2)

Solve for x

How To Solve Integral of e? And solve velocity?

how can i solve this

how do i solve this?

Search Tags