ทฤษฎีจำนวนและเลขคณิตมอดูลาร์: แบบฝึกหัดพร้อมเฉลยทีละขั้นตอน

แบบฝึกหัด ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ฟรี พร้อมแผนภาพ คำใบ้ และเฉลยละเอียด ตัวเลขใหม่ทุกครั้ง สามระดับ: gcd และเศษ, ตัวผกผันและความสอดคล้อง, เลขยกกำลังมอดูลาร์และ RSA

โจทย์ฝึกฟรีง่าย
012345678910mod 11

จงหา 942 mod 11 ซึ่งเป็นเศษ r ที่ 0 ≤ r < 11

a = 942n = 11

คำตอบที่แน่นอน: จำนวนเต็ม ไม่ต้องปัดเศษ

โจทย์ถัดไป →
ฝึก ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ฟรีฝึก ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ เลยโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร

สิ่งที่คุณจะได้ฝึก

  1. ง่ายgcd และเศษ
  2. ปานกลางตัวผกผันและความสอดคล้อง
  3. ยากเลขยกกำลังมอดูลาร์และ RSA

วิธีแก้โจทย์ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

  1. ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
  2. สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
  3. สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
  4. แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
  5. สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)

ข้อผิดพลาดที่พบบ่อย

  • ให้เศษเป็นลบสำหรับจำนวนลบ
  • หยุดขั้นตอนวิธีของยูคลิดที่เศษแรก
  • ปล่อยตัวผกผันให้เป็นลบแทนที่จะบวก n
  • หาเลขชี้กำลัง d ของ RSA มอดูโล n แทนที่จะเป็น φ(n)
  • ลดเลขชี้กำลังมอดูโล p แทนที่จะเป็น p − 1 เมื่อใช้ทฤษฎีบทของแฟร์มา

สูตรสำคัญ

การหารที่มีเศษ
a = q·n + r, 0 ≤ r < n
ยูคลิด
gcd(a, b) = gcd(b, a mod b)
ตัวคูณร่วมน้อย
lcm(a, b) = a·b/gcd(a, b)
อินเวอร์ส
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
ความสอดคล้องเชิงเส้น
a·x ≡ b → x ≡ a⁻¹·b (mod n)
ฟังก์ชันโทเทียนต์ของออยเลอร์
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
แฟร์มา
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

เรียนรู้ ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ตั้งแต่ต้น

1เศษและความสอดคล้อง

การหาร a ด้วย n ได้ผลหาร q และเศษ r: a = q·n + r โดย 0 ≤ r < n เศษเขียนเป็น a mod n สำหรับจำนวนลบ q ก็เป็นลบเช่นกัน: −3 = −1·7 + 4 ดังนั้น −3 mod 7 = 4

จำนวนสองจำนวนสอดคล้องกันมอดูโล n, a ≡ b (mod n) เมื่อให้เศษเท่ากัน คือเมื่อ n หาร a − b ลงตัว

0123456mod 7−3 ≡ 411 ≡ 4

เศษลดค่าได้ทุกขั้นตอน ซึ่งทำให้ตัวเลขเล็กอยู่เสมอ:

(a + b) mod n = ((a mod n) + (b mod n)) mod n, และเช่นเดียวกันสำหรับ a·b

ตัวอย่างเช่น 47·58 mod 9: 47 ≡ 2 และ 58 ≡ 4 ดังนั้น 47·58 ≡ 8 (mod 9)

ตรวจสอบตนเอง −17 mod 5 เป็นเท่าใด
  1. 2
  2. 3
  3. −2
  4. −3

คำตอบ: 3. −17 = −4·5 + 3 ดังนั้นเศษคือ 3 คำตอบ 2 คือ 17 mod 5 เศษไม่เป็นลบเสมอ

2ขั้นตอนวิธีของยูคลิด

ตัวหารร่วมมาก gcd(a, b) คือจำนวนที่ใหญ่ที่สุดที่หารทั้งสองลงตัว ขั้นตอนวิธีของยูคลิดใช้ gcd(a, b) = gcd(b, a mod b):

  1. หาร: a = q·b + r
  2. แทน (a, b) ด้วย (b, r)
  3. ทำซ้ำจนเศษเป็น 0 เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ gcd
