6

$\{p \in \mathbb Z \mid \text{$p$ is prime and $(p - 1)/2$ is prime}\} = \{2q + 1 \in \mathbb Z \mid \text{$q$ is prime and $2q + 1$ is prime}\}$ With your intervals suitably adjusted, the algorithm considers the same candidates with the same probability whether you check $p$ or $q$ for primality first.


3

How is the 3072-bit modulus derived? Find the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and $q = (p - 1)/2$ are prime, and $p \equiv 7 \pmod 8$. In this case, $n = 3072$ and so $c = 1690314$. Use $g = 2$ as the generator. (Here $\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/...


2

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor. Not really; to factor, all you need is a value $e$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$)...


1

$P[s(g^{ab}) = i] = \frac{q-1}{q^2}$ if $i \neq 1$ and $\frac{2q-1}{q^2}$ if $i = 1$. We assume that $g$ is a generator of $\mathbb{QR}_p = \mathbb Z_q$. Then, as you said, in order to study the probability that $g^{ab} = i = g^c$ for a fixed $c$, we can calculate the probability that $ab = c\bmod q$. In general, the probability that a random pair $(a,b)\...


1

Beyond the existing answers, any clever selection of $p$ is problematic. If we use a special $p$ and it is reused widely, an attacker can attack all of them together. Most of the work in calculating Dlog only depends on the public paramaters and not on the individual value we are trying to get the discrete logartithm of. We even have reason to believe the ...


Only top voted, non community-wiki answers of a minimum length are eligible