Máy tính Ký hiệu Legendre

Giới thiệu về công cụ này

Ký hiệu Legendre (a/p), được định nghĩa cho một số nguyên a và một số nguyên tố lẻ p, là một cách gọn để trả lời một câu hỏi cơ bản của lý thuyết số: đồng dư thức x² ≡ a (mod p) có nghiệm không? Công cụ này tính nó bằng tiêu chuẩn Euler: (a/p) ≡ a^((p-1)/2) (mod p), bằng 1 nếu a là thặng dư bình phương mod p, −1 nếu nó là phi thặng dư, và 0 nếu p chia hết a.

Ký hiệu Legendre là một khối xây dựng của lý thuyết thuận nghịch bình phương và xuất hiện khắp lý thuyết số tính toán và mật mã học — gồm các phép kiểm tra nguyên tố, các thuật toán tính căn bậc hai theo mô đun, và các cấu trúc trong mật mã đường cong elliptic — ở bất cứ nơi nào việc một số có phải là số chính phương theo modulo một số nguyên tố hay không là điều quan trọng.