252 = 2·105 + 42, 105 = 2·42 + 21, 42 = 2·21 + 0 → gcd = 21

ตัวคูณร่วมน้อยหาได้จากสิ่งนี้: lcm(a, b) = a·b / gcd(a, b)

ตรวจสอบตนเอง gcd(84, 36) เป็นเท่าใด
  1. 12
  2. 252
  3. 4
  4. 6

คำตอบ: 12. 84 = 2·36 + 12 และ 36 = 3·12 + 0 ดังนั้น gcd คือ 12 ส่วน 252 คือตัวคูณร่วมน้อย 84·36/12

3ตัวผกผันและขั้นตอนวิธีแบบขยาย

ตัวผกผันของ a มอดูโล n คือจำนวน x ที่ a·x ≡ 1 (mod n) มีอยู่เมื่อ gcd(a, n) = 1 เท่านั้น

ขั้นตอนวิธีของยูคลิดแบบขยายรันยูคลิดบน (n, a) และเก็บสัมประสิทธิ์ t สำหรับแต่ละเศษ เพื่อให้เศษ r ทุกตัว ≡ t·a (mod n) เริ่มด้วย t = 0 สำหรับ n และ t = 1 สำหรับ a แต่ละ t ใหม่คือ t สองแถวก่อนหน้าลบด้วย q คูณ t หนึ่งแถวก่อนหน้า เมื่อเศษ 1 ปรากฏ t ของมันคือตัวผกผัน

เมื่อมีตัวผกผัน ความสอดคล้อง a·x ≡ b (mod n) แก้ได้โดย x ≡ a⁻¹·b เมื่อ d = gcd(a, n) มากกว่า 1 จะมีคำตอบ d คำตอบถ้า d หาร b ลงตัว และไม่มีคำตอบถ้าไม่ลงตัว

ความสอดคล้องสองข้อที่มอดูลัสเป็นจำนวนเฉพาะสัมพัทธ์กัน x ≡ r₁ (mod m₁) และ x ≡ r₂ (mod m₂) มีคำตอบเดียวพอดีมอดูโล m₁·m₂ (ทฤษฎีบทเศษเหลือของจีน) เขียน x = r₁ + m₁k แล้วแก้หา k

ตัวอย่างที่แก้ให้ดู

จงหาตัวผกผันของ 7 มอดูโล 40

1

ยูคลิดบน (40, 7)

40 = 5·7 + 5, 7 = 1·5 + 2, 5 = 2·2 + 1
2

ติดตามสัมประสิทธิ์ t

t(40) = 0, t(7) = 1

t(5) = 0 − 5·1 = −5, t(2) = 1 − 1·(−5) = 6, t(1) = −5 − 2·6 = −17
3

ทำให้เป็นบวก

1 ≡ −17·7 (mod 40) และ −17 + 40 = 23

4

ตรวจสอบ

7·23 = 161 = 4·40 + 1
คำตอบ

ตัวผกผันคือ 7⁻¹ ≡ 23 (mod 40)

4เลขยกกำลังมอดูลาร์และ RSA

การยกกำลังสองซ้ำคำนวณ aᵏ mod n ได้อย่างรวดเร็ว: เขียน k เป็นเลขฐานสอง หา a, a², a⁴, a⁸, … mod n โดยยกกำลังสองและลดค่า แล้วคูณเลขยกกำลังที่บิตเป็น 1

ทฤษฎีบทเล็กของแฟร์มา: สำหรับจำนวนเฉพาะ p ที่หาร a ไม่ลงตัว aᵖ⁻¹ ≡ 1 (mod p) ดังนั้นลดเลขชี้กำลังมอดูโล p − 1 ได้

RSA สร้างกุญแจจากจำนวนเฉพาะสองจำนวน p และ q:

  1. n = p·q และ φ(n) = (p − 1)(q − 1)
  2. เลือก e ที่ gcd(e, φ(n)) = 1 โดย (n, e) คือกุญแจสาธารณะ
  3. คำนวณ d = e⁻¹ mod φ(n): คือกุญแจส่วนตัว
  4. เข้ารหัส c = mᵉ mod n ถอดรหัส m = cᵈ mod n

