Tham khảo toán học
Tìm kiếm các số nguyên, số nguyên tố, số học theo modulo, các phần tử sinh của nhóm cyclic, các số dư bậc hai, các phương trình Diophantine và RSA với các công thức và ví dụ minh họa.
Các lũy thừa liên tiếp của 3 truy cập mọi số dư khác 0 trước khi trở lại 1.
Việc bình phương các số dư khác 0 chỉ tạo ra 1, 2 và 4.
55 thuật ngữ
Số nguyên và nền tảng
Integer
ℤMột số nguyên có thể là số âm, số 0 hoặc số dương.
Sử dụng số nguyên cho số đếm với hướng, chỉ mục, sự khác biệt và các phép tính rời rạc chính xác.
-4, 0 và 27 là các số nguyên.Số nguyên và nền tảng
Natural number
ℕMột số đếm; việc liệu số 0 có được bao gồm hay không phụ thuộc vào quy ước được sử dụng.
Nêu quy ước trước khi sử dụng số tự nhiên trong một chứng minh, đặc tả hoặc chương trình.
Một số sách định nghĩa số tự nhiên bắt đầu từ 1, vì vậy hãy luôn kiểm tra quy ước.
This guide uses ℕ = {0, 1, 2, 3, ...}.Số nguyên và nền tảng
Absolute value
|a|Khoảng cách không âm từ một số nguyên đến số không trên trục số.
Sử dụng nó để biểu diễn độ lớn, khoảng cách, lỗi và các giới hạn đối xứng.
|-7| = 7 and |5 - 12| = 7.Số nguyên và nền tảng
Parity
n mod 2Tính chất của một số nguyên là chẵn hay lẻ.
Sử dụng tính chẵn lẻ cho việc phân nhánh, các mẫu xen kẽ, các chứng minh, kiểm tra tổng và logic mức bit.
18 mod 2 = 0, so 18 is even.Số nguyên và nền tảng
Division algorithm
a = bq + rVới các số nguyên a và b dương, tồn tại các số nguyên q và r duy nhất sao cho 0 ≤ r < b.
Sử dụng nó làm nền tảng cho các thuật toán chia, dư, Euclid và số học modulo.
29 = 6 × 4 + 5, so q = 4 and r = 5.Khả năng chia hết
Divisor
d | nMột số nguyên d là ước của n khi n = dk với một số nguyên k nào đó.
Sử dụng các ước số để phân tích cấu trúc thừa số, các ước số chung và khả năng chia hết chính xác.
6 | 42 because 42 = 6 × 7.Khả năng chia hết
Multiple
n = dkMột số thu được bằng cách nhân một số nguyên với một số nguyên khác.
Sử dụng các bội số cho lịch trình, các chu kỳ chung, các hệ thống tuần hoàn và căn chỉnh mẫu số.
Các bội số của 5 bao gồm 0, 5, 10, 15 và 20.Khả năng chia hết
Divisibility test
n mod d = 0Một quy tắc xác định xem một số nguyên có chia hết cho một số nguyên khác hay không mà không cần thực hiện phép chia dài.
Sử dụng nó để kiểm tra nhanh, tính toán số học trong đầu, xác thực đầu vào và dạy cấu trúc giá trị vị trí.
7,452 is divisible by 3 because 7 + 4 + 5 + 2 = 18.Khả năng chia hết
Greatest common divisor
gcd(a, b)Số nguyên dương lớn nhất chia hết cả hai số nguyên.
Sử dụng nó để giảm các phân số, kiểm tra tính nguyên tố, giải các phương trình đồng dư và tính toán tỷ lệ.
gcd(84, 30) = 6.Khả năng chia hết
Least common multiple
lcm(a, b)Số nguyên dương nhỏ nhất là bội số của cả hai số nguyên khác không.
Sử dụng nó để đồng bộ hóa các chu kỳ, kết hợp các phân số và tính toán các lịch trình lặp lại.
lcm(12, 18) = 36.Khả năng chia hết
GCD-LCM identity
gcd(a,b)lcm(a,b)=|ab|Một mối quan hệ kết nối ước số chung lớn nhất và bội số chung nhỏ nhất của hai số nguyên khác 0.
Sử dụng nó để tính toán một đại lượng một cách hiệu quả khi đại lượng kia đã biết.
gcd(12,18)=6, so lcm(12,18)=|12×18|/6=36.Khả năng chia hết
Euclidean algorithm
gcd(a,b)=gcd(b,a mod b)Một thuật toán chia hết lặp đi lặp lại để tìm ước số chung lớn nhất.
Sử dụng nó để tính toán nhanh GCD, ngay cả khi các số nguyên đầu vào lớn.
gcd(252,105) = gcd(105,42) = gcd(42,21) = 21.Khả năng chia hết
Extended Euclidean algorithm
ax + by = gcd(a,b)Một mở rộng của thuật toán Euclid cũng tìm các hệ số Bézout x và y.
Sử dụng nó để tính toán các nghịch đảo modulo và giải các phương trình Diophantine tuyến tính.
35×(-1) + 12×3 = 1, do đó -1 là hệ số của 35.Khả năng chia hết
Coprime integers
gcd(a,b)=1Hai số nguyên nguyên tố cùng nhau khi ước số chung lớn nhất của chúng là 1.
Sử dụng tính nguyên tố cùng nhau để xác định khả năng đảo ngược theo mô-đun n và để áp dụng định lý Euler.
8 và 15 là hai số nguyên tố cùng nhau ngay cả khi không có số nào là số nguyên tố.Số nguyên tố và phân tích thừa số
Prime number
pMột số nguyên lớn hơn 1 mà các ước dương duy nhất là 1 và chính nó.
Sử dụng các số nguyên tố làm khối xây dựng cơ bản của phân tích thừa số số nguyên và mật mã khóa công khai.
2, 3, 5, 7 và 11 là các số nguyên tố.Số nguyên tố và phân tích thừa số
Composite number
n = abMột số nguyên lớn hơn 1 có một ước dương khác 1 và chính nó.
Sử dụng nó để phân biệt các số nguyên có thể phân tích thành thừa số với các số nguyên tố.
21 is composite because 21 = 3 × 7.Số nguyên tố và phân tích thừa số
Prime factorization
n=∏pᵢ^aᵢViết một số nguyên dưới dạng tích của các lũy thừa của các số nguyên tố.
Sử dụng nó để tính toán các ước số, GCD, LCM và các hàm số học.
360 = 2^3 × 3^2 × 5.Số nguyên tố và phân tích thừa số
Fundamental theorem of arithmetic
n=∏pᵢ^aᵢMọi số nguyên lớn hơn 1 đều có một phân tích thành các số nguyên tố duy nhất theo thứ tự các thừa số.
Sử dụng nó để biện minh cho các thuật toán và chứng minh dựa trên các số mũ nguyên tố.
72 = 2^3 × 3^2 là phân tích nguyên tố duy nhất của 72.Số nguyên tố và phân tích thừa số
Sieve of Eratosthenes
Một thuật toán liệt kê các số nguyên tố lên đến một giới hạn bằng cách lặp đi lặp lại đánh dấu các bội số của mỗi số nguyên tố được tìm thấy.
Sử dụng nó khi nhiều truy vấn nguyên tố chia sẻ cùng một giới hạn trên vừa phải.
Để tìm các số nguyên tố nhỏ hơn 30, hãy đánh dấu các bội số của 2, 3 và 5.Số nguyên tố và phân tích thừa số
Primality test
Một thuật toán quyết định xem một số nguyên cho trước có phải là số nguyên tố hay không.
Sử dụng phép chia thử cho các đầu vào nhỏ và các kiểm tra xác suất như Miller-Rabin cho các đầu vào lớn.
Một phép kiểm tra số nguyên tố có thể yêu cầu nhiều vòng hoặc một tập cơ sở xác định cho phạm vi số nguyên dự định.
Phép chia thử nghiệm chỉ cần các ước số ứng cử viên lên đến √n.Số học modulo
Congruence
a ≡ b (mod n)Hai số nguyên đồng dư theo mô-đun n khi n chia hết hiệu của chúng.
Sử dụng nó để thay thế các số nguyên bằng các dư tương đương trong các phép tính tuần hoàn.
29 ≡ 5 (mod 12) vì 12 chia hết 29 - 5.Số học modulo
Residue class
[a]ₙTập hợp tất cả các số nguyên đồng dư với một số nguyên cố định theo mô-đun n.
Sử dụng nó để suy luận về các giá trị modulo như các lớp tương đương thay vì các số riêng lẻ.
[2]₅ = {..., -8, -3, 2, 7, 12, ...}.Số học modulo
Modulo operation
a mod nMột phép toán trả về phần dư đại diện sau khi chia cho n.
Sử dụng nó để bọc chỉ mục, đồng hồ, các ngăn băm và trạng thái tuần hoàn.
(23 + 5) mod 24 = 4.Số học modulo
Modular arithmetic
ℤ/nℤPhép toán được thực hiện trên các lớp dư với kết quả được giảm theo mô-đun n.
Sử dụng nó trong mật mã, lý thuyết mã, bộ đệm tuần hoàn và tính toán lịch.
(17 × 19) mod 12 = 11.Số học modulo
Modular inverse
a⁻¹ mod nMột giá trị x thỏa mãn ax ≡ 1 (mod n); nó tồn tại chính xác khi gcd(a,n)=1.
Sử dụng nó để chia trong số học modulo, giải các phương trình đồng dư và triển khai các thuật toán mật mã.
Không nên thực hiện phép chia modulo trước khi kiểm tra xem số chia có nguyên tố cùng nhau với số dư hay không.
3⁻¹ mod 7 = 5 because 3 × 5 ≡ 1 (mod 7).Số học modulo
Modular exponentiation
a^k mod nTính toán lũy thừa theo mô-đun n mà không cần xây dựng trước lũy thừa đầy đủ, có thể rất lớn.
Sử dụng bình phương lặp trong mật mã, kiểm tra tính nguyên tố và các bài toán có số mũ lớn.
3^13 mod 7 = 3 using repeated squaring.Số học modulo
Linear congruence
ax ≡ b (mod n)Một phương trình đồng dư, yêu cầu các số nguyên x thỏa mãn một phương trình mô-đun tuyến tính.
Sử dụng các điều kiện GCD và nghịch đảo mô-đun để xác định và tính toán các giải pháp.
3x ≡ 4 (mod 7) cho x ≡ 6 (mod 7).Số học modulo
Chinese remainder theorem
x ≡ aᵢ (mod nᵢ)Một định lý kết hợp các phương trình đồng dư tương thích, cho một nghiệm duy nhất theo mô-đun tích khi các mô-đun là nguyên tố cùng nhau theo cặp.
Sử dụng nó để kết hợp các ràng buộc tuần hoàn độc lập và tăng tốc tính toán số nguyên lớn.
x ≡ 2 (mod 3), x ≡ 3 (mod 5) cho x ≡ 8 (mod 15).Số học modulo
Euler's totient function
φ(n)Số lượng số nguyên từ 1 đến n mà số đó nguyên tố cùng nhau với n.
Sử dụng nó trong định lý Euler, các phép tính khóa RSA và các hệ dư giảm.
φ(12) = 4 vì 1, 5, 7, và 11 là các số nguyên tố cùng nhau với 12.Số học modulo
Euler's theorem
a^φ(n) ≡ 1 (mod n)Nếu a và n là nguyên tố cùng nhau, thì a mũ φ(n) cho 1 modulo n.
Sử dụng nó để giảm các số mũ, chứng minh các đẳng thức modulo và giải thích RSA.
gcd(3,10)=1 and φ(10)=4, so 3^4 ≡ 1 (mod 10).Số học modulo
Fermat's little theorem
a^(p-1) ≡ 1 (mod p)Đối với số nguyên tố p và a không chia hết cho p, a mũ p-1 đồng dư với 1 modulo p.
Sử dụng nó cho các nghịch đảo modulo theo một mô-đun nguyên tố và để kiểm tra tính nguyên tố.
Việc vượt qua một phép kiểm tra Fermat không chứng minh rằng một số là số nguyên tố vì các số giả nguyên tố tồn tại.
2^6 ≡ 1 (mod 7).Các nhóm cyclic và các phần tử sinh.
Group
(G, *)Một tập hợp có một phép toán kết hợp, một phần tử đơn vị và một phần tử nghịch đảo cho mọi phần tử.
Sử dụng các nhóm để mô tả các cấu trúc số học trong đó các phép toán có thể được kết hợp và đảo ngược.
Các số nguyên tạo thành một nhóm dưới phép cộng với phần tử đơn vị là 0 và nghịch đảo là -a cho a.Các nhóm cyclic và các phần tử sinh.
Abelian group
a*b=b*aMột nhóm mà phép toán là giao hoán.
Sử dụng nó cho phép cộng modulo, phép cộng vectơ và nhiều nhóm số học khác mà thứ tự phép toán không quan trọng.
(ℤ/nℤ, +) là một nhóm giao hoán.Các nhóm cyclic và các phần tử sinh.
Additive group modulo n
(ℤ/nℤ, +)Các lớp dư theo modulo n với phép cộng được thực hiện theo modulo n.
Sử dụng nó để mô hình hóa các bộ đếm cyclic, các trạng thái tuần hoàn và các lớp đồng dư theo phép cộng.
In ℤ/5ℤ, 3+4=2.Các nhóm cyclic và các phần tử sinh.
Multiplicative group of units
(ℤ/nℤ)×Các lớp dư tương đối nguyên tố với n, với phép nhân theo modulo n.
Sử dụng nó để nghiên cứu các nghịch đảo modulo, căn nguyên tố, định lý của Euler và mật mã khóa công khai.
(ℤ/8ℤ)×={1,3,5,7}.Các nhóm cyclic và các phần tử sinh.
Cyclic group
G=⟨g⟩Một nhóm mà mọi phần tử đều là lũy thừa hoặc tổng lặp lại của một phần tử.
Sử dụng nó để giảm một phép toán nhóm thành phép toán trên các số mũ hoặc bội số nguyên.
Nhóm cộng tính ℤ/6ℤ được sinh ra bởi 1 và 5.Các nhóm cyclic và các phần tử sinh.
Generator
⟨g⟩=GMột phần tử mà khi thực hiện phép toán nhóm lặp đi lặp lại, nó tạo ra mọi phần tử của một nhóm cyclic.
Sử dụng nó để liệt kê các nhóm cyclic và định nghĩa các hoạt động mật mã dựa trên số mũ.
Luôn chỉ rõ nhóm và phép toán vì một phần tử có thể tạo ra một cấu trúc nhưng không phải là một cấu trúc khác.
Các lũy thừa của 3 theo modulo 7 tạo ra 3,2,6,4,5,1, do đó 3 tạo ra (ℤ/7ℤ)×.Các nhóm cyclic và các phần tử sinh.
Order of an element
ord(g)Số nguyên dương nhỏ nhất k mà g^k là phần tử đơn vị.
Sử dụng nó để kiểm tra xem một phần tử có phải là một sinh viên hay không và để xác định độ dài chu kỳ.
Theo modulo 7, ord(2)=3 vì 2^3≡1 và không có số mũ dương nhỏ hơn nào hoạt động.Các nhóm cyclic và các phần tử sinh.
Primitive root
ordₙ(g)=φ(n)Một phần tử sinh của nhóm nhân của các đơn vị theo modulo n.
Sử dụng các căn nguyên để biểu diễn các phần dư khác 0 dưới dạng lũy thừa và để xây dựng các logarit rời rạc.
3 là căn nguyên tố theo modulo 7 vì bậc của nó là φ(7)=6.Các nhóm cyclic và các phần tử sinh.
Primitive root existence
Các căn nguyên thủy theo modulo n tồn tại chính xác cho n=1, 2, 4, p^k, hoặc 2p^k trong đó p là một số nguyên tố lẻ.
Sử dụng tiêu chí này trước khi tìm kiếm một căn nguyên modulo một số nguyên hợp.
Không có căn nguyên tố (primitive root) theo modulo 8 vì 8 không có các dạng cần thiết.Các nhóm cyclic và các phần tử sinh.
Discrete logarithm
g^x=hCho một phần tử sinh g và một phần tử của nhóm h, logarit rời rạc tìm một số mũ x sao cho g^x=h.
Sử dụng nó để hiểu các giả định bảo mật của Diffie-Hellman, ElGamal và đường elip.
Lôgarit rời rạc có thể dễ dàng trong các nhóm nhỏ hoặc được chọn không tốt và khó chỉ khi có các tham số phù hợp.
Theo modulo 7 với phần tử sinh là 3, log₃(5)=5 vì 3^5≡5.Các nhóm cyclic và các phần tử sinh.
Carmichael function
λ(n)Số mũ dương nhỏ nhất m sao cho a^m ≡ 1 modulo n với mọi a tương đối nguyên tố với n.
Sử dụng nó để có được một số mũ phổ quát chặt chẽ hơn so với φ(n) cho các lũy thừa modulo và phân tích RSA.
λ(8)=2 vì mọi số lẻ a đều thỏa mãn a²≡1 (mod 8).Các số dư bậc hai
Quadratic residue
x²≡a (mod n)Một số dư a mà phương trình x²≡a modulo n có nghiệm.
Sử dụng nó để phân tích căn bậc hai modulo, kiểm tra tính nguyên tố và mật mã dựa trên số dư bậc hai.
2 là một số dư bậc hai theo modulo 7 vì 3²≡2.Các số dư bậc hai
Quadratic nonresidue
Một số dư khác 0 mà không có nghiệm cho phương trình x²≡a modulo n.
Sử dụng nó để phân loại các dư và xây dựng các kiểm tra hoặc tham số mật mã với ký hiệu bậc hai đã biết.
3 là một số dư bậc hai không theo modulo 7.Các số dư bậc hai
Modular square root
x=√a mod nMột nghiệm x của phương trình x²≡a modulo n.
Sử dụng nó trong giải nén điểm, các thuật toán lý thuyết số và mật mã dựa trên dư.
Căn bậc hai của 2 theo modulo 7 là 3 và 4.Các số dư bậc hai
Legendre symbol
(a/p)Đối với một số nguyên tố lẻ p, một giá trị 0, 1 hoặc -1 cho biết khả năng chia hết cho p hoặc trạng thái số dư bậc hai theo modulo p.
Sử dụng nó để kiểm tra ký hiệu bậc hai và phát biểu tiêu chuẩn Euler và tính chất nghịch đảo bậc hai một cách ngắn gọn.
(2/7)=1 vì 2 là một số dư bậc hai theo modulo 7.Các số dư bậc hai
Jacobi symbol
(a/n)Một phần mở rộng nhân của ký hiệu Legendre cho các mẫu số lẻ hợp dương.
Sử dụng nó cho các phép tính ký tự hiệu quả và các thuật toán không yêu cầu phân tích thừa số của n trước.
Một ký hiệu Jacobi bằng 1 không đảm bảo rằng a là một số dư bậc hai theo modulo số nguyên tố hợp n.
(5/21)=(5/3)(5/7)=1.Các số dư bậc hai
Euler's criterion
a^((p-1)/2)≡(a/p) (mod p)Một tiêu chí xác định trạng thái số dư bậc hai theo modulo một số nguyên tố lẻ bằng cách sử dụng lũy thừa mô-đun.
Sử dụng nó để tính toán biểu tượng Legendre mà không cần liệt kê mọi bình phương.
Với p=7, 3^3≡-1 (mod 7), do đó 3 là một số không dư bậc hai.Các số dư bậc hai
Quadratic reciprocity
(p/q)(q/p)=(-1)^((p-1)(q-1)/4)Một định lý liên quan đến việc liệu một số nguyên tố lẻ có phải là một số dư bậc hai theo modulo một số nguyên tố khác hay không.
Sử dụng nó để giảm các phép tính biểu tượng Legendre lớn thành các phép tính nhỏ hơn.
Vì 3 và 11 đều đồng dư 3 theo modulo 4, (3/11)=-(11/3).Các số dư bậc hai
Supplementary laws
(-1/p), (2/p)Các công thức xác định tính chất dư bậc hai của -1 và 2 theo modulo một số nguyên tố lẻ.
Sử dụng chúng với tính chất đệ quy bậc hai để hoàn thành các phép tính biểu tượng Legendre.
(2/p)=1 khi p≡1 hoặc 7 (mod 8), và -1 khi p≡3 hoặc 5 (mod 8).Các số dư bậc hai
Tonelli-Shanks algorithm
Một thuật toán để tìm một căn bậc hai mô-đun của một số dư bậc hai theo modulo một số nguyên tố lẻ.
Sử dụng nó khi mô-đun là số nguyên tố và phương pháp đơn giản p≡3 modulo 4 không áp dụng.
Với p=13, thuật toán Tonelli-Shanks tìm x=6 hoặc 7 cho x²≡10 (mod 13).Các số dư bậc hai
Square roots modulo a composite
Các căn bậc hai theo modulo được tìm thấy theo các thừa số lũy thừa của số nguyên tố và kết hợp với định lý dư Trung Quốc.
Sử dụng nó để phân tích các hệ thống và phép đồng dư kiểu Rabin với các mô-đun hợp số.
Đối với một tích của các số nguyên tố lẻ khác nhau, một số dư có thể có nhiều căn bậc hai, vì vậy việc chọn căn bậc hai dự định đòi hỏi thông tin bổ sung.
Giải x²≡1 theo modulo 3 và 5, sau đó kết hợp các lựa chọn dấu theo modulo 15.Các phương trình nguyên
Diophantine equation
Một phương trình mà chỉ tìm các nghiệm là số nguyên.
Sử dụng khả năng chia hết, GCD, đồng dư và giới hạn để xác định xem có tồn tại các nghiệm nguyên hay không.
3x + 5y = 17 has the integer solution x = 4, y = 1.Các phương trình nguyên
Linear Diophantine equation
ax + by = cMột phương trình tuyến tính mà các ẩn số phải là số nguyên; các nghiệm tồn tại chính xác khi gcd(a,b) chia hết c.
Sử dụng nó cho việc phân bổ chính xác, các bài toán về tiền xu, lịch trình và các ràng buộc về lưới.
6x + 9y = 30 có nghiệm vì gcd(6,9)=3 chia hết 30.Ứng dụng
RSA arithmetic
c ≡ m^e (mod n)Toán học khóa công khai dựa trên phép lũy thừa mô-đun và độ khó của việc phân tích thừa số của một tích các số nguyên tố lớn.
Sử dụng nó để hiểu cách lý thuyết số hỗ trợ mã hóa và chữ ký số.
Các giá trị thử nghiệm chỉ dành cho mục đích học tập; RSA thực tế yêu cầu padding tiêu chuẩn, kích thước khóa an toàn và các thư viện đã được kiểm tra.
Với các giá trị ví dụ n=55, e=3, và m=7, c=7^3 mod 55=13.