Giới thiệu
Đầu năm nay, Claus Peter Schnorr tuyên bố đã "phá vỡ RSA". Bài báo gốc đã được thảo luận trong Phương pháp bao thanh toán năm 2021 của Schnorr có cho thấy hệ thống mật mã RSA không an toàn không?. Một phiên bản sửa đổi bài báo của anh ấy đã được đăng trên iacr khoảng một tuần trước và theo nhận xét của @fgrieu, ai đó đã cố gắng bắt đầu một cuộc thảo luận về nó: âFast Factoring Integers by SVP Algorithms, đã sửa có chính xác không?.
Tôi quyết định thử và tôi thấy mình hoàn toàn bối rối trước một tuyên bố ban đầu trên báo. Ông xem xét một hoán vị $f$ của $\{1,\dots,n\}$ và định nghĩa các vectơ cột $b_1,\dots,b_n,b_{n+1}$ như sau
ở đâu $p_1=2,p_2=3,\dots$ là người đầu tiên $n$ số nguyên tố và $N'$ không liên quan đến vấn đề của tôi (tôi đoán vậy). Ông xem xét một tổ hợp tuyến tính với các hệ số nguyên $e_1,\dots,e_n$ của người đầu tiên $n$ vectơ
$${\bf b}=\sum_{i=1}^n e_i{\bf b}_i \in \mathcal{L}(R'_{n,f})$$
bộ
$$u=\prod_{e_i>0} p_i^{e_i}, v=\prod_{e_i<0}p_i^{-e_i}\in {\mathbb{N}}$$
và viết
$$\hat{z}_{{\bf b}}=N'\ln{(u/v)}$$
vì $b$cuối cùng (tức là $(n+1)$-th) phối hợp.
Số báo
Vấn đề tôi gặp phải là với ước tính giới hạn dưới cho $\|b\|^2$ điều đó theo sau. Schnorr viết
Thoạt nhìn thì điều này có vẻ sai: nó khẳng định rằng
$$\sum_i e_i^2f(i)^2 \geq\sum_i |e_i|\ln(p_i)$$
Nhưng nếu hoán vị $f$ được chọn sao cho, nói, $f(n)=1$ sau đó chọn $e_n=1$ và tất cả những thứ khác $e_i=0$ sản lượng
$$1\geq\ln(p_n)$$
mà, trừ khi tôi thiếu một cái gì đó, rõ ràng là sai.
Hơn nữa, trừ khi $e$ là vectơ không, không có cách nào mà bất đẳng thức đã khẳng định có thể là một đẳng thức kể từ khi loại bỏ $\hat{z}_b^2$ thuật ngữ từ cả hai bên, phía bên tay phải $\ln(uv)$ là số vô tỉ, là log tự nhiên của một số nguyên $uv\geq 2$, trong khi vế trái, $\sum_i e_i^2f(i)^2$, là một số nguyên dương.
Tui bỏ lỡ điều gì vậy? Ai đó có thể đoán đúng tuyên bố mà anh ấy đang cố gắng chứng minh không?
