Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Alice chooses

i) A large prime $p_A$ (say 200 to 300 digits)
ii) A primitive element $\alpha_A$ modulo $p_A$,
iii) A (possibly random) integer $d_A$ with $2 \le d_A \le p_A-2$.

Alice computes

iv) $\beta_A \equiv \alpha_A^{d_A} \pmod {p_A}$.

Alice's public key is $(p_A,\alpha_A,\beta_A)$. Her private key is $d_A$.

What is meant by the notation $\alpha_A$, $p_A$, and what is meant by a 'primitive element', does it mean a small number or something else entirely?

share|improve this question
What do you mean by "a (subscript a)"? There is no a with a subscript anywhere in the quote? Do you mean $\alpha_A$? – CodesInChaos Jun 26 '13 at 10:09

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on.

A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, \alpha_A, \alpha_A^2, \alpha_A^3, \ldots, \alpha_A^{p_A-1}\}$ must be the whole set $\{1, 2, 3, \ldots, p-1\}$ of nonzero elements of the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, i.e. any nonzero element of the field can be expressed as a power of $\alpha_A$. Another way of expressing this property is that $\alpha_A$ must have the order $p-1$ (the largest possible order of an element of the field), which means that none of the $\alpha_A^k$ for $1 \le k \le p-2$ are equal to $1$ modulo $p$.

share|improve this answer

Your Answer


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.