Bài toán tìm phần tử sinh. Xin chào mọi người. Hôm nay thầy giáo mình có nói về bài toán giải logarit rời rạc hay tìm x để a^x = b (mod p). Trong đó có một thuật giải khá hay là Baby-step Giant-step. Trong thuật giải này có một bước đi tìm phần tử sinh g thỏa mãn g^p = p-1 (mod p). Mình tìm mãi trên mạng ko thấy có. Nên h mong mọi người giúp đỡ. Cảm ơn. |
Mình không biết cái thuật toán Baby-step Giant-step là cái nào cả. để mình xem lại sau nhưng có vẻ cái bước cuối bạn nói không được đúng cho lắm vì dùng dịnh lí fermat nhỏ thì g^p=g (mod p) nên tìm được g=p-1 .chắc là bạn nhầm gì đó đúng không? nhưng bài toán bạn đưa ra hay quá có gì mình sẽ trao đổi với bạn nhé.được chứ? (em rảnh nên chỉ đi nhặt sạn thôi, có gì các mod đừng bảo em spam gì lung tung nhé) |
Xin lỗi sondx89 mình tra trên wikipedia nhưng không thấy cái cái link nào nói rõ thuật toán baby-step Giant-step bạn có thể chỉ cho mình được không? còn bài toán của bạn thì sẽ giải như sau, mình nói qua và các bạn thử nhé: lấy g là phần tử sinh nhóm Zp.khi đó a=g^h , b=g^k (h,k bây giờ thì rõ rồi). pt sau: g^(hx)=g^k. suy ra hx-k=0 mod p-1 ??? như vậy là ra rồi.như vậy có đúng không? viết thuật toán thì mình chịu, vì minh không biết gì về tin lắm. |
Trích:
|
Múi giờ GMT. Hiện tại là 01:34 PM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.