← Back to catalogue
Published

probable prime

vr.tr.probable-prime · thing-q2654835

Let an agent define probable primes and the tests that produce them, relay their use in cryptography and record searches, and distinguish probable primes from proven primes and pseudoprimes.

Thing Registry Cross-cutting context XCT.QTY
Bundle → Layer → Finding → QuestionsClassifiersWhat it isWhy it existsDistinguishing featuresWhat robots and AI may and may not doMoral aspectsOwnersLinks to other meta-modelsIdentity and identifiersDirect propertiesRecognitionCapabilities and actionsHazards and failure modesStandards and interfacesContext of useSources

Bundle → Layer → Finding → Questions Filled

4 bundles · 8 layers · 8 findings · 16 questions

Define Definition.

Definition

Definition.

Definition

Definition.

  1. What is a probable prime, and how does it differ from a proven prime and a pseudoprime? definition
  2. Is the question about probable primes, proven primes or pseudoprimes? boundary

Tests

Tests.

Tests

Tests.

  1. How do Fermat, Miller-Rabin and Baillie-PSW tests work, and what are their error bounds? definition
  2. Which entry fits the specific test? action
Use Use in practice.

Cryptography

Cryptography.

Cryptography

Cryptography.

  1. How are probable primes generated for keys, and what do standards require? provenance
  2. Which references are standard? provenance

Records

Record searches.

Records

Records.

  1. What are the largest known probable primes, and how are they later proven? provenance
  2. Is the information current? boundary
Theory Theory.

Pseudoprimes

Pseudoprimes.

Pseudoprimes

Pseudoprimes.

  1. What pseudoprimes and Carmichael numbers defeat simple tests? provenance
  2. Which entry fits Carmichael number? action

Proof

Proving primality.

Proof

Proof.

  1. How do deterministic tests such as AKS and ECPP prove primality? provenance
  2. Which sources are cited? provenance
Context History.

History

History.

History

History.

  1. How did probabilistic primality testing develop from Fermat to Rabin and beyond? provenance
  2. Which entry fits the history of computational number theory? action

Terminology

Terminology.

Terminology

Terminology.

  1. Where does the term industrial-grade prime come from? provenance
  2. Which entry fits primality test? action

Classifiers Filled

Family
Thing Registry
Category
Cross-cutting context
Entry kind
thing
Plane
XCT
Domain
XCT.QTY
Other names and narrower kinds
industrial-grade prime

What it is Filled

An integer that satisfies a specified necessary condition for primality, such as a condition checked by a Fermat, Miller-Rabin or Baillie-PSW test, without thereby establishing a proof of primality. Composite numbers that satisfy such conditions are called pseudoprimes relative to the condition used. Passing a necessary condition alone does not establish a high likelihood of primality; confidence depends on the test, its assumptions and how candidates are selected. Probable primes, sometimes called industrial-grade primes, are used in cryptography where the required assurance does not demand a primality proof, and large probable primes such as certain Mersenne and repunit candidates are reported before proofs are available.

Why it exists Filled

Let an agent define probable primes and the tests that produce them, relay their use in cryptography and record searches, and distinguish probable primes from proven primes and pseudoprimes.

Distinguishing features Filled

  • A probable prime satisfies a specified necessary condition for primality.
  • The assurance provided depends on the test and its assumptions.
  • Probable-prime tests can offer fast screening.
  • Probable primes have cryptographic uses.
  • Passing a probable-prime test is distinct from proving primality.

What robots and AI may and may not do Filled

Must not

  • Present a probable prime as proven prime.
  • Use a test known to be fooled by pseudoprimes, such as a single Fermat base, for security keys.
  • Accept externally supplied primes for cryptography without independent testing.
  • Infer high confidence in primality merely from passing an arbitrary necessary condition.

Only with a human decision

  • A human must approve prime generation methods for production cryptography.

May

  • Run primality tests and report which tests were used, their assumptions and any applicable error bounds.
  • Mark a number as probable prime, not proven prime, until a proof is given.

Moral aspects Filled

  • Weak primality checks have led to breakable cryptographic keys.
  • Mathematical records rely on honest distinction between probable and proven.

Who is affected

  • Users of cryptographic systems
  • Mathematicians
  • Software developers

Owners Filled

Steward

The public: held in common as mathematical knowledge.

Links to other meta-models Filled

parent

  • Q16317911 - registry parent class

related

  • positive integer - in registry terms
  • primality test - such as Miller-Rabin
  • pseudoprime - a composite that passes
  • public-key cryptography - for key generation

What else AI and robots need to interact with it Filled

Identity and identifiers required Filled

  • Vercy registry: vr.tr.probable-prime
  • Wikidata: Q2654835 (https://www.wikidata.org/wiki/Q2654835)

Direct properties not applicable Not applicable

  • Miller-Rabin error bound: at most 1/4 per round - for composites

Plane XCT: no invented physical properties.

Recognition optional Filled

  • Integer passing probabilistic primality tests
  • Fermat, Miller-Rabin, Baillie-PSW probable primes
  • A proven prime has a certificate; a pseudoprime is a composite that passes
  • Not a visible object; a number with a test result.

Capabilities and actions required Filled

  • define and explain tests
  • relay use in cryptography
  • relay record searches
  • distinguish from proven primes

Hazards and failure modes required Filled

  • Treating probable as proven
  • Insufficient test rounds
  • Adversarial composites against weak tests

Standards and interfaces required Filled

  • FIPS 186 and other standards specifying probable prime generation
  • No regulation of the concept

Context of use required Filled

  • Efficient primality assurance in practice.
  • Fermat probable primes
  • strong or Miller-Rabin probable primes
  • Lucas and Baillie-PSW probable primes
  • industrial-grade primes in cryptography
  • large probable primes in record lists

Sources Filled

  1. Wikidata item Q2654835: probable prime - identity and sense of the item
  2. Wikipedia: Probable prime - general description of the item

Open questions

  • Should Miller-Rabin and Baillie-PSW be the primary linked entries?
  • How should cryptographic standards be linked?
  • How should record probable primes be recorded?

Machine files

Card as JSON Specification Card backlog vercy.card/1

Provenance

thing registry research (pass 2) · unreviewed

Built from: models/things/publications/thing-q2654835/spec.json