Tham gia Đăng nhập
Điểm:1
avatar Crypto

Cách chọn Smoothness Bound phù hợp khi sử dụng phương pháp Index Calculus

lá cờ et
user93353

Trong khi triển khai Sàng bậc hai, sách giáo khoa đưa ra một công thức sơ bộ về giới hạn Độ mịn mà bạn nên sử dụng trong Cơ sở hệ số của mình.

Để phân tích một số N bằng cách sử dụng Sàng bậc hai, chúng ta có thể sử dụng như sau:

$L = e^{\sqrt {\ln(N)ln(ln(N))}}$, $B = L^{\frac {1}{\sqrt 2}}$

Đối với phương pháp tính chỉ số để giải bài toán Nhật ký rời rạc trong $\mathbb F_p$, có công thức tương tự không? Nhiều văn bản tôi đã kiểm tra, chỉ nói chọn một Giới hạn độ mịn thích hợp B. Nhưng không đưa ra bất kỳ dấu hiệu nào về cách một người chọn một B thích hợp.

117
1 + 0
Điểm:1
avatar Crypto
lá cờ pe
Samuel Neves

Coppersmith, Odlyzko và Schroeppel thiết lập ban đầu $B = L[1/2, 1/2]$ cho cả sàng tuyến tính và Gaussian. sức mạnh bộ $B = L[1/2, 1/\sqrt{2}]$ cho một biến thể tính toán chỉ số nghiêm ngặt sử dụng phương pháp đường cong elip làm phương pháp kiểm tra độ trơn.

Các giới hạn này chỉ tiệm cận; giới hạn trong một triển khai thường sẽ được điều chỉnh để tính đến hiệu suất không tiệm cận thực sự của các chương trình con liên quan.

0 + 7
lá cờ et
user93353
Tôi đã thử công thức này với một số ví dụ đã giải trong một số cuốn sách và kết quả có vẻ khác với những gì các ví dụ đã sử dụng. Ví dụ:trong cuốn sách mật mã toán học của Silverman, anh ấy giải được $37^x \equiv 211 \pmod 18443$. Nếu tôi sử dụng công thức $B = L^{\frac {1}{\sqrt 2}}$, tôi nhận được 28,5. Tuy nhiên, để giải quyết vấn đề, Silverman sử dụng B=5, cách khá xa so với B tính được. Silverman cũng có một bài toán bài tập $17^x \equiv 19 \pmod 19079$, trong đó B tính được sẽ là 28,5, nhưng tôi có thể để giải quyết nó một lần nữa bằng cách sử dụng B=5.
0
Hồi đáp
lá cờ et
user93353
Ý của bạn là gì khi `với các lần hủy bỏ sớm, với tư cách là người kiểm tra độ mịn.`?
0
Hồi đáp
lá cờ et
user93353
Tại sao lại có 2 công thức tức là tại sao $B = L[1/2, 1/\sqrt{2}]$ - $L^{1/2}$ là gì
0
Hồi đáp
lá cờ pe
Samuel Neves
Nếu bạn đang xem cuốn sách của Silverman, phần cuối của Phần 3.8 ở trang 169 sẽ trả lời câu hỏi của bạn. Đừng chú ý nhiều đến các tham số trong các ví dụ, chúng được tối ưu hóa cho sự rõ ràng hơn là hiệu suất (tức là, sẽ tệ hơn nếu một ví dụ hoạt động có quá nhiều số nguyên tố, cần nhiều quan hệ hơn, v.v.)
0
Hồi đáp
lá cờ pe
Samuel Neves
$L[1/2, 1/\sqrt{2}]$ là [ký hiệu L] chung chung hơn(https://en.wikipedia.org/wiki/L-notation). Nó có nghĩa giống như $L^{1/\sqrt{2}}$ của bạn.
0
Hồi đáp
lá cờ et
user93353
Cảm ơn bạn - bạn cũng có thể cho tôi biết ý của bạn khi nói `với các lần hủy bỏ sớm, với tư cách là người kiểm tra độ mượt.`
0
Hồi đáp
lá cờ pe
Samuel Neves
Đừng bận tâm đến điều đó, tôi đã nhầm lẫn điều này với một tờ báo Pomerance khác. Ở đây nó chỉ là ECM. Nhưng điều đó không quan trọng lắm; bộ phận dùng thử cũng sẽ hoạt động, với thời gian chạy kém hơn một chút.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.