2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.