# Tag Info

0

Use the Legendre symbol in your case. Explanation: when $p=2.q+1$, the order of the multiplicative group of $F_p$ is p-1=2q. Then there is no other alternative, when you select a random number, it could be a quadratic Residue with probability $\frac{1}{2}$. The legendre symbol of any number a, is : $a^{\frac{p-1}{2}}=a^{q}=\pm 1$ Then except the number 1, ...

1

Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter $p$ or $q$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or ...

0

One specific example of a multiplicative group of a composite order is RSA. Group order could be not known to a proving party (hidden from). With this setup, one can prove relations over integers, not residues modulo group order. Proof based on Lagrange 4-squares theorem is a well-known example. No efficient implementation is known for a proof of "more" ...

Top 50 recent answers are included