{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R13",
  "content_hash": null,
  "slug": "apn256-artifact-differential-audit",
  "type": "artifact",
  "title": "Exact differential-uniformity verifier and power-permutation scan",
  "summary": "Standard-library Python checks every derivative row and confirms that the 128 power permutations on F_256 have minimum differential uniformity four.",
  "relevance": "For An APN permutation of the 256-element field, record apn256-artifact-differential-audit (“Exact differential-uniformity verifier and power-permutation scan”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python checks every derivative row and confirms that the 128 power permutations on F_256 have minimum differential uniformity four.",
  "relevance_source": "recorded",
  "body": "The program represents \\(\\mathbb F_{2^8}\\) with the AES polynomial\n\\[\nx^8+x^4+x^3+x+1\n\\]\nand computes every derivative value directly. It checks all 128 exponents \\(d\\) with \\(\\gcd(d,255)=1\\), exactly the exponents for which \\(x^d\\) permutes \\(\\mathbb F_{256}\\). The minimum differential uniformity is four. It is attained for\n\\[\nd\\in\\{127,191,223,239,247,251,253,254\\}.\n\\]\nThis exhausts the monomial-permutation family and does not address general lookup tables.\n\nTwo controls expose the even-dimension obstruction. Over \\(\\mathbb F_{2^7}\\), \\(x^3\\) is both a permutation and APN. Over \\(\\mathbb F_{2^8}\\), the same Gold map remains APN but takes each nonzero cube value three times. The inverse permutation \\(x^{254}\\) on \\(\\mathbb F_{256}\\) has differential uniformity four. The canonical report has SHA-256 digest `7a35e41b9243f97ac244c69402b8bbf0a8ad747db186329e0d509ab923d4c9a8`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all 128 power permutations x^d on F_256, together with x^3 on F_128 and the nonpermuting APN map x^3 on F_256",
    "bounds": {
      "dimension": {
        "min": 7,
        "max": 8
      },
      "f256_power_permutation_exponents": {
        "min": 128,
        "max": 128
      },
      "derivative_directions_per_f256_function": {
        "min": 255,
        "max": 255
      },
      "inputs_per_f256_derivative": {
        "min": 256,
        "max": 256
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_computation",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3, standard library only",
    "citation": {
      "url": "https://arxiv.org/abs/2606.11967",
      "locator": "Self-contained Python standard-library computation executed by TheoremDB entry research on 2026-07-25"
    },
    "inline_source": [
      "from collections import Counter",
      "from hashlib import sha256",
      "from json import dumps",
      "from math import gcd",
      "",
      "def mul(a,b,n,poly):",
      "    mask=(1<<n)-1",
      "    z=0",
      "    while b:",
      "        if b&1: z ^= a",
      "        b >>= 1",
      "        carry=a&(1<<(n-1))",
      "        a=(a<<1)&mask",
      "        if carry: a ^= poly&mask",
      "    return z",
      "",
      "def power(a,e,n,poly):",
      "    z=1",
      "    while e:",
      "        if e&1: z=mul(z,a,n,poly)",
      "        a=mul(a,a,n,poly)",
      "        e>>=1",
      "    return z",
      "",
      "def table_power(n,poly,d):",
      "    return [0 if x==0 else power(x,d,n,poly) for x in range(1<<n)]",
      "",
      "def du(table):",
      "    N=len(table)",
      "    return max(max(Counter(table[x]^table[x^a] for x in range(N)).values()) for a in range(1,N))",
      "",
      "def audit(n,poly,d):",
      "    table=table_power(n,poly,d)",
      "    return {'n':n,'polynomial_hex':hex(poly),'exponent':d,'permutation':len(set(table))==len(table),'differential_uniformity':du(table)}",
      "",
      "seven=audit(7,0x83,3)",
      "eight_gold=audit(8,0x11b,3)",
      "eight_inverse=audit(8,0x11b,254)",
      "permutation_exponents=[d for d in range(1,255) if gcd(d,255)==1]",
      "power_uniformities={d:du(table_power(8,0x11b,d)) for d in permutation_exponents}",
      "minimum=min(power_uniformities.values())",
      "minimizers=[d for d,u in power_uniformities.items() if u==minimum]",
      "report={'known_odd_dimension_example':seven,'even_dimension_gold_obstruction':eight_gold,'f256_inverse':eight_inverse,'f256_power_permutation_scan':{'exponents_checked':len(permutation_exponents),'minimum_differential_uniformity':minimum,'minimizing_exponents':minimizers}}",
      "assert seven=={'n':7,'polynomial_hex':'0x83','exponent':3,'permutation':True,'differential_uniformity':2}",
      "assert eight_gold=={'n':8,'polynomial_hex':'0x11b','exponent':3,'permutation':False,'differential_uniformity':2}",
      "assert eight_inverse['permutation'] and eight_inverse['differential_uniformity']==4",
      "assert len(permutation_exponents)==128",
      "assert minimum==4 and minimizers==[127,191,223,239,247,251,253,254]",
      "payload=dumps(report,sort_keys=True,separators=(',',':'))",
      "digest=sha256(payload.encode()).hexdigest()",
      "assert digest=='7a35e41b9243f97ac244c69402b8bbf0a8ad747db186329e0d509ab923d4c9a8'",
      "print(payload)",
      "print('report_sha256='+digest)"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2606.11967",
    "locator": "Self-contained Python standard-library computation executed by TheoremDB entry research on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R16",
      "title": "Existence of an APN permutation on F_256 remains open",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "R14",
      "title": "Classification and computational-search audit",
      "object_type": "attempt",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "apn-permutation-f256",
      "title": "apn permutation f256",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}