Khi nào một nửa nguyên tố lớn có thể được phân tích?

Trong điều kiện nào là một nửa nguyên tố lớn có thể phân tích? Đặc biệt, nửa nguyên tố 400 chữ số sau đây có thực sự tầm thường để phân tích thành các số nguyên tố không?

6962155154859963260211100482357357666900094513013513488352858667799199787495340476167566639530574848375895722792291996203873323650274512138128403360943634134259376986501375967452208380337012919869885380406071772232795575963202558402893589313281327208179913789760736615950818685956393838601277519011418885197723428318400763080858914698836058070301404903262955501113318317950597435778777212408626799143

"Tầm thường" gần như chắc chắn là từ sai cho điều này. Một câu hỏi hay hơn là liệu nó có hợp lý để tính hiệu quả hay không. Đầu tiên, điều đáng nói là bán nguyên tố của bạn là 400 số thập phân chữ số. Nhân cái này với $\log_2(10)$, chúng ta thấy rằng đó là $\khoảng 1300$ bit dài. Con số này lớn hơn rất nhiều so với kỷ lục bao thanh toán lớn nhất được tuyên bố (của các số nguyên tố) của 829 bit. Vì vậy, câu trả lời là "không", trừ khi dấu chấm phẩy của bạn có cấu trúc đặc biệt khiến nó trở nên "yếu".

Các số bán nguyên tố có thể có cấu trúc đặc biệt nào? Để cho $N = p_1p_2$ là thừa số hóa. Có một vài ứng cử viên, hoạt động nếu

1. Một trong những $p_i$ Là bé nhỏ (nói nhiều nhất $\khoảng 60$ bit), thì phương pháp đường cong elip là hợp lý để chạy.

2. Một trong những $p_i$ là như vậy $p_i+1$ Là mịn màng, ví dụ. tất cả các thừa số nguyên tố của $p_i+1$ được giới hạn bởi một số khá nhỏ $B$. sau đó của William $p+1$ thuật toán là hợp lý.

3. Một trong những $p_i$ là như vậy $p_i-1$ Là quyền hạn, ví dụ. tất cả số nguyên tố sức mạnh các yếu tố của $p_i-1$ được giới hạn bởi một số khá nhỏ $B$. sau đó thăm dò ý kiến $p-1$ thuật toán là hợp lý.

Có thể có một vài "cấu trúc đặc biệt" khác mà tôi đang thiếu (tôi dường như nhớ một cái nếu $p_1\khoảng p_2$, nhưng không thể nhớ tên bây giờ). Tuy nhiên, cơ hội thực sự duy nhất của bạn để bao thanh toán số là nó được tạo không đúng cách, mà tất cả những điều trên sẽ là ví dụ, vì vậy trừ khi bạn có lý do cụ thể để nghĩ rằng chúng được tạo không đúng cách (giả sử đây là một thách thức CTF), tôi sẽ Đừng bận tâm cố gắng để phá vỡ nó.

Nếu bạn có lý do để nghĩ rằng điều này nên được tạo không đúng cách, thì việc triển khai những điều này tồn tại. Ví dụ, Hiền nhân đã triển khai ECM (thông qua GMP-ECM). bên trong GMP-ECM chính trang đó, tôi cũng thấy các tham chiếu đến $p-1$ và $p+1$, nhưng tôi không biết liệu sage có trực tiếp thử những thứ này hay không (vì chúng chỉ thực sự hữu ích nếu bạn nghi ngờ các nửa số nguyên tố đã được tạo không đúng cách).

Nhưng không gặp phải một trong những trường hợp "semiprime yếu" này (điều cực kỳ khó xảy ra nếu nửa nguyên tố được tạo đúng --- vì vậy trừ khi bạn có lý do để nghĩ rằng đây là một Yếu RSA bán nguyên tố có lẽ không đáng để kiểm tra).

Kỹ thuật được sử dụng là giảm N thành một dạng đặc biệt dễ dàng phân tích.

Hiển thị N ở dạng nhị phân và nhận thấy hàng trăm số 0 ở giữa 4 số.

Điều này đã được giảm xuống như sau:

N = một2^1228+b2^875+c*2^353+d

ở đâu a= 1506291488774150974626762365373 b= 322571915263178581 c= 576377099039115423 d= 123431

Coi đây là một đa thức theo x, với x=2:

N = mộtx^1228+bx^875+c*x^353+d

Yếu tố này rất nhanh chóng để:

(359561509069941x^353+77)(4189245652768553*x^875 + 1603)

Trong một bình luận @Sam Blake đã hỏi một câu hỏi tiếp theo về một số nguyên thành thừa số:

7215955072690155355400859323297730634528493510676300043022948136348249037517276095868127042993906604904230826475281383188764473510881994780947137238252071087749294743150564851420395422525735221770067605216401023

Câu hỏi đặt ra là số nguyên tố nửa nguyên tố thứ 2 này có thực sự nhỏ để phân tích thành số nguyên tố không?

Nửa nguyên tố này không yếu vì nó không dễ dàng từ bỏ dạng đặc biệt của nó.

Nó yếu đối với một đối thủ có năng lực quốc gia vì nó chỉ có 701 bit. Nên sử dụng mô-đun 2048 bit hoặc cao hơn với độ dài bit p và q bằng nhau.

Ngoài ra, nó dường như không có điểm yếu khi sử dụng Fermat's, p-1, tỷ lệ của nó không phải là nhỏ phần nhỏ, ECM không hữu ích.

Số nguyên này dường như không phù hợp với một dạng đặc biệt dễ phân tích. Mặc dù một khi hình thức đặc biệt được công nhận, con số có thể được phân tích với nỗ lực ít hơn nhiều, việc phát hiện dạng đặc biệt nào có thể rất tốn thời gian vì có nhiều dạng.

Những gợi ý nào bạn sẵn sàng đưa ra? Rằng đây là một nửa nguyên tố? Mà các yếu tố có độ dài không bằng nhau? Rằng các thừa số là các đa thức với các số hạng: a0 x 2^(k0) + a1 x 2^(k1) + a2 x 2^(k2)...