φ(n) ของออยเลอร์นับจำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n: φ(p) = p − 1 สำหรับจำนวนเฉพาะ φ(pᵏ) = pᵏ − pᵏ⁻¹ และ φ มีสมบัติการคูณสำหรับตัวประกอบที่เป็นจำนวนเฉพาะสัมพัทธ์กัน

ตรวจสอบตนเอง กุญแจ RSA ใช้ p = 5, q = 11 และ e = 3 d เป็นเท่าใด
  1. 13
  2. 27
  3. 37
  4. 3

คำตอบ: 27. φ(n) = 4·10 = 40 และ 3·27 = 81 = 2·40 + 1 ดังนั้น d = 27 ตัวผกผันของ 3 มอดูโล n = 55 จะเป็น 37 แต่ d หาได้มอดูโล φ(n)

5ข้อผิดพลาดที่พบบ่อย

  • ให้เศษเป็นลบสำหรับจำนวนลบ: −17 mod 5 คือ 3 ไม่ใช่ −2
  • หยุดยูคลิดที่เศษแรกแทนที่จะเป็นเศษที่ไม่เป็นศูนย์ตัวสุดท้าย
  • ลืมบวก n เข้ากับสัมประสิทธิ์ลบจากขั้นตอนวิธีแบบขยาย
  • คำนวณเลขชี้กำลัง RSA d มอดูโล n แทนที่จะเป็นมอดูโล φ(n)
  • ลดเลขชี้กำลังมอดูโล p แทนที่จะเป็น p − 1 เมื่อใช้ทฤษฎีบทของแฟร์มา

6ข้อสอบมีหน้าตาอย่างไร

  • ง่าย: gcd และเศษ คุณรันขั้นตอนวิธีของยูคลิดเพื่อหา gcd หรือ lcm หาเศษของจำนวนลบ และลดผลบวกและผลคูณมอดูโล n
  • ปานกลาง: ตัวผกผันและความสอดคล้อง คุณหาตัวผกผันมอดูลาร์ด้วยขั้นตอนวิธีแบบขยาย แก้ความสอดคล้องเชิงเส้น รวมความสอดคล้องสองข้อด้วยทฤษฎีบทเศษเหลือของจีน และคำนวณ φ(n) ของออยเลอร์
  • ยาก: เลขยกกำลังมอดูลาร์และ RSA คุณใช้การยกกำลังสองซ้ำและทฤษฎีบทของแฟร์มา แก้ความสอดคล้องที่มีหลายคำตอบ และหาเลขชี้กำลังส่วนตัว ข้อความเข้ารหัส และข้อความที่ถอดรหัสของ RSA

เรียนรู้ทีละขั้นในแอปเรียนรู้ทีละขั้นในแอป

ตัวอย่างวิธีทำ

ตัวอย่างที่ 1ง่าย

จงหา (914·953) mod 11 โดยไม่ต้องคูณจำนวนใหญ่ออกมา: ให้ลดค่าก่อน

n = 11

จงหา (914·953) mod 11

แสดงคำใบ้
  1. (x·y) mod n = ((x mod n)·(y mod n)) mod n และใช้ได้เช่นเดียวกันกับผลบวก
  2. 914 mod 11 = 1, 953 mod 11 = 7.
  3. ลดผลคูณของเศษมอดูโล 11
แสดงคำตอบและเฉลยทีละขั้นตอน

การหารลงตัวและเศษ: a mod n คือเศษ r ที่ 0 ≤ r < n และ a = q·n + r ซึ่งใช้ได้เมื่อ a เป็นลบด้วย ขั้นตอนวิธีของยูคลิดหา gcd(a, b) โดยทำ a = q·b + r ซ้ำและแทน (a, b) ด้วย (b, r) เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ gcd จากนั้น lcm(a, b) = a·b/gcd(a, b) ลดเศษได้ทุกขั้นตอน: (a + b) mod n และ (a·b) mod n ขึ้นอยู่กับ a mod n และ b mod n เท่านั้น

ลดแต่ละจำนวน

914 ≡ 1, 953 ≡ 7 (mod 11)

รวมกัน

