# #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$$.

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!!!

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