Modular Arithmetic

นิยาม ให้ a เป็นจำนวนเต็ม m เป็นจำนวนเต็มบวก จะใช้สัญลักษณ์ a mod m แทนเศษที่
ได้จากการหาร a ด้วย m

ตัวอย่าง           3 mod 5 = 3 , -3 mod 5 = 2 , 17 mod 5 = 2,
-9 mod 4= 3 , 2001 mod 101 = 82
นิยาม ให้ a , b ฮ Z m ฮ Z⁺ จะเรียก a สมภาคกับ b มอดุโล m ( a congruent to b modulo m) ถ้า m | (a-b) จะใช้สัญลักษณ์แทนด้วย a บ b ( mod m )
จะใช้สัญลักษณ์ a    ~บ b ( mod m ) แทน a ไม่สมภาคกับ b มอดุโล m
ตัวอย่าง 17 บ 5 mod 6 , 24 ~บ 14 mod 6
ข้อสังเกตุ a บ b mod m ก็ต่อเมื่อ a mod m = b mod m
ทฤษฎีบท ให้ m ฮ Z⁺ , a, b ฮ Z
a บ b mod m ก็ต่อเมื่อ a = b + km บาง k ที่เป็นจำนวนเต็ม
ทฤษฎีบท ให้ m ฮ Z⁺ , a, b,c,d ฮ Z จะได้ว่า
1. a บ a mod m
2. ถ้า a บ b mod m แล้ว b บ a mod m
3. ถ้า a บ b mod m และ b บ c mod m แล้ว a บ c mod m
4. ถ้า a บ b mod m แล้ว a + c บ b +c mod m, a c บ b c mod m
5. ถ้า a บ b mod m และ c บ d mod m แล้ว
         a + c บ b +d mod m , a.c บ   b.d mod m
6. ถ้า a บ b mod m แล้ว a^k บ b^k mod m ทุก k ฮ Z⁺

ตัวอย่าง 7 บ 2 mod 5, 11 บ 1 mod 5 จะได้ว่า 18 = 7+11 บ 2 + 1 = 3 mod 5
และ 77 = 7 (11) บ 2(1) = 2 mod 5

ตัวอย่าง จงแสดงว่า 15 | (17¹⁰⁰ - 1 )

บทประยุกต์ ของ สมภาค

ตัวอย่าง การเลื่อกตัวเลขแบบสุ่มโดยวิธี สมภาคเชิงเส้น โดยการเลือกตัวเลข 4 ตัว คือ
m, a, c, x₀ ซึ่ง 1 < a < m , m > c ณ 0 และ m > x₀ ณ 0 .
แล้วจะสร้งตัวเลขลำดับ { x_n } ซึ่ง m > x_nณ 0 ทุก n จาก สมการ
x_n+1 = a x_n + c mod m
เช่น m = 9, a = 7, c = 4 , x₀ = 3
จะได้ว่า x₁=7, x₂=8, x₃=6, x₄=1, x₅=2, x₆=0, x₇=4, x₈=5, x₉=3,...

ตัวอย่าง รหัส ซีซาร์ ( Caesar cipher ) กำหนดให้ ตัวอักษร A = 0 , B =1,..., Z = 25
ให้ f(p) = p + 3 mod 26.
จงเปลี่ยนข้อความ " MEET YOU IN THE PARK " โดยรหัส ซีซาร์

ตัวอย่าง จงถอดข้อความ " WHQ" ที่ถูกเปลี่ยนโดยรหัสซีชาร์

ตัวอย่าง กำหนดให้ ตัวอักษร A = 0 , B =1 , ... , Z = 25
ให้ f(p) = 7p+3 mod 26.
จงเปลี่ยนข้อความ " LOVE " โดย ใช้ฟังก์ชัน f .

สมภาคเชิงเส้น

นิยาม สมภาค ในรูปแบบ a x บ b mod m เมื่อ m ฮ Z⁺ , a, b ฮ Z และ x เป็นตัวแปร
จะเรียกว่า สมภาคเชิงเส้น (Linear Congruences)

นิยาม จะเรียก จำนวนเต็ม x₀ ที่สอดคล้องในสมภาคเชิงเส้น a x บ b mod m
ว่าผลเฉลย (solution) ของสมภาคเชิงเส้น

ทฤษฎีบท ถ้า x₀ เป็นผลเฉลย ของสมภาคเชิงเส้น a x บ b mod m
และ x₀ บ x₁ mod m แล้ว x₁ เป็นผลเฉลย ของสมภาคเชิงเส้นด้วย

ทฤษฎีบท ให้ m ฮ Z⁺ , a, b ฮ Z และ d = gcd (a, m) แล้วจะได้ว่า
สมภาคเชิงเส้น a x บ b mod m มีผลเฉลย ก็ต่อเมื่อ d | b

ตัวอย่าง จงหาผลเฉลย ( ถ้ามี ) ของสมภาคเชิงเส้น 14 x บ 13 mod 21

ตัวอย่าง จงหาผลเฉลย ( ถ้ามี ) ของสมภาคเชิงเส้น 235 x บ 54 mod 7

ทฤษฎีบท ให้ m, n ฮ Z⁺ , a, b ฮ Z และ gcd (m, n) = 1 แล้วระบบสมภาคเชิงเส้น

