primitive root modulo n
Let an agent define primitive roots modulo n precisely, state when they exist and how many there are, test and find them for a given modulus, and relate them to orders, discrete logarithms and cryptography without giving operational key material.
Bundle → Layer → Finding → Questions Filled
4 bundles · 8 layers · 8 findings · 16 questions
Define The definition.
Definition
Definition.
Definition
Definition.
- What is a primitive root modulo n, and how does it relate to multiplicative order? definition
- Is the question about primitive roots modulo n or about complex roots of unity? boundary
Existence
Existence theorem.
Existence
Existence.
- For which n do primitive roots exist, and how many are there? definition
- Which entry fits the multiplicative group modulo n? action
Compute Finding and testing.
Test
Testing.
Test
Test.
- How is an integer tested as a primitive root using the prime factors of phi of n? action
- What is the result for the modulus in question? measurement
Find
Finding.
Find
Find.
- How are primitive roots found in practice, and what is known about the least primitive root? provenance
- Which references are standard? provenance
Use Applications.
Logarithm
Discrete logarithms.
Logarithm
Logarithm.
- How do primitive roots define discrete logarithms and index tables? definition
- Which entry fits the discrete logarithm problem? action
Cryptography
Cryptographic use.
Cryptography
Cryptography.
- How are generators used in protocols such as Diffie-Hellman, in general terms? provenance
- Is the user asking for parameter choices for a real system, which needs security guidance? boundary
Theory Results and history.
Results
Theorems and conjectures.
Results
Results.
- What is proved and conjectured about primitive roots, such as Artin conjecture? provenance
- What is proven versus conjectured? boundary
History
History.
History
History.
- How did Euler, Lagrange and Gauss develop the theory of primitive roots? provenance
- Which entry fits Gauss? action
Classifiers Filled
- Family
- Thing Registry
- Category
- Cross-cutting context
- Entry kind
- thing
- Plane
- XCT
- Domain
- XCT.QTY
What it is Filled
In number theory, an integer g such that every integer coprime to n is congruent to some power of g modulo n, that is, g generates the multiplicative group of integers modulo n; primitive roots exist exactly when n is 1, 2, 4, a power of an odd prime, or twice a power of an odd prime, and they underlie discrete logarithms and several cryptographic protocols.
Why it exists Filled
Let an agent define primitive roots modulo n precisely, state when they exist and how many there are, test and find them for a given modulus, and relate them to orders, discrete logarithms and cryptography without giving operational key material.
Distinguishing features Filled
- Generator of the multiplicative group modulo n
- Existence depends on the form of n
- Order equals Euler phi of n
- Basis of the discrete logarithm
What robots and AI may and may not do Filled
Must not
- State that a primitive root exists for an n where it does not.
- Use small or weak parameters in a real security system.
- Present a conjecture, such as Artin's, as proven.
Only with a human decision
- Choosing parameters for a cryptographic system that protects people's data.
May
- Compute and check primitive roots modulo n and explain when they exist.
- Use primitive roots in teaching and in authorized cryptographic work.
Moral aspects Filled
- Mistakes in number-theoretic parameters can weaken cryptography that protects people.
- Mathematical credit matters to researchers.
Who is affected
- Users of cryptographic systems
- Students
Owners Filled
Steward
Nobody owns the concept; it belongs to mathematics.
Links to other meta-models Filled
parent
- Q4349566 - registry parent class
- Q7366581 - registry parent class
related
- root of unity modulo n - the case of maximal order
- multiplicative group of integers modulo n - the group it generates
- discrete logarithm - the inverse problem
- Euler totient function - counts and orders
What else AI and robots need to interact with it Filled
Identity and identifiers required Filled
- Vercy registry: vr.tr.primitive-root-modulo-n
- Wikidata: Q948010 (https://www.wikidata.org/wiki/Q948010)
- OEIS: A001918 least primitive root of the nth prime
Direct properties not applicable Not applicable
- number of primitive roots when they exist: phi of phi of n integers - Euler totient applied twice
- smallest primitive root modulo 7: 3 integer - example
Plane XCT: no invented physical properties.
Recognition optional Filled
- Multiplicative order equal to Euler phi of n
- Exists only for n equal to 1, 2, 4, p to the k, or 2 p to the k with p an odd prime
- A primitive nth root of unity in the complex numbers is a related but different object
- Not visible; a property of an integer relative to a modulus.
Capabilities and actions required Filled
- test whether an integer is a primitive root modulo n
- find primitive roots for a modulus
- state the existence theorem and count
- explain the link to discrete logarithms
Hazards and failure modes required Filled
- Assuming a primitive root exists for every modulus
- Confusing with complex roots of unity
- Using small or weak generators in cryptographic settings, which belongs to security guidance
Standards and interfaces required Filled
- No regulation; definitions follow standard number theory texts
Context of use required Filled
- Generating the multiplicative group modulo n; basis for discrete logarithms.
- primitive roots modulo a prime
- primitive roots modulo prime powers and twice prime powers
- least primitive roots as a studied sequence
- generalisations to generators of cyclic subgroups
Sources Filled
- Wikidata item Q948010: primitive root modulo n - identity and sense of the item
- Wikipedia: Primitive root modulo n - general description of the item
Open questions
- Should the discrete logarithm be a separate entry?
- How should OEIS sequences be linked?
- How should Artin conjecture and related open problems be recorded?
Machine files
Provenance
thing registry research (pass 2) · unreviewed
Built from: models/things/publications/thing-q948010/spec.json