Các phương pháp mã hóa và bảo mật thông tin- P4: Thế kỷ XXI thế kỷ công nghệ thông tin, thông tin đã và đang tác động trực tiếp đến mọi mặt hoạt động kinh tế xã hội của hầu hết các quốc gia trên thế giới. Thông tin có một vai trò hết sức quan trọng, bởi vậy chúng ta phải làm sao đảm bảo được tính trong suốt của thông tin nghĩa là thông tin không bị sai lệch, bị thay đổi, bị lộ trong quá trình truyền từ nơi gửi đến nơi nhận | Upload by L a p 0 nếu a chia hết cho p. L a p 1 nếu a là thặng dư bậc 2 mod p. L a p -1 nếu a không thặng dư mod p. Một phương pháp dễ dàng để tính toán ra L a p là L a p a p-1 2 mod p Ký hiệu Jacobi Jacobi Symboy Ký hiệu Jacobi được viết J a n nó là sự khái quát hoá của ký hiệu Lagrăng nó định nghĩa cho bất kỳ cặp số nguyên a và n. Ký hiệu Jacobi là một chức năng trên ập hợp số thặng dư thấp của ước số n v à có tlể tính toán theo công thức sau Nếu n là số nguyên tố thì J a n 1 với điều kiện a là thặng dư bậc hai modulo n . Nếu n là số nguyên tố thì J a n -1 với điều kiện a không là thặng dư bậc hai modulo n . Nếu n không phải là số nguyên tố thì Jacobi J a n J h p1 X J h p2 X. . . X J h pm với p1 p2. . . pm là các thừa số lớn nhất của n. Thuật toán này tính ra số Jacobi tuần hoàn theo công thức sau 1. J 1 k 1 2. J axb k J a k X J b k 3. J 2 k 1 Nếu k2-1 8 là chia hết J 2 k -1 trong các trường hợp khác. 4. J b a J b mod a a 5. Nếu GCD a b 1 a. J a b X J b a 1 nếu a-1 b-1 4 là chia hết. b. J a b X J b a -1 nếu a-1 b-1 4 là còn dư. Trang 16 Upload by Sau đây là thuật toán trong ngôn ngữ C int jacobi int a int b int a1 a2 if a b a b if a 0 return 0 if a 1 return 1 if a 2 if b b-1 8 2 0 return 1 else return -1 if a b 1 cả a và b đều là số dư if a-1 b-1 4 2 0 return jacobi b a else return -jacobi b a if gcd a b 1 if a-1 b-1 4 2 0 return jacobi b a else return -jacobi b a factor2 a a1 a2 return jacobi a1 b jacobi a2 b Nếu p là số nguyên tố có cách tốt hơn để tính số Jacobi như dưới đây 1. Nếu a 1 thì J a p 1 2. Nếu a là số chai hết thì J a p J a 2 p X -1 pA2 -1 8 3. Nếu a là số dư khác 1 thì J a p J p mod a a X -I a-1 x p-1 4 Trang 17 Upload by Định lý phần dư trung hoa. Nếu bạn biết cách tìm thừa số nguyên tố của một số n thì bạn có thể đã sử dụng một số điều gọi là định lý phần dư trung hoa để giải quyết trong suốt hệ phương trình. Bản dịch cơ bản của đinh lý này được khám phá bởi toán học Trung Hoa vào thế kỷ thứ .
