mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   modular arithmetic (https://www.mersenneforum.org/showthread.php?t=14309)

science_man_88 2010-12-07 14:47

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.

davieddy 2010-12-07 15:34

Your post count is approaching that of the legendary Mally, sm.

science_man_88 2010-12-07 15:46

[QUOTE=davieddy;240513]Your post count is approaching that of the legendary Mally, sm.[/QUOTE]

so in other words I should stop ?

CRGreathouse 2010-12-07 18:49

For basic introductions, see
[url]http://www.cut-the-knot.org/blue/Modulo.shtml[/url]
[url]http://www.math.rutgers.edu/~erowland/modulararithmetic.html[/url]

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
[url]http://www.math.usf.edu/~eclark/elem_num_th_book.pdf[/url]
[url]http://shoup.net/ntb/[/url]
[url]http://modular.math.washington.edu/ent/[/url]

davieddy 2010-12-07 19:06

[QUOTE=science_man_88;240515]so in other words I should stop ?[/QUOTE]

Nah.
Hasn't done me any harm.
Yet.
Touch wood.

David

science_man_88 2010-12-07 22:29

[QUOTE=CRGreathouse;240540]For basic introductions, see
[url]http://www.cut-the-knot.org/blue/Modulo.shtml[/url]
[url]http://www.math.rutgers.edu/~erowland/modulararithmetic.html[/url]

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
[url]http://www.math.usf.edu/~eclark/elem_num_th_book.pdf[/url]
[url]http://shoup.net/ntb/[/url]
[url]http://modular.math.washington.edu/ent/[/url][/QUOTE]

I see uses I never thought of as modular arithmetic lol.

3.14159 2010-12-07 22:30

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 [B]not[/B] hold for exponentiation;

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

CRGreathouse 2010-12-07 22:42

[QUOTE=science_man_88;240508]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]

[QUOTE=3.14159;240571]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.[/QUOTE]

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 2010-12-07 22:46

[QUOTE=3.14159;240571]The above does [B]not[/B] hold for exponentiation;

((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.[/QUOTE]

Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).

3.14159 2010-12-08 00:20

[QUOTE=CRGreathouse;240575]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.[/QUOTE]

List a few examples.

3.14159 2010-12-08 00:25

[QUOTE=CRGreathouse;240577]Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).[/QUOTE]

Going back to my example: By phi, do you mean, phi(19, (exponent))? Or do you mean, 19?


All times are UTC. The time now is 22:58.

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