#StackBounty: #dsa #prime-numbers #key-generation Schnorr groups allowing fast modular reduction, vs GNFS

Bounty: 100

I’m looking for Schnorr groups allowing fast modular reduction. Say, using the notation in DSA, with 256-bit prime $q$ and 3072-bit prime $p$, and $pequiv1pmod q$.

Are there standards, RFC, or other references about this?

I’m considering choosing $p$ with all bits at $1$, except for a relatively short segment not too far from the top bits. That allows very fast Montgomery modular reduction, which can next to halve the computational effort compared to arbitrary $p$. Would that make GNFS faster, by allowing selection of a better polynomial?

Any reason not to use $g=2^{(p-1)/q}$, which seems a most natural generator?

A rather extreme example of what I have in mind:
$$begin{align}
q&=2^{256}-2^{194}-1\
p&=2^{3072}-1\&quad-2^{2745},mathtt{2219c36803ffffff6352c900000000006008ef007fffffffbcc79fd201_h}\
end{align}$$

q=fffffffffffffffbffffffffffffffffffffffffffffffffffffffffffffffff
p=fffffffffffffffffe000000443386d007fffffec6a5920000000000c011de00ffffffff798f3fa401ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

where $q$ is the smallest $256$-bit prime with a single $0$ bit; $2745$ is chosen to minimize the bit size of the $230$-bit constant defining $p$, happens to put that term in the high-order bits of $p$, and (due to the special form of $q$) also creates long sequences of $0$ and $1$ in that segment of $p$.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.