mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-12-07, 14:47   #1
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default modular arithmetic

I was wondering how much I knew about modular arithmetic and if anyone else could add more it would be appreciated. I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations. I know there's more than this to modular arithmetic anyone care to expand my knowledge or give me a link because they don't care lol I can look up more I guess I will have to.
science_man_88 is offline   Reply With Quote
Old 2010-12-07, 15:34   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

6,451 Posts
Default

Your post count is approaching that of the legendary Mally, sm.
davieddy is offline   Reply With Quote
Old 2010-12-07, 15:46   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by davieddy View Post
Your post count is approaching that of the legendary Mally, sm.
so in other words I should stop ?
science_man_88 is offline   Reply With Quote
Old 2010-12-07, 18:49   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default

For basic introductions, see
http://www.cut-the-knot.org/blue/Modulo.shtml
http://www.math.rutgers.edu/~erowlan...rithmetic.html

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
http://www.math.usf.edu/~eclark/elem_num_th_book.pdf
http://shoup.net/ntb/
http://modular.math.washington.edu/ent/
CRGreathouse is offline   Reply With Quote
Old 2010-12-07, 19:06   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

144638 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
so in other words I should stop ?
Nah.
Hasn't done me any harm.
Yet.
Touch wood.

David
davieddy is offline   Reply With Quote
Old 2010-12-07, 22:29   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
For basic introductions, see
http://www.cut-the-knot.org/blue/Modulo.shtml
http://www.math.rutgers.edu/~erowlan...rithmetic.html

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
http://www.math.usf.edu/~eclark/elem_num_th_book.pdf
http://shoup.net/ntb/
http://modular.math.washington.edu/ent/
I see uses I never thought of as modular arithmetic lol.
science_man_88 is offline   Reply With Quote
Old 2010-12-07, 22:30   #7
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

Operations using modular arithmetic;

(a mod x + b mod x) mod x = (a + b) mod x.

(a mod x * b mod x) mod x = (a * b) mod x.

The above does not hold for exponentiation;

((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.

Last fiddled with by 3.14159 on 2010-12-07 at 22:34
3.14159 is offline   Reply With Quote
Old 2010-12-07, 22:42   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations.
Quote:
Originally Posted by 3.14159 View Post
Operations using modular arithmetic;

(a mod x + b mod x) mod x = (a + b) mod x.

(a mod x * b mod x) mod x = (a * b) mod x.
Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.
CRGreathouse is offline   Reply With Quote
Old 2010-12-07, 22:46   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
The above does not hold for exponentiation;

((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.
Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).
CRGreathouse is offline   Reply With Quote
Old 2010-12-08, 00:20   #10
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24×3×5×7 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.
List a few examples.
3.14159 is offline   Reply With Quote
Old 2010-12-08, 00:25   #11
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

24·3·5·7 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).
Going back to my example: By phi, do you mean, phi(19, (exponent))? Or do you mean, 19?

Last fiddled with by 3.14159 on 2010-12-08 at 00:26
3.14159 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
modular arithmetic problem JuanTutors Math 4 2009-03-11 16:06
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Jim Howell's modular arithmetic program? ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 03:16.

Sun Oct 25 03:16:23 UTC 2020 up 45 days, 27 mins, 0 users, load averages: 2.67, 2.33, 2.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.