允许快速模块缩减的Schnorr群，vs GNFS

Question

我正在寻找施诺尔集团允许快速模块缩减。比如说，使用DSA中的表示法，包括256位素数q和3072位素数p，以及p\equiv1\pmod q.

Are那里的标准，RFC，或其他有关这方面的引用？

我正在考虑选择p和1上的所有位元，除了一个相对较短的段，距离顶部位不太远。这允许非常快速的蒙哥马利模块缩减，这可以将计算工作量与任意p相比减少一半。通过允许选择更好的多项式()使GNFS速度更快的Would

<#>Any为什么不使用 g=2^{(p-1)/q}，哪个似乎是最自然的生成器？

我所想到的一个非常极端的例子：\begin{align} q&=2^{256}-2^{194}-1\\ p&=2^{3072}-1\\&\quad-2^{2745}\,\mathtt{2219c36803ffffff6352c900000000006008ef007fffffffbcc79fd201_h}\\ \end{align}

q=fffffffffffffffbffffffffffffffffffffffffffffffffffffffffffffffff
p=fffffffffffffffffe000000443386d007fffffec6a5920000000000c011de00ffffffff798f3fa401ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

其中，q是具有单个0位的最小的256-bit素数；选择2745来最小化定义p的230-bit常量的位大小，恰好将该术语放在p的高阶位中，并且(由于q的特殊形式)还在p的该段中创建0和1的长序列。

更新：Daniel的回答显示，实际上，上面允许相当大的GNFS加速。算了吧。以p=2^{3072}-1-c\,2^{3072-\ell}为例，c是一个\ell-1-bit无袖常量，还有一些更大的\ell>230呢？直到\ell关于1024 (相当于p比特大小的三分之一)，我们仍然节省了大部分模块缩减工作。

Answer 1

TL;DR

1. 没有使用这一理念的标准或RFCs。
2. 有一个稍微改进的数字字段筛子攻击，你的例子数字基于信封计算(见下文)。
3. 你提议的发电机就行了。
4. 下面的建议不应接受\ell\ge 768的特殊多项式。

为了攻击一个普通的3072位素数，可以使用The方法构造多项式f_\alpha(x)和具有公共根模p的f_\beta(x)。最好的选择是5级的f_\alpha和4级的系数0，+1，-1和f_\beta，系数在614位附近。然后可以测试\mathcal N(a+b\alpha)和\mathcal N(a+b\beta)的0\le |a|,b\le 2^{65.5}，因为它们都是平滑的(在这里，\mathcal N表示到\mathbb Q的规范)。最大的数字大概是327.5位和876位，而在SageMath中快速的Dickman-\rho计算表明，它们都是光滑的2^{-65.332}概率，而且你应该能够在光滑界以下得到比素数更光滑的数字。然后，您解决了一个粗略的2\times\pi(2^{65.5})变量稀疏线性代数问题(其中\pi(n)表示到n的素数)，然后和后续问题的工作量明显减少。2^{131}光滑性检验和大型线性代数问题的工作与通常引用的128位工作不完全脱节。

您的素数的<#>The后信封允许多项式对f_\alpha(x)=x^9-2^{15}cx^8-64 f_\beta(x)=x-2^{342}，其中c是您的230位常数。然后可以测试\mathcal N(a+b\alpha)和\mathcal N(a+b\beta)的0\le |a|\le 2^{46.5}和0，因为两者都是2^{61.5}平滑的。最大的数字大概是693.5位和418.5位，SageMath说这两者在2^{-61.197}上都很有可能是平滑的。因此，同样，您应该能够得到比素数更光滑的界限以下的数字。然后有一个粗略的2\times\pi(2^{61.5})变量稀疏线性代数问题等等，这是一个粗略的2^{123}光滑性测试和一个可公度线性代数问题。因此，您的问题可能比典型的3072位素数要容易8位。这比其他SNFS攻击的退化要小得多，并且根据情况可以容忍。

埃塔:关于后续问题。特殊多项式可以击败J-L对的最小程度似乎是4。在3072位数的头处有768位或更多位的普通blob应该意味着没有4级或更多的特殊多项式。在某些情况下，使用\ell<768可能仍然是安全的，但是分析开始变得非常复杂。