1·7 = 7 ≡ 7 (mod 11)

คำตอบ

(914·953) mod 11 = 7
ตัวอย่างที่ 2ปานกลาง

จงหาฟังก์ชันโทเทียนต์ของออยเลอร์ φ(637) ซึ่งเป็นจำนวนของจำนวนเต็มตั้งแต่ 1 ถึง 637 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 637

n = 637 = 72·13

จงหา φ(637)

แสดงคำใบ้
  1. แยก n เป็นตัวประกอบเฉพาะ: 637 = 72·13
  2. φ มีสมบัติการคูณสำหรับตัวประกอบที่เป็นจำนวนเฉพาะสัมพัทธ์กัน และ φ(pᵏ) = pᵏ − pᵏ⁻¹
  3. φ(n) = n·∏(1 − 1/p).
แสดงคำตอบและเฉลยทีละขั้นตอน

ตัวผกผันและความสอดคล้อง: a มีตัวผกผันมอดูโล n เมื่อ gcd(a, n) = 1 เท่านั้น ขั้นตอนวิธีของยูคลิดแบบขยายเขียน 1 = s·n + t·a แล้ว a⁻¹ ≡ t (mod n) ความสอดคล้อง a·x ≡ b (mod n) ที่ gcd(a, n) = 1 มีคำตอบ x ≡ a⁻¹·b ความสอดคล้องสองข้อ x ≡ r₁ (mod m₁) และ x ≡ r₂ (mod m₂) ที่มอดูลัสเป็นจำนวนเฉพาะสัมพัทธ์กันมีคำตอบเดียวมอดูโล m₁·m₂ (ทฤษฎีบทเศษเหลือของจีน) φ(n) ของออยเลอร์นับจำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n: φ(n) = n·∏(1 − 1/p)

ตัวประกอบเฉพาะ

637 = 72·13

โทเทียนต์

φ(637) = φ(49)·φ(13) = 42·12 = 504

คำตอบ

φ(637) = 504
ตัวอย่างที่ 3ยาก
mc = me​ mod n225m = cd​ mod n?(n, e) = (481, 23)d

กุญแจ RSA ใช้ p = 13, q = 37 และ e = 23 จงถอดรหัสข้อความเข้ารหัส c = 225: หาข้อความ m

p = 13q = 37e = 23c = 225

จงหา m

แสดงคำใบ้
  1. n = 481, φ(n) = 432
  2. d = e⁻¹ mod φ(n) = 263
  3. m = cd mod n = 225263 mod 481: ใช้การยกกำลังสองซ้ำ.
แสดงคำตอบและเฉลยทีละขั้นตอน

เลขยกกำลังมอดูลาร์และ RSA: คำนวณ aᵏ mod n ด้วยการยกกำลังสองซ้ำ: เขียน k เป็นเลขฐานสอง ยกกำลังสอง ลดค่าหลังทุกขั้นตอน และคูณเลขยกกำลังที่บิตเป็น 1 แฟร์มา: aᵖ⁻¹ ≡ 1 (mod p) สำหรับจำนวนเฉพาะ p ที่หาร a ไม่ลงตัว ดังนั้นลดเลขชี้กำลังมอดูโล p − 1 ได้ RSA: เลือกจำนวนเฉพาะ p และ q, n = p·q และ φ(n) = (p − 1)(q − 1) เลขชี้กำลังสาธารณะ e เป็นจำนวนเฉพาะสัมพัทธ์กับ φ(n) และเลขชี้กำลังส่วนตัวคือ d = e⁻¹ mod φ(n) เข้ารหัสด้วย c = mᵉ mod n และถอดรหัสด้วย m = cᵈ mod n

เลขชี้กำลังส่วนตัว

n = 481, φ(n) = 432
d = 23−1 mod 432 = 263

ถอดรหัสด้วยการยกกำลังสองซ้ำ

263 = 256 + 4 + 2 + 1
2251 ≡ 225 (mod 481)
2252 ≡ 120 (mod 481)
2254 ≡ 451 (mod 481)
2258 ≡ 419 (mod 481)
22516 ≡ 477 (mod 481)
22532 ≡ 16 (mod 481)
22564 ≡ 256 (mod 481)
225128 ≡ 120 (mod 481)
225256 ≡ 451 (mod 481)
225263 ≡ 225·120·451·451 ≡ 361 (mod 481)

