用$4 p=u^2+11 v^2$判断p是否为素数？

hbghlyj

reference.wolfram.com/language/PrimalityProvi … /ProvablePrimeQ.html
在Mathematica中判断p是否为素数，並設置PrimeQMessages -> True

1. p = 7146330773479944228428207205564989096279426988634539762839671
2. ProvablePrimeQ[p, "PrimeQMessages" -> True]

Copy the Code

輸出：
Prime candidate $p=7146330773479944228428207205564989096279426988634539762839671$.
Trial division vector has length 10000.
Class table index $=2$, discriminant $=-11$.
$4 p=u^2+11 v^2$. Trying trial division.
Trial division successful.
Finding root of a polynomial of order 1 mod $p$.
Prime candidate $p=10192561134679267567916180128088389927110688089848260241$.
Trial division vector has length 5000.
Class table index $=1$, discriminant $=-7$.
$4 p=u^2+7 v^2$. Trying trial division.
Class table index $=2$, discriminant $=-11$.
Class table index $=3$, discriminant $=-19$.
$4 p=u^2+19 v^2$. Trying trial division.
Trial division successful.
Finding root of a polynomial of order $1 \bmod p$.
上面好像用到了$4 p=u^2+11 v^2$来判断p是否为素数？这是如何判断的呢

hbghlyj

1. Reduce[28585323093919776913712828822259956385117707954538159051358684 == u^2 + 11 v^2, {u, v}, Integers]

Copy the Code

u = 1879910095543973176950636453140, v = 1509101512538070887203232553738
为什么判断p为素数会用到这个不定方程呢

hbghlyj

这是 ProvablePrimeQ 的另一个例子

  In[1]:= FerrierPrime = (2^148 + 1)/17;

  In[2]:= PrimeQ[FerrierPrime] // Timing

  Out[2]= {0.01 Second, True}



  In[3]:= ProvablePrimeQ[FerrierPrime,

          "Certificate" -> True] // Timing

  Out[4]= {0.04 Second,{True,

    {20988936657440586486151264256610222593863921,17,

      {2,{3,2,{2}},{5,2,{2}},{7,3,{2,{3,2,{2}}}},

      {13,2,{2,{3,2,{2}}}},{19,

      2,{2,{3,2,{2}}}},{37,2,{2,{3,2,{2}}}},{73,5,{

        2,{3,2,{2}}}},{97,5,{2,{3,2,{2}}}},{109,

        6,{2,{3,2,{2}}}},{241,7,{2,{3,2,{2}},{5,2,{

        2}}}},{257,3,{2}},{433,5,{2,{3,2,{2}}}},{

        577,5,{2,{3,2,{2}}}},{673,5,{2,{3,2,{2}},{

        7,3,{2,{3,2,{2}}}}}},{38737,5,{2,{3,2,{2}},

        {269,2,{2,{67,2,{2,{3,2,{2}},{11,2,{2,{5,

        2,{2}}}}}}}}}},{487824887233,5,{2,{3,2,{2}},{

        1091,2,{2,{5,2,{2}},{109,6,{2,{3,2,{2}}}}}},

        {28751,14,{2,{5,2,{2}},{23,5,

        {2,{11,2,{2,{5,2,{2}}}}}}}}}}}}}}

使用 PrimalityCertificate 验证$(2^{148} + 1)/17$为素数

那么上面的 PrimalityCertificate 的底层原理是什么呢？
出现 {2,{3,2,{2}} 是什么意思