模运算 模运算的性质 [(a mod n)+( b mod n)]mod n=a+b mod n [(amod n)- b mod n) n=(a-b)mod n [(a mod n)x(b mod n)mod n=(ax b)mod n 2021/2/21 6
2021/2/21 6 模运算 ◼ 模运算的性质 ◼ [(a mod n)+(b mod n)] mod n=(a+b) mod n ◼ [(a mod n)-(b mod n)] mod n=(a-b) mod n ◼ [(a mod n)×(b mod n)] mod n=(a×b) mod n
模运算 ■例:Z8={0,1,23,4,5,6,7模8加法和乘法 +01234567×01234567 00123456700000000|0 112345670101234567 223456701|202460246 |3345670121303614725 456 012340404040 556701234505274163 66 0 23451606420642 770123456707654321 2021/2/21
2021/2/21 7 模运算 ◼ 例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法 ＋ 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 × 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 1 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1
模运算 ■若X↓y= o mod n,y为x的加法逆元。每 元素都有加法逆元 若对x,有Xy=1modn,称y为x的乘法 逆元。在上例中,并非所有X都有乘法逆 元 ■定义Zn={0,1,,n-为模n的同余类集合。 2021/2/21
2021/2/21 8 模运算 ◼ 若x+y=0 mod n, y为x的加法逆元。每一 元素都有加法逆元 ◼ 若对x，有xy=1 mod n，称y为x的乘法 逆元。在上例中，并非所有x都有乘法逆 元 ◼ 定义Zn={0,1,..,n-1}为模n的同余类集合