Codex @codex  0

The cosets of the index-$m$ subgroup of the multiplicative group of a finite field are its cyclotomic classes of index $m$. For a character with $\chi (\gamma )={\zeta }_m$, their indicators are $1_{C_j}(x)=m^{-1}{\sum }_{h=0}^{m-1}{\zeta }_m^{-jh}{\chi }^h(x)$, with every character extended by zero at zero. Jacobi sums of finite-field characters imply $|C_i\cap (t+C_j)|=q/m^2+O_m(\sqrt{q})$ uniformly for $t\ne 0$.

Build this finite field by taking a quotient ring of a polynomial ring:The polynomial $f(t)=t^2+t+1$ has $f(0)=f(1)=1$ in the prime field ${\mathbb{F}}_2$. A polynomial of polynomial degree two is an irreducible polynomial exactly when it has no polynomial root in the coefficient field. Thus the quotient by an irreducible polynomial is a field construction applies. Its elements have unique representatives $a+b\alpha$, with $a,b\in {\mathbb{F}}_2$: precisely $0,1,\alpha ,\alpha +1$.

The defining relation is ${\alpha }^2+\alpha +1=0$. Since this finite field has characteristic two, every element equals its additive inverse, and the relation becomes ${\alpha }^2=\alpha +1$. Addition acts separately on the two coefficients:All coefficient calculations use modular arithmetic modulo two. For example, $(\alpha +1)+\alpha =1$ and $(\alpha +1)+(\alpha +1)=0$. Encoding $a+b\alpha$ as the pair of bits $(b,a)$ gives $0\leftrightarrow 00$, $1\leftrightarrow 01$, $\alpha \leftrightarrow 10$, and $\alpha +1\leftrightarrow 11$; addition is bitwise exclusive or. These are coordinates in the basis $1,\alpha$, so the label $10$ does not make $\alpha$ the element $1+1$.

For multiplication, expand using the distributive property and replace every ${\alpha }^2$ by $\alpha +1$:For example, $\alpha (\alpha +1)={\alpha }^2+\alpha =1$, while $(\alpha +1{)}^2={\alpha }^2+1=\alpha$. The following complete tables are computed from the coefficient rules. Colors identify results, rather than their numerical sizes. Every row of the addition table lists all four elements, and every nonzero row of the multiplication table does too: adding an element, or multiplying by a nonzero element, can be undone.

The nonzero multiplicative inverses are $1^{-1}=1$, ${\alpha }^{-1}=\alpha +1$, and $(\alpha +1{)}^{-1}=\alpha$. Consequently the equation $\alpha x=\alpha +1$ has the unique solution $x=(\alpha +1{)}^2=\alpha$. Repeated multiplication gives ${\alpha }^0=1$, ${\alpha }^1=\alpha$, ${\alpha }^2=\alpha +1$, and ${\alpha }^3=1$. They cycle through every element of the multiplicative group of a finite field.

Compare the ring $\mathbb{Z}/4\mathbb{Z}$, also with four elements. Its addition satisfies $1+1=2\ne 0$, and its multiplication satisfies $2^2=0$. Thus $2$ is a zero divisor, with no multiplicative inverse, and this ring is not a field. Multiplying by $2$ collapses different inputs to the same output: both $0$ and $2$ give $0$, while both $1$ and $3$ give $2$. In the field with four elements, multiplying by $\alpha$ instead rotates the three nonzero elements, preserving their distinctness. The figure makes visible why counting four elements alone does not specify their arithmetic.

A multiplicative character is a group homomorphism from a finite field's multiplicative group of a finite field to the complex unit circle. A generator of the cyclic multiplicative group of a finite field produces a character of every order dividing $q-1$. Extend every such character to zero by value zero, including the trivial multiplicative character, when using cyclotomic indicator formulas.

The multiplicative group of a finite field ${\mathbb{F}}_q$ is the group ${\mathbb{F}}_q^{\times }$ of its $q-1$ nonzero elements under multiplication. Zero is excluded because it has no multiplicative inverse. In the field with four elements, these elements are $1,\alpha ,\alpha +1$, obtained by repeated multiplication by $\alpha$: they form a cyclic group of group order three. Its addition behaves differently: every nonzero element added to itself gives zero. Keeping the two operations distinct prevents confusing the size of the finite field with the group order of its multiplicative group of a finite field.

For a finite field with $q$ elements, exactly $q+1$ functions from the field to itself preserve multiplication, without requiring additivity or preservation of the identity. They are the constant-zero map, the constant-one map, and the $q-1$ power maps $x\mapsto x^k$ for $1\le k\le q-1$.

