Score:2

Schnorr RSA factoring (round 2)

gb flag

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?

fgrieu avatar
ng flag
[Other question](https://crypto.stackexchange.com/q/92022/555) about the same article.
gb flag
@fgrieu thanks.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.