I am given
p = 4916335901
q = 88903
and am asked to show these are prime as well as q|(p-1) in DSA.
I am unsure on how to do this, what does q|(p-1) mean exactly?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
I am given $p = 4916335901$, $q = 88903$ and am asked to show these are prime
To check whether a given integer $n$ is prime you have to check whether it is only divisible by $1$ and $n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in case of such small numbers just ask Wolfram alpha. In your case, both $p$ and $q$ are indeed prime, and your given $p$ is of the form $p=k\cdot q +1$. Most often one encounters the use of $k=2$, so called safe primes in cryptography. You can generate such primes even in the size for cryptographic purposes efficiently.
as well as $q|(p-1)$ in DSA.
The notation $a|b$ means that $a$ evenly divides $b$, i.e., $b$ divided by $a$ gives a remainder of zero. This is easy to check by computing $\frac{4916335901-1}{88903}=55300$, so yes $q|(p-1)$.
Using a prime of the form $p=k\cdot q+1$ with small $k$, you know that when you are working in ${\mathbb Z}_p^*$ (which has order $p-1$) that you have a cyclic subgroup of prime order $q$.
