Diễn Đàn MathScope

Diễn Đàn MathScope (http://forum.mathscope.org/index.php)
-   Lý Thuyết Số/Number Theory (http://forum.mathscope.org/forumdisplay.php?f=131)
-   -   Bài toán tìm phần tử sinh. (http://forum.mathscope.org/showthread.php?t=13571)

sondx89 23-09-2010 11:20 PM

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.

cuchuoi 15-04-2011 01:32 AM

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é)

cuchuoi 15-04-2011 04:29 AM

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.

thanhthuy 15-04-2011 07:48 AM

Trích:

Nguyên văn bởi sondx89 (Post 65793)
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.

Bạn có thể tham khảo một số slide ở [Only registered and activated users can see links. Click Here To Register...]. Trong sage cũng có lệnh tìm căn nguyên thủy. Rồi làm như bạn cuchuoi cũng được. Nhưng nói chung là về mặt thuật toán thì làm theo vòng lặp có vẻ tiết kiệm được dung lượng hơn. Vì ở đây nếu làm theo kiểu phần tử sinh thì sẽ mất đến 3 bước. Tham khảo thêm trên trang của GS Ngô Quang Hưng về bài viết về hàm log rời rạc ở [Only registered and activated users can see links. Click Here To Register...].


Múi giờ GMT. Hiện tại là 01:34 PM.

Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.

[page compression: 6.42 k/6.84 k (6.17%)]