Phép toán Modulo – Wikipedia tiếng Việt

Thương số (

q

) và số dư (

r

) theo các hàm của số bị chia (

a

), bằng cách dùng các thuật toán khác nhauThương số ( ) và ) theo những hàm của số bị chia ( ), bằng cách dùng những thuật toán khác nhau

Trong điện toán, phép toán modulo là phép toán tìm số dư của phép chia 2 số (đôi khi được gọi là modulus).

Cho hai số dương, (số bị chia) a và (số chia) n, a modulo n (viết tắt là a mod n) là số dư của phép chia có dư Euclid của a cho n. Ví dụ, biểu thức “5 mod 2” bằng 1 vì 5 chia cho 2 có thương số là 2 là số dư là 1, trong khi “9 mod 3” bằng 0 do 9 chia 3 có thương số là 3 và số dư 0; không còn gì trong phép trừ của 9 cho 3 nhân 3. (Lưu ý rằng thực hiện phép chia bằng máy tính cầm tay sẽ không hiển thị kết quả giống như phép toán này; thương số sẽ được biểu diễn dưới dạng phần thập phân.)

Mặc dù thường được thực hiện khi a và n đều là số nguyên, nhiều hệ tính toán cho phép sử dụng các kiểu khác của toán học bằng số. Giới hạn của một modulo nguyên của n là tù 0 đến n − 1. (a mod 1 luôn bằng 0; a mod 0 là không xác định, có thể trả về lỗi chia cho số 0 trong nhiều ngôn ngữ lập trình.) Xem số học mô-đun để tìm các quy ước cũ hơn và liên quan được áp dụng trong lý thuyết số.

Khi hoặc a hoặc n là số âm, định nghĩa cơ bản bị phá vỡ và các ngôn ngữ lập trình khác nhau trong việc định nghĩa các kết quả này.

Tính toán phần dư trong phép toán modulo[sửa|sửa mã nguồn]

Trong toán học, hiệu quả của phép toán modulo là số dư của phép chia có dư. Tuy vậy những quy ước khác vẫn sống sót. Máy vi tính và máy tính có nhiều cách khác nhau để tàng trữ và đại diện thay mặt cho những số ; do đó định nghĩa của chúng về phép toán modulo nhờ vào vào ngôn từ lập trình hoặc phần cứng máy tính bên dưới cơ bản .

Trong hầu hết các hệ thống máy tính, thương số q và số dư r của phép chia a cho n thỏa mãn

q ∈ Z a = n q + r | r |

(1)

Tuy nhiên, vẫn còn sự nhập nhằng về dấu nếu số dư khác không: hai lựa chọn có thể cho số dư xảy ra, một âm và một dương, và hai lựa chọn cho thương số xảy ra. Trong lý thuyết số, thông thường số dư dương luôn được chọn, nhưng lựa chọn của các ngôn ngữ lập trình tùy thuộc vào ngôn ngữ và dấu của a hoặc n. Ngôn ngữ Pascal và ALGOL 68 tiêu chuẩn chọn số dư dương (hoặc 0) kể cả khi số chia là các số âm, đối với một vài ngôn ngữ lập trình như C90 thì dấu tùy thuộc vào cài đặt khi hoặc n hoặc a là số âm. Xem bảng để biết chi tiết. a modulo 0 là không xác định trong hầu hết các hệ thống, mặc dù một số hệ thống định nghĩa là a.

Theo diễn đạt của Leijen ,

Boute argues that Euclidean division is superior to the other ones in terms of regularity and useful mathematical properties, although floored division, promoted by Knuth, is also a good definition. Despite its widespread use, truncated division is shown to be inferior to the other definitions. ( Tạm dịch : Boute lập luận rằng phép chia có dư là tiêu biểu vượt trội so với những phép chia khác về tính đều đặn và những thuộc tính toán học hữu dụng, mặc dầu với phép chia sàn, được Knuth ủng hộ, cũng là một định nghĩa tốt. Tuy được sử dụng thoáng đãng, phép chia rút gọn được chứng tỏ kém hơn những định nghĩa khác. )Division and Modulus for Computer Scientists[9]— Daan Leijen ,

Tuy nhiên, Boute tập trung vào các tính chất của chính phép toán modulo và không đánh giá sự thật là phép chia rút gọn (tiếng Anh: truncated division) cho thấy sự đối xứng của (-a) div n = -(a div n) và a div (-n) = -(a div n), mà cũng giống phép chia thông thường. Bởi vì cả hai phép chia sàn và phép chia có dư đều không có tính đối xứng này, phán đoán của Boute ít nhất là không toàn diện.[cần dẫn nguồn]

Các sai lầm đáng tiếc thường thì[sửa|sửa mã nguồn]

