{
  "id": "oai:papers.qnfo.org:spectral-gap-on-bruhat-tits-trees-as-a-deterministic-primality-test",
  "slug": "spectral-gap-on-bruhat-tits-trees-as-a-deterministic-primality-test",
  "title": "Spectral Gap on Bruhat–Tits Trees as a Deterministic Primality Test",
  "authors": [
    "Rowan Brad Quni-Gudzinas"
  ],
  "abstract": "Primality testing is a prerequisite for RSA key generation, yet current deployments rely on probabilistic algorithms such as Miller–Rabin that admit rare composite “liars”. A deterministic polynomial‑time alternative would eliminate this residual risk and simplify certification. We encode an odd integer N as a p‑adic automorphism γ_NinAut(T_p) of the (p + 1)‑regular Bruhat–Tits tree and examine the spectrum of the combinatorial Laplacian Δ_γ_N on the depth‑D=lceillog_p Nrceil quotient graph. Assuming the exponential‑mixing result of [1] and the branch description of [2], we conjecture a spectral‑gap dichotomy: primes are expected to satisfy λ₁≥(p + 1)-2√p, while composites are conjectured to obey λ₁≤ C/D with an assumed constant C=2; neither bound is derived in this paper. For p=2, D=6, an assumed mean eigenvalue μ≈1.984 yields a projected gap δ=2-μ≈0.016, exceeding a working threshold $0.01$. The algorithm runs in O((log N)⁶) bit‑operations. If the dichotomy holds, RSA implementations could replace probabilistic tests with a provably correct deterministic step, removing probabilistic error from key generation.",
  "abstract_markdown": "Primality testing is a prerequisite for RSA key generation, yet current deployments rely on probabilistic algorithms such as Miller–Rabin that admit rare composite “liars”. A deterministic polynomial‑time alternative would eliminate this residual risk and simplify certification. We encode an odd integer $N$ as a $p$‑adic automorphism $\\gamma_N\\in\\operatorname{Aut}(\\mathcal{T}_p)$ of the $(p\\!+\\!1)$‑regular Bruhat–Tits tree and examine the spectrum of the combinatorial Laplacian $\\Delta_{\\gamma_N}$ on the depth‑$D=\\lceil\\log_p N\\rceil$ quotient graph. Assuming the exponential‑mixing result of [1] and the branch description of [2], we conjecture a spectral‑gap dichotomy: primes are expected to satisfy $\\lambda_1\\ge(p\\!+\\!1)-2\\sqrt{p}$, while composites are conjectured to obey $\\lambda_1\\le C/D$ with an assumed constant $C=2$; neither bound is derived in this paper. For $p=2$, $D=6$, an assumed mean eigenvalue $\\mu\\approx1.984$ yields a projected gap $\\delta=2-\\mu\\approx0.016$, exceeding a working threshold $0.01$. The algorithm runs in $O((\\log N)^6)$ bit‑operations. If the dichotomy holds, RSA implementations could replace probabilistic tests with a provably correct deterministic step, removing probabilistic error from key generation.",
  "date": "2026-10-20",
  "first_published": "2026-10-20",
  "last_revised": "2026-10-20T05:21:19Z",
  "modified": "2026-10-20T05:21:19Z",
  "version": "1.1.0",
  "version_count": 2,
  "language": "en",
  "keywords": [],
  "quality_tags": [
    "High-quality scholarly research",
    "open-access scholarly work",
    "versioned research publication"
  ],
  "quality_label": "High-quality scholarly research",
  "quality_basis": "QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
  "quality_evidence_url": "https://qnfo.org/about",
  "peer_review_status": "Not independently peer-reviewed",
  "resource_type": "ScholarlyArticle",
  "doi": null,
  "doi_url": null,
  "url": "https://papers.qnfo.org/papers/spectral-gap-on-bruhat-tits-trees-as-a-deterministic-primality-test",
  "license_url": "https://legal.qnfo.org/",
  "license_spdx": null,
  "sha256": "73004af592bd0ba49f151ba5cbb278652a6914d53ccf0bc4cf7ffab2ba805d3e",
  "version_url": "https://papers.qnfo.org/papers/spectral-gap-on-bruhat-tits-trees-as-a-deterministic-primality-test/v/1.1.0",
  "datacite": {
    "schemaVersion": "http://datacite.org/schema/kernel-4",
    "identifiers": [
      {
        "identifier": "https://papers.qnfo.org/papers/spectral-gap-on-bruhat-tits-trees-as-a-deterministic-primality-test",
        "identifierType": "URL"
      }
    ],
    "creators": [
      {
        "name": "Rowan Brad Quni-Gudzinas",
        "nameType": "Personal",
        "nameIdentifiers": [
          {
            "nameIdentifier": "https://orcid.org/0009-0002-4317-5604",
            "nameIdentifierScheme": "ORCID",
            "schemeUri": "https://orcid.org"
          }
        ]
      }
    ],
    "titles": [
      {
        "title": "Spectral Gap on Bruhat–Tits Trees as a Deterministic Primality Test"
      }
    ],
    "publisher": "QNFO",
    "publicationYear": "2026",
    "resourceType": {
      "resourceTypeGeneral": "Text",
      "resourceType": "ScholarlyArticle"
    },
    "subjects": [
      {
        "subject": "High-quality scholarly research",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "open-access scholarly work",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      },
      {
        "subject": "versioned research publication",
        "subjectScheme": "QNFO publisher classification",
        "schemeUri": "https://qnfo.org/about"
      }
    ],
    "dates": [
      {
        "date": "2026-10-20",
        "dateType": "Issued"
      },
      {
        "date": "2026-10-20",
        "dateType": "Updated"
      }
    ],
    "language": "en",
    "version": "1.1.0",
    "rightsList": [
      {
        "rightsUri": "https://legal.qnfo.org/"
      }
    ],
    "descriptions": [
      {
        "description": "Primality testing is a prerequisite for RSA key generation, yet current deployments rely on probabilistic algorithms such as Miller–Rabin that admit rare composite “liars”. A deterministic polynomial‑time alternative would eliminate this residual risk and simplify certification. We encode an odd integer N as a p‑adic automorphism γ_NinAut(T_p) of the (p + 1)‑regular Bruhat–Tits tree and examine the spectrum of the combinatorial Laplacian Δ_γ_N on the depth‑D=lceillog_p Nrceil quotient graph. Assuming the exponential‑mixing result of [1] and the branch description of [2], we conjecture a spectral‑gap dichotomy: primes are expected to satisfy λ₁≥(p + 1)-2√p, while composites are conjectured to obey λ₁≤ C/D with an assumed constant C=2; neither bound is derived in this paper. For p=2, D=6, an assumed mean eigenvalue μ≈1.984 yields a projected gap δ=2-μ≈0.016, exceeding a working threshold $0.01$. The algorithm runs in O((log N)⁶) bit‑operations. If the dichotomy holds, RSA implementations could replace probabilistic tests with a provably correct deterministic step, removing probabilistic error from key generation.",
        "descriptionType": "Abstract"
      },
      {
        "description": "Publisher quality classification: High-quality scholarly research. QNFO publisher classification for open-access, versioned research with a public revision history and reader correction channel; this is not a claim of independent peer review.",
        "descriptionType": "Other"
      },
      {
        "description": "Peer review status: Not independently peer-reviewed",
        "descriptionType": "Other"
      }
    ],
    "formats": [
      "text/html"
    ]
  }
}