x บ a mod m
x บ b mod n

มีผลเฉลยร่วมกันเพียงชุดเดียวมอดุโล mn

ทฤษฎีบท (Chiness Remainder Theory )
ให้ m₁, m₂ , ... , m_k ฮ Z⁺ , a₁, a₂ ,..., a_k ฮ Z และ gcd (m_i , m_j) = 1 ถ้า i น j
แล้วระบบสมภาคเชิงเส้น

x บ a₁ mod m₁
x บ a₂ mod m₂

x บ a_k mod m_k

มีผลเฉลยร่วมกันเพียงชุดเดียวมอดุโล m₁m₂ ... m_k

ตัวอย่าง จงหาผลเฉลยของระบบสมภาคเชิงเส้น
x บ 2 mod 3 , x บ 3 mod 5 , x บ 2 mod 7

ตัวอย่าง จงหาผลเฉลยของระบบสมภาคเชิงเส้น
x บ 7 mod 9, x บ 3 mod 23, x บ 1 mod 4

การคำนวณ ตัวเลขที่มีค่ามาก

ให้ m₁, m₂ ,.., m_n > 1 เป็นจำนวนเฉพาะสัมพัทธ์ต่อกันทุกคู่ ( gcd(m_i,m_j) = 1 ถ้า i น j )
m = m₁. m₂ .. m_n จะได้ว่า ทุกจำนวนเต็ม a ที่ m > a ณ 0
สามารถแทนได้ด้วย n-สิ่งอันดับ (a mod m₁, a mod m₂ ,..., a mod m_n)

ตัวอย่าง ให้ m₁ = 3 และ m₂ =4
ดังนั้นสามารถแทนตัวเลข ตั้งแต่ 0 ถึง 11 ได้ด้วยคู่อันดับต่อไปนี้
0 = (0,0) 1 = (1,1) 2 = (2,2) 3 = (0,3)
4 = (1,0) 5 = (2,1) 6 = (0,2) 7 = (1,3)
8 = (2,0) 9 = (0,1) 10 = (1,2) 11= (2,3)

ตัวอย่าง ให้ m₁ = 99 , m₂ = 98 , m₃ = 97 และ m₄ = 95
จงแทนตัวเลข 123684 และ 413456 ด้วย 4-สิ่งอันดับ
และถ้า 4ขสิ่งอันดับแทนได้ด้วย ( 65,2,51,10) จงหาค่าของตัวเลขนี้

รห้ส RSA (RSA Encryption)

รห้ส RSA สร้างโดยกลุ่ม นักวิจัย 3 คน คือ Rivert , Shamir and Adleman โดยการสร้างฟังก์ชั่นการแปลงรหัสเป็น
C = M^e mod m
เมื่อ m = p.g โดยที่ p , q เป็นจำนวนเฉพาะ 1< e < (p-1)(q-1) และ gcd(e ,(p-1)(q-1) ) = 1
และ สามารถถอดรหัสเป็น
P = C^d mod m
โดยต้องหาค่า d ที่ d e บ 1 mod (p-1)(q-1)
ซึ่งในทางปฎิบัติแล้วการที่จะแปลงรหัสด้วยวิธีนี้เราต้องมีเครื่องคำนวณที่มีความสามารถในการคิดตัวเลขที่มีค่ามากได้เร็วดังตัวอย่าง

ตัวอย่าง จงแปลงรหัส ข้อความ STOP โดยใช้รหัส RSA เมื่อ p = 43 และ q = 59 และ เลือก e = 13
วิธีทำ จากข้อความ STOP แปลงเป็นตัวเลขได้ 18, 19, 14, 15
จัดกลุ่มตัวเลขเป็น 4 หลัก (แล้วแต่ข้อตกลงระหว่างผู้ส่งกับผู้รับ)ได้เป็น 1819 และ 1415
แปลงรหัสโดย C = M¹³ mod (43)(59) =2537
ได้เป็น 1819¹³ mod 2537 = 2081 และ 1415¹³ mod 2537 = 2182
ดังนั้นจะได้ตัวเลขที่ได้จากการแปลงรหัสเป็น 2081 2182 ซึ่งจะแปลงเป็นตัวอักษรต่อไป

ตัวอย่าง จงถอดรหัส RSA จากตัวอย่างที่แล้ว ที่แปลงมาจากข้อความแล้วได้ตัวเลข
0981 0461 โดยที่ผู้ส่งรหัส บอกค่า e =13 และ n = 2537
วิธีทำ จาก n = 2537 แยกตัวประกอบเป็นจำนวนเฉพาะ 2 ตัวคูณกันได้ 43 59
หา d ที่ทำให้ได้ว่า d(13) บ 1 mod (42)(58) ได้ d = 937
ถอดรหัส โดย P = C⁹³⁷ mod 2537
ดังนั้น 0981⁹³⁷ mod 2537 = 0704 และ 0461⁹³⁷ mod 2537 = 1115
ซึ่งถอดเป็นข้อความได้เป็น HELP.

ดูเพิ่มเติมที่ http://www.orst.edu/dept/honors/makmur/index.html
และที่ http://www.rsasecurity.com/