ข้อความ

m = 361
ตรวจสอบ: 36123 mod 481 = 225

คำตอบ

m = 361

คำถามและคำตอบ

ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ คืออะไร

การหาร a ด้วย n ได้ผลหาร q และเศษ r: a = q·n + r โดย 0 ≤ r < n เศษเขียนเป็น a mod n สำหรับจำนวนลบ q ก็เป็นลบเช่นกัน: −3 = −1·7 + 4 ดังนั้น −3 mod 7 = 4

จำนวนสองจำนวนสอดคล้องกันมอดูโล n, a ≡ b (mod n) เมื่อให้เศษเท่ากัน คือเมื่อ n หาร a − b ลงตัว

จะแก้โจทย์ ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ทีละขั้นได้อย่างไร
  1. ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
  2. สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
  3. สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
  4. แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
  5. สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)
ข้อผิดพลาดที่พบบ่อยใน ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ มีอะไรบ้าง
  • ให้เศษเป็นลบสำหรับจำนวนลบ
  • หยุดขั้นตอนวิธีของยูคลิดที่เศษแรก
  • ปล่อยตัวผกผันให้เป็นลบแทนที่จะบวก n
  • หาเลขชี้กำลัง d ของ RSA มอดูโล n แทนที่จะเป็น φ(n)
  • ลดเลขชี้กำลังมอดูโล p แทนที่จะเป็น p − 1 เมื่อใช้ทฤษฎีบทของแฟร์มา
แบบฝึกหัด ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ครอบคลุมเรื่องอะไรบ้าง
  • ง่าย: gcd และเศษ
  • ปานกลาง: ตัวผกผันและความสอดคล้อง
  • ยาก: เลขยกกำลังมอดูลาร์และ RSA

โจทย์ทุกข้อใช้ค่าใหม่ คุณจึงเรียนรู้วิธีทำ ไม่ใช่จำคำตอบ ติดขัดใช่ไหม เปิดคำใบ้เล็ก ๆ ก่อน และเปิดคำอธิบายฉบับเต็มเมื่อจำเป็นเท่านั้น

การฝึกทำงานอย่างไร

  • โจทย์ทุกข้อใช้ค่าใหม่ คุณจึงเรียนรู้วิธีทำ ไม่ใช่จำคำตอบ
  • ติดขัดใช่ไหม เปิดคำใบ้เล็ก ๆ ก่อน และเปิดคำอธิบายฉบับเต็มเมื่อจำเป็นเท่านั้น
  • ความก้าวหน้า ข้อที่ผิด และโจทย์ที่บันทึกไว้จะถูกเก็บไว้ เพื่อให้คุณทบทวนก่อนสอบได้

รายวิชาที่มีหัวข้อนี้

พื้นฐานวิทยาการคอมพิวเตอร์คณิตศาสตร์ไม่ต่อเนื่อง

หัวข้ออื่นในคณิตศาสตร์และสถิติ

ลิมิตอนุพันธ์การหาค่าเหมาะที่สุดอินทิกรัลลำดับและอนุกรมแคลคูลัสหลายตัวแปรสมการเชิงอนุพันธ์จำนวนเชิงซ้อนวิธีเชิงตัวเลขเมทริกซ์และดีเทอร์มินันต์เวกเตอร์: ผลคูณจุดและผลคูณไขว้ตรรกศาสตร์ประพจน์และการพิสูจน์เซต ความสัมพันธ์ และฟังก์ชันทฤษฎีกราฟความน่าจะเป็นสถิติเชิงพรรณนาการแจกแจงปกติช่วงความเชื่อมั่นการทดสอบสมมติฐานและช่วงความเชื่อมั่นการถดถอยเชิงเส้นและสหสัมพันธ์การทดสอบไคสแควร์

ใบงานสำหรับพิมพ์

ใบงาน ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ พร้อมเฉลย
ฝึก ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ ฟรีฝึก ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ เลยโจทย์ฟรีวันละ 5 ข้อ ไม่ต้องใช้บัตร