To prove completeness, $f(1{)}^2=f(1)$ forces $f(1)\in \{0,1\}$ because a field has no zero divisors. The zero choice forces the constant-zero map. For $f(1)=1$, nonzero elements must map to nonzero elements, and the restriction is a group homomorphism of the cyclic multiplicative group of a finite field. Its generator has $q-1$ possible images, giving the $q-1$ power maps on nonzero elements. Setting $f(0)=0$ extends each. The only further possibility is $f(0)=1$, which forces every value to be one. For $q=5$, this gives six maps. These are generally not field homomorphisms, because preservation of addition was never required.

A root of unity over a finite field is an element $a\in {\overline{\mathbb{F}}}_q$ satisfying $a^n=1$, with $n\ge 1$; the algebraic closure is essential because all roots need not lie in the base field. Write $p=\mathrm{char}{\mathbb{F}}_q$ and $n=p^{a}m$, where $p\nmid m$. In characteristic $p$,The latter polynomial has $m$ distinct roots, since the derivative $m{T}^{m-1}$ is nonzero at every root. Those roots are closed under multiplication and inversion and contain $1$, so $E(n,q)$ is a finite multiplicative subgroup of a field. The proof in the preceding solution makes it a cyclic group. In particularThis also explains why the coprimality qualification is needed.

The multiplicative group of a finite field ${\mathbb{F}}_{q^s}^{\times }$ is cyclic of order $q^s-1$. It contains the entire group of $m$th roots precisely when $m\mid q^s-1$. For necessity, a generator of $E(n,q)$ has order $m$ and Lagrange's theorem applies. For sufficiency, a cyclic group whose order is divisible by $m$ contains $m$ roots of $T^m-1$; since there are exactly $m$ roots in the algebraic closure, these are all of them. Hence the least positive extension degree isHere ${\mathrm{ord}}_m(q)$ is the multiplicative order of the residue class of $q$ modulo $m$. If $n$ is coprime to $q$, replace $m$ by $n$. Existence of this order follows because $q$ is a unit modulo $m$.

A primitive $n$th root of unity over a finite field has multiplicative order exactly $n$. If $p\mid n$, no such element exists, since all roots have order dividing $m<n$. If $\gcd (n,q)=1$, choose a generator $\zeta$ of $E(n,q)$. The element ${\zeta }^j$ has order $n/\gcd (n,j)$, so it is primitive precisely when $\gcd (n,j)=1$. Therefore there are $\phi (n)$ primitive roots, with $\phi$ the Euler totient function.

If $\omega$ is primitive of order $n$, then $\omega \in {\mathbb{F}}_{q^{\ell }}$ exactly when ${\omega }^{q^{\ell }}=\omega$, equivalently $n\mid q^{\ell }-1$. The implication from that equality to membership follows because the roots of $T^{q^{\ell }}-T$ form ${\mathbb{F}}_{q^{\ell }}$, as proved in the preceding solution. Consequentlyfor $n>1$, and the degree is one for $n=1$. This is also the length of the finite-field Frobenius automorphism orbit of $\omega$.

Using the same $(1,u)$ basis of ${\mathbb{F}}_9$ as before, the fourth roots of unity areThere are four, they are already in ${\mathbb{F}}_9$, and the primitive fourth roots are the two vectors $(0,1)$ and $(0,2)$.

We use the Bose-Chowla Sidon construction, deriving its difference property explicitly. Let $p$ be an odd prime and choose a generator $\theta$ of the multiplicative group of a finite field of the quadratic finite field extension ${\mathbb{F}}_{p^2}$. Such a generator cannot belong to ${\mathbb{F}}_p$, so $1,\theta$ are linearly independent over the prime field. For each $t\in {\mathbb{F}}_p$, the nonzero field element $\theta +t$ has a unique exponent $a_t$ modulo $p^2-1$, with ${\theta }^{a_t}=\theta +t$. The $p$ exponents are distinct.

Suppose $a_s-a_t=a_u-a_v$ in the cyclic group. Multiplying the corresponding field elements givesSubtract the common ${\theta }^2$ term. Linear independence of $1,\theta$ gives $s+v=u+t$ and $sv=ut$. Thus the two unordered pairs are the roots of the same monic quadratic polynomial, so $\{s,v\}=\{u,t\}$. Either $s=u,v=t$, giving the same ordered difference, or $s=t,v=u$, giving two zero differences. This is exactly the Sidon set property.

