2
$\begingroup$

Introduction

Earlier this year Claus Peter Schnorr claimed to have "broken RSA". The original paper was discussed in Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?. A revised version of his paper was posted on the iacr about a week ago and as per @fgrieu's comment, someone attempted to start a discussion around it: Is “Fast Factoring Integers by SVP Algorithms, corrected” correct?.

I decided to give it a go and I found myself utterly mystified by an early claim in the paper. He considers a permutation $f$ of $\{1,\dots,n\}$ and defines column vectors $b_1,\dots,b_n,b_{n+1}$ as below

enter image description here

where $p_1=2,p_2=3,\dots$ are the first $n$ primes and $N'$ is irrelevant to my issue (I presume). He considers a linear combination with integer coefficients $e_1,\dots,e_n$ of the first $n$ vectors

$${\bf b}=\sum_{i=1}^n e_i{\bf b}_i \in \mathcal{L}(R'_{n,f})$$

sets

$$u=\prod_{e_i>0} p_i^{e_i}, v=\prod_{e_i<0}p_i^{-e_i}\in {\mathbb{N}}$$

and writes

$$\hat{z}_{{\bf b}}=N'\ln{(u/v)}$$ for $b$'s last (i.e. $(n+1)$-th) coordinate.

Issue

The issue I have is with the estimate of a lower bound for $\|b\|^2$ that follows. Schnorr writes

enter image description here

This seems to be false on the face of it: it asserts that $$\sum_i e_i^2f(i)^2 \geq\sum_i |e_i|\ln(p_i)$$ But if the permutation $f$ is chosen so that, say, $f(n)=1$ then choosing $e_n=1$ and all other $e_i=0$ yields $$1\geq\ln(p_n)$$ which, unless I'm missing something, is patently false.

Furthermore, unless $e$ is the zero vector there is no way that the claimed inequality can ever be an equality since, upon removing the $\hat{z}_b^2$ term from both sides, the right hand side $\ln(uv)$ is irrational, being the natural log of an integer $uv\geq 2$, whereas the left hand side, $\sum_i e_i^2f(i)^2$, is a positive integer.

Am I missing something? Can someone guess the correct statement he is trying to prove?

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.