"""T729: primitive Frobenius polynomials of Fermat varieties.

Requires SageMath and numberdb: sage -pip install numberdb
Run sage -python generate.py to compute/check without writing.
Run sage -python generate.py --publish to fill the authorized target draft.
Parameters n,d,p refer to X_1^d+...+X_(n+1)^d=X_0^d.
Exact binary Jacobi sums are assembled into higher sums; zero intermediate
character products use J_(k+1)=-Q*J_k rather than a nontrivial-character rule.
All ordered nonzero character tuples and their p-orbits are retained.
Sources: Griffon arXiv:1612.08721v2, Theorem 2.3/Remark 2.4; Brünjes
arXiv:math/0301186, Theorem 4.6; cyclic-block descent at nonsplit primes.
No numerical reconstruction or rounding is used. Outputs are exact ZZ[T].
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.number_field.number_field import CyclotomicField
from sage.rings.finite_rings.finite_field_constructor import GF
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from functools import lru_cache
from itertools import product
from math import gcd, comb
import os, sys, json, time

R = PolynomialRing(ZZ, 'T')
PRIMES = (2,3,5,7,11,13,17,19,23,29,31)

def selection():
    for n,d in [(2,d) for d in range(3,7)]+[(4,3)]:
        for p in PRIMES:
            if d%p and (n==2 or p>3):
                yield {'n':n,'d':d,'p':p}

def orbits(n,d,p):
    todo={a for a in product(range(1,d),repeat=n+2) if sum(a)%d==0}
    answer=[]
    while todo:
        a=min(todo); b=a; orb=[]
        while b not in orb:
            orb.append(b); b=tuple(p*x%d for x in b)
        assert b==a
        todo.difference_update(orb);answer.append((a,len(orb)))
    assert sum(r for a,r in answer)==((d-1)**(n+2)+(d-1))//d
    return answer

@lru_cache(maxsize=8)
def binary_sums(p,r,m):
    q=p**r; assert (q-1)%m==0
    F=GF(q,'a'); g=F.multiplicative_generator(); K=CyclotomicField(m); z=K.gen()
    logs={};x=F.one()
    for j in range(q-1):
        logs[x]=j%m;x*=g
    assert x==1 and len(logs)==q-1
    hist=[[0]*m for _ in range(m)]
    for x,j in logs.items():
        if x!=1:hist[j][logs[1-x]]+=1
    roots=[z**k for k in range(m)]
    ans={}
    for s in range(1,m):
        for t in range(1,m):
            c=[0]*m
            for i in range(m):
                for j in range(m):c[(s*i+t*j)%m]+=hist[i][j]
            ans[s,t]=sum((ZZ(c[k])*roots[k] for k in range(m)),K.zero())
    return K,ans

@lru_cache(maxsize=None)
def compute(n,d,p):
    assert n>=2 and n%2==0 and d>=3 and ZZ(p).is_prime() and d%p
    K=CyclotomicField(d); S=PolynomialRing(K,'T'); T=S.gen(); result=S.one(); evidence=[]
    for a,r in orbits(n,d,p):
        h=d
        for x in a:h=gcd(h,x)
        m=d//h; aa=[x//h for x in a]; q=p**r
        L,B=binary_sums(p,r,m)
        j=L.one();s=aa[1]
        for t in aa[2:]:
            j *= -q if s==0 else B[s,t]
            s=(s+t)%m
        assert s==(-aa[0])%m and s!=0
        # This higher Jacobi sum already includes chi_0(-1) for our model.
        beta=K(j)
        assert beta*beta.conjugate()==q**n
        result*=1-beta*T**r
        evidence.append({'a':list(a),'r':r,'beta':str(beta)})
    out=R([ZZ(c) for c in result.list()]); b=((d-1)**(n+2)+(d-1))//d; w=n//2
    assert out[0]==1 and out.degree()==b
    eps=out[b]//ZZ(p)**(w*b);assert eps in (-1,1) and out[b]==eps*ZZ(p)**(w*b)
    for k in range(b//2+1):
        assert out[b-k]==eps*ZZ(p)**(w*(b-2*k))*out[k]
    for k,c in enumerate(out.list()):assert abs(c)<=comb(b,k)*ZZ(p)**(w*k)
    return out,evidence

class FermatFrobenius(numberdb.Generator):
    table='T729'
    parameters=('n','d','p')
    type='Z[]'
    rigour='exact'
    digits=100
    def enumerate(self):yield from selection()
    def value(self,params,digits):
        return compute(*(int(params[k]) for k in self.parameters))[0]

if __name__=='__main__':
    gen=FermatFrobenius()
    if '--publish' in sys.argv:
        print(gen.publish())
    else:
        for params in selection():
            t=time.monotonic();v,e=compute(*(params[k] for k in gen.parameters))
            print(json.dumps({'params':params,'coefficients':[str(c) for c in v.list()],
                              'orbits':e,'seconds':time.monotonic()-t}),flush=True)