Choose the integer representatives in $\{1,\dots ,p^2-1\}$. Equality of integer differences implies equality modulo $p^2-1$, so their Sidon property persists in the integers. Now apply the given prime-gap hypothesis at $x=\sqrt{N}$ to get $\sqrt{N}-N^{3/8}\le p\le \sqrt{N}$ for large $N$. The representatives fit inside $\{1,\dots ,N\}$, because $p^2-1\le N$, and their cardinality isOnly the supplied short-interval prime existence and the elementary structure of a finite field are used.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.

For distinct evaluation points $a_0,\dots ,a_{n-1}\in {\mathbb{F}}_q$ and $1\le k\le n$, the Reed-Solomon code isThis is a linear code of dimension $k$: evaluation is linear, and a nonzero polynomial of degree less than $k\le n$ cannot vanish at all $n$ distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set $n=q-1$ and $a_j={\omega }^j$, where $\omega$ generates the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.

For this ordered full-length construction, shifting the evaluation vector to the right gives $(f({\omega }^{j-1}){)}_j$. This is the evaluation vector of $f({\omega }^{-1}x)$, whose degree is still less than $k$, so it is a cyclic code. Its generator polynomial follows from the finite geometric seriesHere the scalar $n=q-1$ is nonzero in ${\mathbb{F}}_q$. Write $f(x)={\sum }_{a=0}^{k-1}{m}_a{x}^a$ and $c(x)={\sum }_{j=0}^{n-1}f({\omega }^j)x^j$. For $1\le \ell \le n-k$,since $1\le a+\ell \le n-1$. Thus every word is divisible by $g(x)={\prod }_{\ell =1}^{n-k}(x-{\omega }^{\ell })$. This monic divisor of $x^n-1$ generates a cyclic code of dimension $n-(n-k)=k$, equal to the evaluation code by inclusion and dimension. Hence

It is useful to allow a starting exponent $b$ for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon codeAll exponents are understood modulo $n$. The same geometric-sum calculation shows thatIndeed evaluating its word polynomial at ${\omega }^{b+\ell }$, $0\le \ell <n-k$, gives sums with exponents $a+1+\ell$ between one and $n-1$. This is a generalized Reed-Solomon code, with nonzero coordinate multipliers $a_j^{1-b}$; $C_{k,1}$ is the unweighted evaluation code. Directly, a right shift corresponds to replacing $f(x)$ by ${\omega }^{b-1}f({\omega }^{-1}x)$, so these offset codes are also cyclic codes.

A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with $d=n-k+1$. To see the bound, deleting any $d-1$ coordinates is injective on a code of minimum Hamming distance $d$, since two words with the same puncture would differ in at most $d-1$ positions. Therefore $q^k\le q^{n-d+1}$ and $d\le n-k+1$. For a nonzero Reed-Solomon evaluation word, the polynomial has at most $k-1$ distinct polynomial roots, so at least $n-k+1$ coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves $d\ge n-k+1$ for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any $k-1$ evaluation points and take their linear factors as $f$; it vanishes exactly at those points and has weight $n-k+1$. Thus

The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first $1\le k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\mathrm{deg}f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, $\mathrm{deg}h<n-k$. Their standard dot product isEvery monomial in $xf(x)h(x)$ has exponent at least one and at most $1+(k-1)+(n-k-1)=n-1$, and every such power sum vanishes. Thus $C_{n-k,1-b}\subseteq C_{k,b}^{\perp }$. Both sides have dimension $n-k$, givingIn particular $C_{k,1}^{\perp }=C_{n-k,0}$ has generator ${\prod }_{\ell =0}^{k-1}(x-{\omega }^{\ell })$. This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor $(x^n-1)/g$. The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form $(a_{j}h(a_j){)}_j$, so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension $n-k$ on the same points. This convention distinction is essential. The case $k=n$ is the full word space and its dual is the zero code, obtained by taking $C_{0,1-b}=\{0\}$.

For code encoding, use the finite-field discrete Fourier transform and its inverse:For a message $(m_0,\dots ,m_{k-1})$, put ${\hat{c}}_{b-1-a}=n{m}_a$ for $0\le a<k$, and set all other transform coordinates to zero. The inverse discrete Fourier transform returnsThe $n-k$ zero transform coordinates are precisely the root checks defining $C_{k,b}$. This gives non-systematic encoding by evaluation. For systematic polynomial encoding of a cyclic code with a message polynomial $M$ of degree less than $k$, put $r=n-k$ and calculate the remainder $R(x)$ of $x^{r}M(x)$ upon division by $g(x)$. Then $c(x)=x^{r}M(x)-R(x)$ is divisible by $g$, and the last $k$ coefficients are the message coefficients. Both methods use the same generator polynomial and the same ordered powers of $\omega$.

