BCH code Created 2026-09-24 Updated 2026-11-05
Let be a finite field, let be coprime to , and choose an element of multiplicative order in an field extension. A BCH code of length , starting exponent , and design distance is the cyclic code whose generator polynomial of a cyclic code is
where is the algebraic minimal polynomial of over . Equivalently, is the least-degree monic polynomial over the base finite field vanishing at consecutive powers. This least-degree condition distinguishes the BCH code from its proper cyclic code subcodes with additional zeros. The BCH bound gives minimum Hamming distance at least .
For example, over the field with two elements, let and let be a polynomial root of . The roots and have the same algebraic minimal polynomial, so and give , a Hamming code of length seven.[ref]
Candidate-denominator gcd post-processing Created 2026-10-06 Updated 2026-10-14
After continued-fraction recovery in quantum order finding, an even candidate denominator can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and . If is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.
Carmichael function Created 2026-09-24 Updated 2026-10-20
For an integer , the Carmichael function is the exponent of a finite group for the unit group : the least positive integer for which
Here the greatest common divisor condition selects the units. Euler's totient function counts them; the Carmichael function gives their least common return exponent.[ref]
Modulo eight, the units are , and their squares are all congruent to one. Their multiplicative orders are , so although . Modulo fifteen, the units have multiplicative orders . For example, the powers of two return through . Thus although ; the multiplicative order of four is only two.
Figure 1.
Individual unit orders divide the least common return exponent modulo eight and fifteen
. Details.
The three quantities are related by
A common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order , proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.
For the prime factorization with distinct prime numbers and , the formulas are
These are least common multiples, rather than products: . The convention handles the trivial case separately.[ref]
The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order . For , the unit group modulo is a direct product of groups , generated by the classes of and five, so its exponent of a finite group is .[ref]
This gives a uniform reduction for modular exponentiation: for a unit and a nonnegative integer , reduce modulo . For example, because . The unit hypothesis matters: , but . Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number passes the Fermat primality test for every unit base exactly when . For example, .
For a reduced fraction with , , and coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has length
Here denotes multiplicative order, and denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.[ref]
For example, long division of gives the remainders , with emitted digits . Consequently
Each remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.
Figure 1.
Long-division remainders explain the six-digit repeat of one seventh and the two-digit prefix of one twenty-eighth
. Details.
More generally, initialize long division with . At each step, division with remainder gives
so . Since are coprime integers, the modular inverse of shows that exactly when . To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of digits represents for an integer . A reduced fraction with that value forces . Hence the shortest digit repeat and the multiplicative order coincide.
Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With , the integer
is the block, padded on the left with zeros to digits. For , and , so the block is and . Reduction matters: has decimal period one, whereas .
If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. Write
The decimal preperiod has exactly digits. If , the remaining repeating decimal has decimal period . For instance, gives : two prefix digits, then six repeating digits. If , the decimal representation is a terminating decimal with exactly fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example terminates after three places.
A short derivation explains both cases. After digits, multiplying the reduced fraction by and discarding its integer part leaves a reduced fraction whose denominator is . This denominator first becomes coprime to ten at . It then equals , giving an immediate repeat when , or an integer when . The same long division argument works for positional notation in any base : for a reduced denominator coprime to , the shortest repeating block has length .
Euler's theorem Created 2026-10-03 Updated 2026-11-05
For an integer modulus and an integer with greatest common divisor , Euler's theorem, also called the Fermat-Euler theorem, states
Here Euler's totient function counts the units in the unit group . These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to . The guaranteed return to one permits exponent reduction for units.[ref]
For a prime number , , recovering Fermat's little theorem in the form when . Multiplying by and separately handling gives for every integer . For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.
Modulo twelve, the units have representatives , so Euler's totient function gives . Multiplication by five produces
Thus this permutation has two permutation cycles, each of length two. In particular , and the guaranteed return follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles and , covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.
Figure 1.
Two unit permutations: multiplication by five modulo twelve and by seven modulo fifteen
. Every arrow multiplies by the indicated unit and reduces modulo the indicated integer modulus. The permutation cycles exhaust each reduced residue system. The permutation cycle containing one records the powers of the multiplier; its length is the multiplier's multiplicative order, which can be smaller than Euler's totient function. Details.
There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer divides both and , then for every , so cannot be congruent to one modulo . For example, and , rather than one. Such a base has no multiplicative order modulo that integer modulus.[ref]
For a unit modulo n and a nonnegative integer , division with remainder writes with . Euler's theorem then gives
This replaces a potentially enormous exponent by a small remainder. The exponent itself is reduced modulo Euler's totient function, while the powers are reduced modulo : these are different integer moduli.
For a worked modulo-fifteen calculation, seven is coprime to fifteen and . Therefore
Use exponentiation by squaring on the remaining exponent , reducing after each multiplication:
Thus . Modular exponentiation supplies the computation; Euler's theorem supplies the optional shortening of its exponent. Exponentiation by squaring also works for nonunit bases, without using this shortening.
The guaranteed exponent is a common return exponent and an upper bound on the shortest period; it need not be that period. The multiplicative order is the least positive return exponent for the chosen unit. The Carmichael function is the least positive return exponent that works for every unit. Their precise relation is
Either smaller return exponent can replace in exponent reduction for units. Modulo fifteen, , so gives immediately. For base four the multiplicative order is only two, smaller even than . A return at exponent eight alone does not prove that the multiplicative order is eight.[ref]
Figure 1.
Actual power periods, Carmichael function exponents and Euler return exponents
. Each row lists powers from exponent zero through eight. Highlighted first returns identify multiplicative orders; the accompanying labels distinguish a chosen base's shortest period, the common exponent for all units, and Euler's totient function. Powers of the nonunit three modulo fifteen repeat after an initial term but never return to one at a positive exponent. The final calculation compares reduction of modulo eight and modulo four. Details.
If the reduced exponent is zero, the rule gives , and still requires a unit. Applying it to the nonunit three would falsely predict ; the actual residue is six. For negative exponents, first interpret the power using a modular multiplicative inverse, as in modular exponentiation.
Fermat little theorem Created 2026-09-24 Updated 2026-10-14
For a prime number and an integer not divisible by , Fermat's little theorem states the modular congruence
Equivalently, for every integer , including and multiples of ,
The first formulation follows from the second by multiplying by a modular multiplicative inverse of . Conversely, multiply the first by when ; when , both sides of the second are zero modulo . The divisibility condition in the first formulation is essential.[ref]
For , , so and . Also , while : a zero residue class cannot satisfy the first formulation. It does satisfy . A failure at a zero residue class therefore says nothing against a candidate's being a prime number.
The prime number is included. Its only nonzero residue class is one: every odd integer satisfies . Every integer also satisfies , because is even. Testing the first formulation with an even integer would violate its hypothesis.
The useful surprise is that every nonzero residue class returns to one at the same exponent , although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer , when . It also computes a modular multiplicative inverse as modulo , including . Repeated squaring makes these modular exponentiations practical.
In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with , of group order . Lagrange's theorem says that the multiplicative order of divides , giving the guaranteed return. Euler's theorem extends this to a general integer modulus , using the units and Euler's totient function ; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.
Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent leave zero or one upon division by a prime number . The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.[ref]
Fermat number Created 2026-10-07 Updated 2026-10-13
A Fermat number is the positive integer , indexed by a nonnegative integer . The first five are , all prime numbers; the next is the composite number . This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.
Figure 1.
Exact Fermat numbers: five initial primes, a composite sixth term, and rapidly increasing decimal lengths
. Details.
Why does the exponent itself have the form ? Suppose is a positive integer with an odd integer factor . The polynomial factorization shows that is a proper divisor of . Consequently, if is a prime number, must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.
The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.
The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, and qualify, but does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).
Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor of . His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.[ref]
A short modern check needs only two representations of :
In modular arithmetic these give and . Substitution yields , so . This verifies the factor directly; it does not claim to reconstruct Euler's search process.
Fibonacci primitive root Created 2026-10-20 Updated 2026-11-05
A Fibonacci primitive root modulo an odd prime is a primitive root modulo n satisfying . Its powers obey , so the same multiplication that generates all nonzero residues also follows a Fibonacci recurrence.
For example, works modulo five: and its powers exhaust the nonzero residues. Solving the quadratic condition alone is insufficient; the multiplicative order must also equal . Away from , the quadratic has roots only when its discriminant five is a quadratic residue modulo .
Finite quotients of cyclic squaring presentations Created 2026-10-06 Updated 2026-10-14
A group presentation with a cyclic list of generators and relations has no nontrivial finite quotient of a group. In a finite image, all generator orders are odd. Choose the least prime dividing any nontrivial generator order and let be the predecessor of a generator whose order is divisible by . Conjugation by acts as squaring on , so the multiplicative order of modulo divides the order of . That multiplicative order is greater than one and divides , giving a prime divisor smaller than in the order of , a contradiction. This argument applies to any cycle length; it asserts absence of finite quotients, not infinitude of the presented group.
Lifting a primitive root to odd prime powers Created 2026-09-24 Updated 2026-11-05
Let be an odd prime and a primitive root modulo . Then is a primitive root modulo every prime power if and only if it is a primitive root modulo . In that case
The condition at says with . The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by , gives
Here is the prime valuation. To see the induction step, the first term in has prime valuation , while every later term has strictly greater prime valuation when is odd and .
Any return must have , by its order modulo . Writing , the displayed valuation forces , with equality giving a return. This proves the claimed multiplicative order. The reverse implication follows by taking .
Multiplicative order Created 2026-09-24 Updated 2026-10-13
For coprime integers with , the multiplicative order is the least positive integer such that
It counts the distinct powers in the cyclic subgroup generated by the congruence class of . Thus it is an order of a group element in the unit group .[ref]
For example, the modular exponentiation , starting at , produces . The first return to one takes three steps, so . Starting at the congruence class three and repeatedly multiplying by two instead gives : these are the other three units modulo seven, outside the cyclic subgroup generated by two.
Figure 1.
Multiplication by two modulo seven has two cycles; its powers follow the cycle through one
. Details.
Euler's theorem guarantees a return to one at exponent , where is Euler's totient function. Thus the multiplicative order exists for every unit.[ref] In fact,
By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is ; the multiplicative order need not equal Euler's totient function. If , its multiplicative order is one.
The coprime integers hypothesis is necessary: if , any common divisor of and divides one. For instance, powers of two modulo eight give , with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.
For a prime number and , multiplication by gives a permutation of the nonzero residue classes. For modulo seven, the representatives map to : the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.
Figure 1.
Multiplication by three modulo seven permutes all six nonzero residue classes
. The upper arrows show each input and its image. The lower arrows repeatedly apply the same permutation to one, displaying the powers modulo seven. The highlighted final one is the first positive return, at exponent six. Details.
For modulo seven, the permutation cycles are instead and . The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.
Figure 2.
Multiplication by two modulo seven gives two permutation cycles of length three
. Every arrow multiplies by two modulo seven. The left permutation cycle contains one and hence the powers of two. The right permutation cycle contains the other three nonzero residue classes. Their common length three divides . Details.
More generally, every permutation cycle of this map has length equal to the multiplicative order of : starting at a nonzero residue class , a return means , and its modular multiplicative inverse allows cancellation of . Thus the nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into .
The product argument gives a short proof outline. Since multiplication by is a permutation of the nonzero residue classes,
Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves . The whole argument works for , where the product is just one.[ref]
Order as the exact period of modular exponentiation Created 2026-09-24 Updated 2026-10-14
Let be coprime integers with , and let be their multiplicative order. For integers ,
Negative exponents mean powers of the modular inverse of . Thus periodic modular exponentiation has smallest positive period , and are distinct congruence classes.[ref]
This lets a huge modular exponentiation reuse a short list: reduce its exponent modulo the multiplicative order, then look up the corresponding power. For example, gives , while gives . When the multiplicative order is unknown, Euler's theorem permits reduction modulo Euler's totient function, though that period may be longer. Repeated squaring remains useful when computing either the unreduced or the reduced power.
For a proof outline, multiply by the modular inverse of , leaving . Apply Euclidean division to write with . Then ; minimality of the multiplicative order forces . The reverse implication follows from . The coprime integers hypothesis enables cancellation: modulo eight, , but this repetition supplies no multiplicative order for two.
Order verification from divisors Created 2026-09-24 Updated 2026-11-05
Let be a unit modulo and let be a positive integer. To prove that is its multiplicative order, it is necessary and sufficient to check
The first check makes the true order a divisor of . If , choose a prime divisor of ; then , contradicting the second check. Conversely, if , no smaller positive exponent can return to one.
For example, alone does not prove order six: the divisor gives and rejects it. The candidate three passes, since but . Once the prime factorization of is supplied, this certificate needs one modular exponentiation per distinct prime factor, plus the return check. The factorization itself is separate work. The candidate has no prime divisors and is accepted exactly when .
The fact that a nontrivial factor usually appears before a full return does not say that either event appears soon. Each iteration of the RSA cycling attack is inexpensive, but the number of iterations can be enormous. The multiplicative orders governing returns modulo and need not be small, and writing down a large return exponent does not provide a fast way to search the preceding iterations.
If this procedure factored arbitrary well-generated RSA cryptosystem moduli in feasible time with substantial success, it would solve the associated integer factorization problem efficiently. If it instead rapidly returned the predecessor of a ciphertext without factoring, it would solve the RSA inversion problem. Both are intended to be infeasible for appropriate parameters. Efficient integer factorization certainly breaks RSA cryptosystem security; the reverse implication for general RSA inversion problem algorithms is not known.
Thus the stated observation alone provides no serious general attack on well-generated parameters. It also does not prove a lower bound: special moduli or messages with short cycles can be weak, and the hardness claims are computational assumptions.
Let be the multiplicative order of modulo . Use Euclidean division to write , . Since ,
If , minimality of forces , so divides . Conversely, immediately gives . For negative integers , powers are interpreted using the multiplicative inverse and the same argument applies.
Apply the result to , using Fermat's little theorem. Then , equivalently
If with an odd prime, then but . The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes necessary.
For sufficiency, suppose and put , an even integer. Pair opposite factors in the factorial:
Wilson's theorem gives , explicitly producing a square root of minus one modulo a prime. Thus
For , Euler's theorem allows , since are coprime integers. At every congruence holds and one may take . Let be the multiplicative order of modulo . Write a nonnegative exponent with using the Euclidean division. Then , so implies by minimality of . Thus . Negative exponents, if included, give the same conclusion using the inverse residue of .
A prime divisor of a Fermat number is odd, and satisfies . Therefore , so its multiplicative order divides . It does not divide , since modulo the odd prime. Every divisor of is a power of two, hence
By Fermat's little theorem and the divisibility just proved, , giving .
Let be a unitary operator and suppose initially that the target is an eigenstate with , . Use control qubits, so . Hadamard gates prepare the uniform superposition . For each binary control position , apply the controlled unitary gate . The resulting state is
Apply the inverse quantum Fourier transform, with convention , and measure the control. The exact amplitude and probability are
For an exactly representable phase , orthogonality of roots of unity makes the outcome certain. Otherwise the finite geometric series gives
The estimate is , with phases interpreted modulo one.
To prove an error bound, choose a nearest label to on the circular grid and put in the interval . For , concavity of sine on gives , while . Therefore the nearest-integer success bound for quantum phase estimation is
Here . At an exact grid point the probability is one. If two nearest labels tie, either one separately has the displayed lower bound.
For high confidence one can prove a stronger quantum phase estimation tail bound. Let be the centered distance between and , chosen with . The denominator estimate implies away from the exact-phase case. A label at circular integer distance from has , and there are at most two labels at each such distance. For , summing the tails gives
On the complementary event the circular phase error is at most . Thus, for desired bits of accuracy, take with and to obtain
Taking makes the right side at most . This adds only control qubits. Efficient QFT is not by itself a guarantee of efficient controlled powers of an arbitrary : implementing them by repeated oracle calls uses calls. The modular-arithmetic application has efficient powers, as follows.
Assume and , and let be the multiplicative order of modulo . Define the unitary operator on , and extend it as the identity on unused computational-basis labels of the binary register. Coprimality makes multiplication a permutation, so this extension really is unitary. The orbit of consists of the distinct states . Its modular multiplication eigenstates are
The last relation follows by shifting the index cyclically; orthogonality follows from the finite Fourier sum. We do not need to know to prepare one of these eigenstates: the readily prepared target obeys
Running quantum phase estimation on this state produces the mixture of the eigenphase distributions, each with weight , because the target eigenstates are orthogonal. Thus it samples a uniformly random phase label and estimates with the bounds just proved. Equivalently the state before the inverse QFT is , which is obtained by quantum modular exponentiation directly.
The controlled power multiplies by , whose constant is computed by repeated squaring. Under the assumed efficient modular exponentiation, these controlled multiplications and the QFT use a number of gates polynomial in the register lengths. Taking requires only phase qubits. The nearest-label event has probability at least and yields an estimate within of . Since , continued-fraction recovery in quantum order finding then identifies the reduced fraction . The denominator is , not necessarily : when and are coprime it is the desired order, and when they are not it is only a divisor. One may test candidate denominators using modular exponentiation and repeat with fresh samples; denominators from successful samples can also be combined by a least common multiple. The probability of a nearest-label sample with coprime to is at least . These qualifications explain exactly what the phase estimate yields without falsely assuming that the unknown order or an eigenstate was available at the start.