Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Đại Học Và Sau Đại Học/College Playground > Lý Thuyết Số/Number Theory

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 23-09-2010, 11:20 PM   #1
sondx89
+Thành Viên+
 
Tham gia ngày: Sep 2010
Bài gởi: 1
Thanks: 0
Thanked 0 Times in 0 Posts
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
sondx89 is offline   Trả Lời Với Trích Dẫn
Old 15-04-2011, 01:32 AM   #2
cuchuoi
+Thành Viên+
 
Tham gia ngày: Apr 2011
Bài gởi: 31
Thanks: 14
Thanked 27 Times in 3 Posts
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é)
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
cuchuoi is offline   Trả Lời Với Trích Dẫn
Old 15-04-2011, 04:29 AM   #3
cuchuoi
+Thành Viên+
 
Tham gia ngày: Apr 2011
Bài gởi: 31
Thanks: 14
Thanked 27 Times in 3 Posts
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.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
cuchuoi is offline   Trả Lời Với Trích Dẫn
Old 15-04-2011, 07:48 AM   #4
thanhthuy
+Thành Viên+
 
thanhthuy's Avatar
 
Tham gia ngày: Aug 2010
Bài gởi: 47
Thanks: 11
Thanked 43 Times in 24 Posts
Trích:
Nguyên văn bởi sondx89 View Post
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. ]. 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. ].
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
thanhthuy is offline   Trả Lời Với Trích Dẫn
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


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


Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 48.65 k/53.99 k (9.89%)]