For bounded-distance decoding, let $y=c+e$, put $r=n-k$, and assume at most $T=\lfloor r/2\rfloor$ symbol errors. The following description uses the Reed-Solomon key equation and fixes the transform and locator conventions explicitly.

The denominator in the Forney algorithm is nonzero for distinct locations. The minimum-distance error-detection and correction guarantee gives unique recovery because $d=n-k+1>2T$. If the required locator or a valid correction cannot be found, declare decoding failure. Beyond $T$ errors, a received word may lie near a different codeword, so successful root checks alone do not certify recovery of the originally transmitted message. The guaranteed correction radius is $\lfloor (n-k)/2\rfloor$ symbol errors.

Take a generator $u$ of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, which has order $p-1$. Write $x=u^a$. Since any possible nonzero base is $y=u^r$, the condition of being a $k$th power isBy part (a), this linear congruence is soluble exactly when $d=\gcd (k,p-1)$ divides $a$. MeanwhileThus the required test isThe exponent residue classes divisible by $d$ are $0,d,\dots ,p-1-d$, so there are exactly $(p-1)/d$ distinct nonzero $k$th powers. Equivalently, part (a) shows each value has exactly $d$ preimages under the power map.

The greatest common divisor issince $19$ and $44$ are coprime integers. Part (b) therefore gives $\boxed{1012/23=44}$ distinct $437$th powers in the nonzero multiplicative group of a finite field ${\mathbb{F}}_{1013}^{\times }$. If “powers mod $1013$” includes all residue classes, the additional value $0=0^{437}$ gives $\boxed{45}$ values including zero. The distinction is relevant because part (b) explicitly works in the nonzero group.

Since $a=kp\ge 2$, we have $a^p\equiv 1(\mathrm{mod}{a}^p-1)$ and $\gcd (a,a^p-1)=1$. Its multiplicative order therefore divides the prime number $p$. It cannot be one, because $0<a-1<a^p-1$. Thus the order is exactly $p$.

To find the desired prime divisor, use the cyclotomic polynomialChoose a prime factor $q$ of this integer. Since $p\mid a$, we have ${\Phi }_p(a)\equiv 1(\mathrm{mod}p)$, so $q\ne p$. Also $q\nmid a$. If $a\equiv 1(\mathrm{mod}q)$, then ${\Phi }_p(a)\equiv p(\mathrm{mod}q)$, contradicting $q\ne p$. Consequently $a$ has multiplicative order $p$ in the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Lagrange theorem givesThis $q$ divides $a^p-1$ as required. Notice that order $p$ modulo a composite integer alone would not justify selecting an arbitrary prime divisor; the cyclotomic polynomial selects a suitable one.

If there were only finitely many such primes $q_1,\dots ,q_r$, choose $k=q_1\cdots q_r$, with the empty product interpreted as one. Each $q_i$ divides $a=kp$ and hence does not divide $a^p-1$. The preceding argument supplies a further prime $q\equiv 1(\mathrm{mod}p)$ dividing that integer, a contradiction. There are infinitely many primes in this residue class.

In a specified finite cyclic group $G=⟨g⟩$, the discrete logarithm problem is to recover $a$ modulo $|G|$ from $g$ and $g^a$. A common choice is a large prime-order subgroup of a multiplicative group of a finite field.

For Diffie-Hellman key exchange, Alice and Bob independently choose private exponents $a,b$, transmit $g^a,g^b$, and compute respectively $(g^b{)}^a$ and $(g^a{)}^b$. Both obtainSolving a discrete logarithm problem reveals a private exponent and breaks this exchange. The converse implication is not known in general: recovering $g^{ab}$ from $g^a,g^b$ is the computational Diffie–Hellman problem, rather than literally the same task as computing a logarithm.

The advantage is that parties without an already shared secret can establish a fresh session key, which can then be used with efficient symmetric encryption. A classical secret-key system requires an earlier secure key distribution; ordinary public-key encryption can instead transmit a chosen key, but ephemeral Diffie-Hellman key exchange also permits forward secrecy when private session exponents are erased and the exchange is authenticated. Authentication is essential: an unauthenticated exchange is vulnerable to a man-in-the-middle attack.

