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
  • $\begingroup$ Other question about the same article. $\endgroup$
    – fgrieu
    Commented Jul 15, 2021 at 11:36
  • $\begingroup$ @fgrieu thanks. $\endgroup$ Commented Jul 15, 2021 at 11:41

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.