Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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