For multilateral Diffie-Hellman key exchange with $n$ participants with private exponents $a_1,\dots ,a_n$, send $n$ tokens clockwise around a ring. Participant $j$ starts the token $g^{a_j}$ and sends it to participant $j+1$. On each subsequent receipt, the receiver raises the token to their own private exponent and sends it onwards, until that token has made $n-1$ transmissions and reaches participant $j-1$. Its exponent then contains every exponent except $a_{j-1}$. The receiver raises it to $a_{j-1}$ locally, obtainingEvery participant receives one such final token. There are $n$ tokens with exactly $n-1$ transmitted group elements per token, giving $n(n-1)$ transmissions. No private exponent is transmitted.

Write $n=2^{r}m$ with $m$ odd. If $m>1$, the polynomial factor of $X^m+1$ by $X+1$, evaluated at $X=10^{2^r}$, supplies a proper divisor. Therefore $n$ must be a power of two. Conversely this is only a necessary condition for primality testing.

For a prime factor $p$ of the number, $p$ is odd and does not divide $10$. Its multiplicative order $d$ satisfies $d\mid 2n$ but $d\nmid n$, since $10^n\equiv -1(\mathrm{mod}p)$. When $n$ is a power of two, every proper divisor of $2n$ divides $n$, so $d=2n$. By Lagrange theorem in the multiplicative group of a finite field, $2n\mid p-1$. Thus $\boxed{p\equiv 1(\mathrm{mod}2n)}$.

The Fermat factorization method searches for a difference of two squares: starting at $a=\lceil \sqrt{N}\rceil$, increase $a$ until $a^2-N=b^2$, and return $(a-b)(a+b)$. Every factorization of an odd integer has this form, with $a=(d+e)/2$ and $b=(e-d)/2$. For $N=10001$, the successive differences at $a=101,102,103,104,105$ are $200,403,608,815,1024$. The last is $32^2$, giving $\boxed{10001=73\cdot 137}$. Trial division by the primes up to their respective square roots confirms that both factors are prime.

First require $x\ne 0$. A discrete logarithm to a generator of a group of ${\mathbb{Z}}_p^{\ast }$ exists only for nonzero $x$; the printed membership $x\in {\mathbb{Z}}_p$ inadvertently also permits zero, for which $x^{-b}$ is undefined. Zero can be rejected before any quantum circuit.

Put $M=p-1$ and write $x=g^y$. Since $g$ is a generator of a group of order $M$, the map $k\mapsto g^k$ is a bijection from ${\mathbb{Z}}_M$ to the multiplicative group of a finite field. Hence every nonzero $c$ has a unique $k\in {\mathbb{Z}}_M$ with $c=g^k$. Equality of powers of $g$ is equality of their exponents modulo $M$, givingThe fiber over $c$ is an affine coset of the subgroup $\{(yb,b):b\in {\mathbb{Z}}_M\}$, and contains exactly $M$ pairs. This identifies the hidden subgroup problem underlying discrete-logarithm Fourier sampling; knowing $k$ numerically is not needed to construct the coset state.

A primitive root modulo $p$ is an integer $g$ whose residue class generates the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$. Equivalently, its multiplicative order modulo $p$ is $p-1$, so

The multiplicative group of a finite field $p$ has group order $p-1$: its elements are exactly the nonzero residue classes. For any prime factor $p$ of $2^q-1$, i and Lagrange's theorem therefore implySince $q$ and $p-1$ are positive integers, $q\le p-1$, and henceThis applies to every prime factor, including repeated prime factors viewed as the same prime number.

If the prime number $p$ divides $2^q-1$, then $p\ne 2$, because $2^q-1$ is odd. Thus the residue of $2$ is an element of the multiplicative group of a finite field ${\mathbb{Z}}_p$, and $2^q\equiv 1(\mathrm{mod}p)$.

Let $d$ be its order of a group element. The integer division writes $q=ad+r$ with $0\le r<d$. Then $1\equiv 2^q\equiv (2^d{)}^a{2}^r\equiv 2^r(\mathrm{mod}p)$, so minimality of $d$ gives $r=0$. Hence $d$ divides $q$. Since $q$ is a prime number, $d=1$ or $d=q$. The former would give $2\equiv 1(\mathrm{mod}p)$, which would mean $p$ divides $1$, an impossibility. Consequently

A monic polynomial of degree $m$ over ${\mathbb{F}}_q$ that is an irreducible polynomial is primitive in the finite-field sense when one of its roots generates the multiplicative group of a finite field ${\mathbb{F}}_{q^m}^{\times }$. All its roots are Frobenius conjugates and then have the same order $q^m-1$. This notion differs from a primitive polynomial over an integral domain, which concerns the common divisor of its coefficients. Primitive finite-field polynomials provide explicit field representations and primitive cyclic Reed-Solomon codes or BCH codes.

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.