Yếu tố Pollard-Rho Song song

Question

Gần đây tôi tình cờ gặp a paper trên song song Pollard's Rho algorithm và cho ứng dụng cụ thể của tôi, ngoài thực tế là tôi chưa đạt được mức yêu cầu của toán học, tôi tự hỏi phương pháp giúp trường hợp cụ thể của tôi.

Tôi đang cố gắng tìm hai yếu tố — semiprimes — của một số rất lớn. Giả định của tôi, dựa trên những gì tôi có thể hiểu được của bài báo, là sự song song này hoạt động tốt trên một số với nhiều yếu tố nhỏ hơn, chứ không phải là hai yếu tố rất lớn.

Điều này có đúng không? Tôi có nên sử dụng song song này hoặc sử dụng cái gì khác không? Tôi có nên sử dụng Rho của Pollard hay không, có một sự song song tốt hơn về một thuật toán hệ số hóa khác không?

Answer 1

Ý tưởng cơ bản trong việc bao thanh toán các số nguyên lớn là sử dụng nhiều phương pháp khác nhau, mỗi phương pháp có các điểm cộng và phép trừ riêng. Kế hoạch thông thường là bắt đầu với phân chia thử nghiệm bằng các số nguyên tố lên 1000 hoặc 10000, tiếp theo là một vài triệu bước rho Pollard; mà nên giúp bạn có được các yếu tố lên đến khoảng mười hai chữ số. Tại thời điểm đó, một vài bài kiểm tra theo thứ tự: là số nguyên tố hoặc một sức mạnh hoàn hảo (có những bài kiểm tra đơn giản cho những thuộc tính đó). Nếu bạn vẫn chưa tính số lượng, bạn biết rằng nó sẽ khó, vì vậy bạn sẽ cần các công cụ hạng nặng. Bước tiếp theo hữu ích là phương pháp p-1 của Pollard, tiếp theo là anh em họ của nó là phương pháp đường cong elip. Sau một thời gian, nếu điều đó không hiệu quả, các phương pháp duy nhất còn lại là rây bậc hai hoặc rây trường số, vốn vốn song song.

Phương pháp rho song song mà bạn đã hỏi không được sử dụng rộng rãi ngày nay. Như bạn đã đề xuất, Pollard rho phù hợp hơn với việc tìm kiếm các yếu tố nhỏ hơn là tìm các yếu tố lớn. Đối với một bán chính, nó tốt hơn để chi tiêu chu kỳ song song trên một trong những sàng hơn trên Pollard rho.

Tôi đề xuất diễn đàn bao thanh toán tại mersenneforum.org để biết thêm thông tin.

Answer 2

Các bài viết wikipedia khẳng định hai ví dụ cụ thể:

Number    Original code  Brent's modification 
18446744073709551617 26 ms    5 ms 
10023859281455311421 109 ms    31 ms 

Trước hết, chạy hai với chương trình của bạn và có một cái nhìn vào những thời điểm của bạn. Nếu chúng tương tự như vậy (số "cứng" tính 4-6 lần), hãy tự hỏi liệu bạn có thể sống với điều đó không. Hoặc thậm chí tốt hơn, sử dụng các thuật toán khác như hệ số "lực lượng vũ phu" cổ điển đơn giản và nhìn vào thời điểm chúng cung cấp. Tôi đoán họ có thể có một yếu tố dễ dàng gần hơn với 1, nhưng thời gian tuyệt đối tồi tệ hơn, vì vậy nó là một sự cân bằng đơn giản.

Lưu ý phụ: Tất nhiên, song song là cách để đi đến đây, tôi đoán bạn biết điều đó nhưng tôi nghĩ điều quan trọng là phải nhấn mạnh. Ngoài ra, nó sẽ giúp cho trường hợp một cách tiếp cận khác là giữa thời gian Pollard-rho (ví dụ Pollard-Rho 5-31 ms, cách tiếp cận khác nhau 15-17 ms) - trong trường hợp này, hãy xem xét chạy 2 thuật toán trong các chuỗi riêng biệt để làm một "cuộc đua nhân tố hóa".

Trong trường hợp bạn chưa thực hiện thuật toán thực tế, dưới đây là Python implementations.