Nếu tác dụng của phép chia modulo có dấu của số bị chia thì sẽ dẫn đến những sai lầm đáng tiếc đáng quá bất ngờ .Ví dụ, để kiểm tra tính lẻ của một số nguyên, ta hoàn toàn có thể kiểm tra số dư khi chia cho có bằng 1 :

boolis_odd(intn){
returnn%2= =1;
}

Khi ngôn ngữ lập trình có số dư có dấu của số bị chia, việc kiểm tra sẽ sai, do khi n (số bị chia) là số âm lẻ, n mod 2 trả về −1, và hàm trả về false.

Có thể sửa lại sai lầm đáng tiếc đó bằng cách kiểm tra rằng hiệu quả khác 0 ( do số dư bằng 0 được xem xét như nhau bất kể dấu ) :

boolis_odd(intn){
returnn%2
!=
0;
}

Hay là, bằng việc hiểu trước rằng với bất kể số lẻ nào, số dư modulo hoàn toàn có thể hoặc bằng 1 hoặc − 1 :

boolis_odd(intn){
returnn%2= =1| |n%2= =- 1;
}

mod nhị phân. Đối với kí hiệu (mod m), xem section này viết về phép toánnhị phân. Đối với kí hiệu, xem Quan hệ đồng dư

Một số máy tính cầm tay có nút của hàm mod(), và nhiều ngôn ngữ lập trình khác có hàm tương tự, biểu diễn cho mod(a, n). Một vài ngôn ngữ hỗ trợ các biễu thức mà dùng “%”, “mod”, hoặc “Mod” là toán tử modulo hoặc toán tử lấy số dư, chẳng hạn

a % n

hoặc

a mod n

hoặc tương đương cho môi trường thiếu hàm mod() (chú ý rằng kiểu ‘int’ vốn đã sinh ra giá trị rút gọn a/n)

a - (n * int(a/n))

Vấn đề hiệu suất[sửa|sửa mã nguồn]

Phép toán modulo hoàn toàn có thể được thiết lập sao cho mỗi lần phép chia với số dư được tính. Đôi với nhu yếu đặc biệt quan trọng, trên vài phần cứng, sống sót những phép toán tương tự như nhưng nhanh hơn. Ví dụ, modulo cho lũy thừa của 2 hoàn toàn có thể biễu diễn tương tự bởi phép toán bitwise AND :

x % 2n == x & (2n - 1)

Ví dụ (giả sử x là số nguyên dương):

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

Trong những thiết bị và ứng dụng mà thiết lập toán tử bitwise hiệu suất cao hơn toán tử modulo, những dạng thay thế sửa chữa này hoàn toàn có thể dẫn đến thống kê giám sát nhanh hơn. [ 10 ]

Các trình biên dịch tối ưu hóa có thể nhận diện các biểu thức có dạng expression % constant trong đó constant là lũy thừa của 2 và tự động cài đặt chúng thành expression & (constant-1). Điều này cho phép viết mã rõ ràng hơn mà không ảnh hưởng đến hiệu suất. Cách tối ưu hóa này không áp dụng cho các ngôn ngữ mà kết quả của phép toán modulo có cùng dẫu với số bị chia (bao gồm C), trừ phi số bị chia là kiểu số nguyên không dấu. Bởi vì nếu số bị chia là số âm thì modulo sẽ là số âm trong khi expression & (constant-1) sẽ luôn dương.

Tính tương tự[sửa|sửa mã nguồn]

Một số phép toán modulo hoàn toàn có thể được lan rộng ra tựa như sang những phép toán toán học khác. Điều này có tính hữu dụng trong những chứng tỏ mật mã học, ví dụ điển hình trao đổi khóa Diffie-Hellman .

• Phần tử đơn vị:

  • (a mod n) mod n = a mod n

    .

  • nx mod n = 0

    với mọi số nguyên dương

    x

    .

  • Nếu

    p

    là số nguyên tố không phải là ước số của

    b

    , thì

    abp−1 mod p = a mod p

    , dựa theo định lý nhỏ Fermat.

• Phần tử đảo:

  • [(−a mod n) + (a mod n)] mod n = 0

    .

  • b−1 mod n

    kí hiệu phần tử đảo modular, được định nghĩa khi và chỉ khi

    b

    và

    n

    là các số nguyên tố cùng nhau, khi vế trái xác định:

    [(b−1 mod n)(b mod n)] mod n = 1

    .

• Tính phân phối:

  • (a + b) mod n = [(a mod n) + (b mod n)] mod n

    .

  • ab mod n = [(a mod n)(b mod n)] mod n

    .

• Phép chia (định nghĩa):

  a

  /

  b

  mod n = [(a mod n)(b−1 mod n)] mod n

  , khi vế phải xác định (là khi

  b

  và math|n}} là các số nguyên tố cùng nhau). Các trường hợp còn lại là không xác định.

• Phép nhân nghịch đảo:

  [(ab mod n)(b−1 mod n)] mod n = a mod n

  .