#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:


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.