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

Sàng bậc hai: Sàng với lũy thừa nguyên tố

lá cờ et
user93353

Tôi đang cố gắng hiểu thuật toán Sàng bậc hai.

Hiện tại tôi đang bị kẹt ở phần sàng lọc.

Giả sử số được phân tích thành nhân tử là 9788111. Tôi quyết định tìm các thừa số 50 trơn. Cơ sở yếu tố ban đầu của tôi (FB) = $p_i$ = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}.

Tôi xem qua từng số trong FB và quyền hạn của chúng.

Đối với mỗi số trong FB, trước tiên tôi kiểm tra xem N có phải là số dư bậc hai hay không (tức là N có phải là QR không $\pmod {p_i}$. Nếu đúng thì tôi tìm về cội nguồn.

Đối với 2, việc kiểm tra xem N có phải là QR hay không là chuyện nhỏ $\pmod 2$. Bạn cũng có thể mở rộng giá trị này cho lũy thừa 2. Đối với các số nguyên tố khác, bạn có thể sử dụng Tiêu chí Euler về Dư lượng bậc hai để kiểm tra xem N có phải là QR không $\pmod {p_i}$. Nếu là QR thì bạn có thể dùng Tonelli-Shanks để tìm gốc rồi sàng bằng gốc đó.

Tôi phải làm gì cho quyền lực chính? Đối với e.q. $5^2$, làm cách nào để kiểm tra nếu $t^2 \equiv N \pmod {5^2}$ có một giải pháp? Có bất kỳ bài kiểm tra hoặc quy tắc nào để kiểm tra điều này trước khi tôi thử tìm thư mục gốc không?

Đối với các cường quốc nhỏ như $5^2$, có thể tìm kiểm tra thủ công nếu N là QR $\pmod {{p_i}^n}$, nhưng làm thế nào để bạn làm điều đó cho các lũy thừa nguyên tố lớn hơn?

102
1 + 0
Điểm:3
fgrieu avatar Crypto
lá cờ ng
fgrieu

Nhớ lại rằng Sàng bậc hai (cơ bản) yêu cầu tìm một số $x$ với $x^2-N$ mịn màng. Hướng tới đó, nó thêm logarit (tỷ lệ, gần đúng) của $p_i$ thành ước số nhỏ ${p_i}^m$ của $x^2-N$ trong chỉ mục $x>0$ của một mảng. Điều này tương đối nhanh, bởi vì chỉ có hai trong số ${p_i}^m$ các mục trong mảng cần phải được chạm vào cho mỗi ${p_i}^m$.

Phải làm gì đối với quyền hạn nguyên tố (nghĩa là, ${p_i}^m$ vì $m>1$)?

Tùy chọn lười biếng và không tối ưu là bỏ qua chúng trong giai đoạn sàng, bù lại bằng ngưỡng mịn thấp hơn và/hoặc nhiều số nguyên tố hơn trong cơ sở.

Một lựa chọn tốt hơn là giải quyết $x^2\equiv N\pmod{{p_i}^m}$, sau đó sàng cho ${p_i}^m$ như chúng tôi đã làm cho $p_i$. Đối với số nguyên tố lẻ $p_i$, chúng tôi đã giải quyết $x\equiv N\pmod{p_i}$, nói rằng nó có (hai) giải pháp $x_j\in[0,p_i)$. (hai) giải pháp của $x^2\equiv N\pmod{{p_i}^m}$ Trong $[0,{p_i}^m)$ là $${x_j}^{({p_i}^{m-1})}\cdot N^{({p_i}^m - 2{p_i}^{m-1} + 1)/2}\bmod { p_i}^m$$

Dickson thuộc tính cái này cho Tonelli. tôi đã sử dụng câu trả lời này như một bồi dưỡng. Công thức cũng vậy trong Wikipedia, với các ví dụ.

0 + 4
lá cờ et
user93353
Cảm ơn bạn. Đối với $p$ số nguyên tố lẻ, nếu $x^2 \equiv N\pmod p$ có nghiệm, thì có đảm bảo rằng $x^2 \equiv N\pmod {p^m}$ cũng có nghiệm không. Tôi biết điều này không đúng với lũy thừa của 2. Nhưng nó có giống với các số nguyên tố lẻ hay nó được đảm bảo?
0
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
@ user93353: Có, đối với số nguyên tố lẻ $p$, nếu $x^2\equiv N\pmod p$ có nghiệm, thì có đảm bảo rằng $x^2\equiv N\pmod {p^m}$ cũng có một giải pháp. Có nhiều nhất hai, modulo $p^m$.
0
Hồi đáp
lá cờ et
user93353
Tuyệt quá! Tôi đoán rằng tôi đã cho rằng nó không phải (giống như nó không dành cho lũy thừa 2).Toàn bộ câu hỏi của tôi trở nên vô nghĩa nếu nó được đảm bảo. Có bằng chứng hay định lý nào cho thấy điều này không? Một tài liệu tham khảo trong một số cuốn sách?
0
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
@ user93353: Nguồn Dickson (chính nó trích dẫn Tonelli) ở cuối câu trả lời của tôi là nguồn tốt nhất mà tôi tìm thấy cho đến nay. [Ghi chú của HAC 3.41](https://cacr.uwaterloo.ca/hac/about/chap3.pdf#page=16) nói rằng thật dễ dàng để tìm căn bậc hai trong một trường có thứ tự lũy thừa nguyên tố, do đó bao gồm modulo một số nguyên tố sức mạnh, nhưng thật không may, sự biện minh bằng cách sử dụng thực tế 3.42 và phương pháp, dường như chỉ bao gồm số nguyên tố 2. Có thể có bằng chứng trực tiếp về công thức của Tonelli (trong câu trả lời của tôi), bằng cách bình phương và đơn giản hóa.
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.