Sàng bậc hai: Có quy tắc ngón tay cái để quyết định có bao nhiêu số để sàng không?

Trong Sàng bậc hai thuần túy, chúng ta cần tìm thêm một chút quan hệ (tương đương, làm mịn) so với số nguyên tố trong cơ sở nhân tử. Trong này, chúng tôi đếm các số nguyên tố nhỏ $p_i$ điều đó làm cho $N$ một modulo dư bậc hai $p_i$, không phải quyền hạn của họ. Số lượng này cũng là số lượng cột trong ma trận quan hệ (thưa thớt), trong đó quan hệ là các dòng, đóng vai trò là đầu vào cho giai đoạn đại số tuyến tính. Thông thường, nhiều hơn 5 dòng so với cột là đủ. Mỗi mối quan hệ bổ sung tiếp theo làm giảm xác suất thất bại xuống hai lần.

Điều này đưa ra một tiêu chí làm việc để ngừng sàng lọc và bắt đầu đại số tuyến tính, nhưng không trực tiếp cho biết chúng ta sẽ cần sàng lọc bao nhiêu số nguyên. Quy tắc ngón tay cái cho điều đó và các tham số khác, phụ thuộc vào nhiều thứ, bao gồm

• Điều quan trọng là nếu chúng ta sàng lọc một (QS) hoặc nhiều đa thức (MPQS/SIQS). Với QS, điều thường xảy ra là đa thức phát triển đến các giá trị quá cao, do đó, việc làm trơn trở nên hiếm gặp; sau đó, mở rộng sàng hoặc sử dụng lại sàng để sàng xa hơn trên cùng một đa thức sẽ không giúp được gì nhiều.
• Chiến lược w.r.t. các giá trị đa thức mà chúng tôi không chắc chắn (hoặc rất tin tưởng), bằng cách tổng hợp nhật ký các thừa số của chúng được tìm thấy bằng cách sàng, rằng chúng đủ mịn cho mục đích của chúng tôi. Chúng ta có thể
  • Bỏ qua chúng, thậm chí nghĩ rằng chúng vẫn có thể $B$-mịn màng.
  • Hãy thử các thừa số nguyên tố nhỏ cho đến các thừa số nguyên tố cao nhất đã sàng $B$, và sức mạnh của họ ngay cả khi họ vượt quá $B$ (nói cách khác, chúng tôi hạn chế $B$-các giá trị mịn của đa thức đã vượt qua bước sàng); điều đó thật dễ dàng và điển hình cho QS (MP/SI) cơ bản.
  • Hãy thử các yếu tố nhỏ lên đến một số giới hạn cao hơn $B'$ (nói cách khác, chúng ta sàng lọc các lũy thừa nguyên tố và nguyên tố để $B<B'$, và hạn chế $B'$-smooths đã qua bước sàng).
  • Ngoài ra, cho phép một thừa số nguyên tố lớn (PMPQS) đạt đến một số giới hạn cao hơn, với hy vọng rằng một xung đột đối với các số nguyên tố lớn này sẽ cho phép hai quan hệ không sử dụng được theo cách khác mang lại một mối quan hệ mới có thể sử dụng được (nghĩa là không có số nguyên tố lớn, để nó phù hợp với số lượng cột giới hạn trong ma trận)
  • Ngoài ra, cho phép hai thừa số nguyên tố lớn (PPMPQS).
• Ngưỡng sàng lọc (đối với tổng nhật ký các số nguyên tố được tích lũy trong mục sàng lọc), là sự thỏa hiệp giữa việc loại bỏ $B$-smooths, và dành quá nhiều thời gian vào việc cố gắng phân tích các ứng cử viên không mang lại các mối quan hệ có thể sử dụng được.

Các đề xuất để QS hoạt động:

• Đầu tiên làm cho một cái gì đó xử lý khiêm tốn $N$ không có một mảng sàng!
  • Sử dụng hệ số nhân tử của $p_i$ chế tạo $N$ một dư lượng bậc hai, lên đến một số giới hạn $B$. Sai lầm đầu tiên ở khía cạnh tối ưu lớn sẽ an toàn hơn $B$.
  • Tìm thấy $B$-làm trơn giữa các giá trị của đa thức $t^2-N$ với $t\gtrsim\left\lceil\sqrt N\,\right\rceil$ bằng cách cơ bản nhất (ví dụ: phép chia thử).Tìm một số mịn hơn một chút so với số nguyên tố.
  • Lấy đại số tuyến tính làm việc với nhân tử $N$.
• Tối ưu hóa hầu hết (hoặc tất cả) các bộ phận dùng thử của $t^2-N$ bằng một bài kiểm tra mà $t\bmod(p_i^k)$ rơi vào một tập hợp thành hai giá trị được tính toán trước.
• Ở giai đoạn đó, nút thắt cổ chai sẽ được thông suốt bằng cách cố gắng phân tích đầy đủ nhiều yếu tố $t^2-N$ sử dụng phân chia thử nghiệm (được tối ưu hóa), với hầu hết kết quả là không $B$-mịn màng. Giới thiệu mảng sàng lọc, với mục đích là (đáng kể) giảm số lượng ứng cử viên sáng giá, với cái giá phải trả là từ chối sai một vài ứng viên (sàng lọc các lũy thừa nguyên tố giúp hiếm khi từ chối sai). Điều này cho phép tăng $N$ (do đó nâng cao tối ưu $B$).
• Giới thiệu lần lượt các tối ưu hóa khác:
  • đang có $-1$ trong cơ sở yếu tố, đó cũng là sàng lọc $N-t^2$ vì $t\lesssim\left\lfloor\sqrt N\,\right\rfloor$
  • cải thiện "số nhân" dễ dàng, yếu tố nào $m\,N$ cho một số số nguyên nhỏ đã chọn $m$, sao cho cơ sở thừa số được cải thiện (có tương đối nhiều số nguyên tố nhỏ)
  • sử dụng nhiều đa thức, cho phép sàng lọc và phân tích các ứng cử viên nhỏ hơn nhiều, do đó có nhiều khả năng $B$-làm mịn
  • nút thắt cổ chai vẫn có thể được cố gắng nhân tố hóa các chất mịn đã vượt qua bài kiểm tra sàng (tùy thuộc vào ngưỡng trong sàng và kích thước của cơ sở nhân tố); một số khoản tiết kiệm có thể thực hiện được bằng cách chỉ sử dụng phép chia thử nghiệm (được tối ưu hóa) cho các số nguyên tố nhỏ, sau đó là thứ gì đó tốt hơn, có lẽ là Pollard's rho với phép thử tính nguyên tố khi nó không mang lại kết quả nhanh chóng; thử nghiệm như vậy sẽ cần thiết cho (các) cải tiến lớn.
  • một rồi hai cải tiến lớn (PMPQS và PPMPQS).
• Tối ưu hóa bất kể nút cổ chai là gì và điều chỉnh nhiều tham số. Cuối cùng, nút cổ chai nên được sàng lọc. Việc triển khai được tối ưu hóa đòi hỏi rất nhiều nỗ lực ở đó, với các kỹ thuật và mã chuyên biệt theo kích thước của các số nguyên tố được sàng lọc và tương tác với (các) bộ đệm CPU.