Giải Thuật Euclide Mở Rộng - Học Nhau Lập Trình

Skip to content

Hôm nay chúng ta sẽ cùng tìm hiểu các thuật toán nhỏ để hỗ trợ cài đặt thuật toán RSA nhé, bây giờ là tới giải thuật Euclide mở rộng Giải thuật Euclide mở rộng Trong số học, nếu d=GCD(a, b) thì tồn tại các số nguyên x, y sao cho ax+by = d. Một trong những ứng dụng của giải thuật Euclide mở rộng là tìm số nghịch đảo trong vành Zm. Số nghịch đảo trong vành Zm Phần tử a của Zm được gọi là khả nghịch trong Zm hay khả nghịch theo modulo m nếu tồn tại phần tử a’ trong Zm sao cho a*a’=1 trong Zm hay a* a’ ≡ 1(mod m). Khi đó a’ được gọi là nghịch đảo modulo m của a. Trong lý thuyết số đã chứng minh rằng, số a là khả nghịch theo modulo m khi và chỉ khi GCD(a, m) = 1. Khi đó tồn tại các số nguyên x, y sao cho: mx + ay = 1. Đẳng thức này lại chỉ ra y là nghịch đảo của a theo modulo m. Do đó có thể tìm được phần tử nghịch đảo của a theo modulo m nhờ thuật toán Euclid mở rộng khi chia m cho a. Áp dụng giải thuật Euclide mở rộng vào tìm d trong giải thuật RSA Khi chọn số nguyên e sao cho 1 < e < ɸ(n) và GCD(e, ɸ(n)) = 1, ta cũng thực hiện tìm d sao cho de ≡ 1 (mod ɸ(n)). Áp dụng giải thuật Euclide mở vào d, e, ɸ(n) với d là nghịch đảo của e trong vành Zɸ(n): kɸ(n) + de = GCD(e, ɸ(n)) = 1, với k là một nguyên bất kỳ thỏa phương trình Như vậy khi giải phương trình trên ta sẽ tìm ra được d theo yêu cầu của thuật toán RSA.

Share this:

• X
• Facebook

Like Loading...

• Uncategorized

Leave a comment Cancel reply

Δ

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use. To find out more, including how to control cookies, see here: Cookie Policy

• Comment
• Reblog
• Subscribe Subscribed
  • Học Nhau Lập Trình - Cùng nhau phát triển
  Sign me up
  • Already have a WordPress.com account? Log in now.
• • Học Nhau Lập Trình - Cùng nhau phát triển
  • Subscribe Subscribed
  • Sign up
  • Log in
  • Copy shortlink
  • Report this content
  • View post in Reader
  • Manage subscriptions
  • Collapse this bar

%d Design a site like this with WordPress.comGet started