Modular Exponentiation - Math Help Forum

$Math Help Forum$

$Go Back$		Math Help Forum > College/University Maths Help > Number theory
$Reload this Page$ Modular Exponentiation

Mark Forums Read

$Reply$

#1

$Old$ 08-27-2008, 05:49 PM

timorrill $timorrill is offline$

Newbie

Join Date: Aug 2008

Posts: 1

Country:

United States

Thanks: 0

Thanked 0 Times in 0 Posts

$timorrill is on a distinguished road$

$Default$ Modular Exponentiation

I'm struggling to understand why the following is true:

x^d mod p = x^(d mod (p-1)) mod p

Can anyone help to explain this?

$Reply With Quote$

Advertisement

#2

$Old$ 08-27-2008, 06:31 PM

$ThePerfectHacker's Avatar$

ThePerfectHacker

$ThePerfectHacker is offline$

Global Moderator

Join Date: Nov 2005

Location: New York City

Posts: 11,339

Country:

Soviet Union

Thanks: 329

Thanked 2,943 Times in 2,472 Posts

$ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$ $ThePerfectHacker has a reputation beyond repute$

$Default$

Quote:

Originally Posted by timorrill $View Post$

x^d mod p = x^(d mod (p-1)) mod p

Can anyone help to explain this?

Assuming $\gcd(x,p)=1$ .

Let $e = d \bmod p-1$ .
Let $k = \text{ord}(x)$ .

Then $x^d \equiv x^e (\bmod p)$ if and only if $d\equiv e (\bmod k)$ if and only if $k|(d-e)$ . But $(p-1)|(d-e)$ and $k|(p-1)$ so $k|(d-e)$ .

__________________
We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America.

$Reply With Quote$

$Reply$

« Simplify | Elementary Number Theory - beginnings »

Thread Tools
$Show Printable Version$ Show Printable Version $Email this Page$ Email this Page
Display Modes
$Linear Mode$ Linear Mode $Hybrid Mode$ Switch to Hybrid Mode $Threaded Mode$ Switch to Threaded Mode

Posting Rules
You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are Off

Forum Jump

All times are GMT -7. The time now is 04:36 AM.

your link here Sponsors

rv solar, e-learning, Mortgage | Free Credit Score | Hotels in Newquay | Equity Release | Credit Cards

Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.