 |
PrimeQCertificate
PrimeQCertificate[n]
gives a certificate that n is prime or that n is composite.
更多信息
- To use
, you first need to load the Primality Proving Package using Needs["PrimalityProving`"]. 
uses the Pratt certificate and the Atkin-Morain certificate for primality.- A certificate of compositeness is a list of three integers, either
or 
, with 
. - A prime
always satisfies 
. The certificate 
can be used to show that n is composite by demonstrating that 
. - Any number
whose square is 
for 
prime must satisfy 
. The certificate 
can be used to show that n is composite by demonstrating that 
and 
. - A certificate of primality consists of a recursive list of certificates which prove that
is a prime if one or more smaller numbers are prime as well. 
has the same options as ProvablePrimeQ.
范例打开所有单元
基本范例 (2)
| In[1]:= |
A certificate that can be used to prove that 
is a prime:
| In[2]:= |
| Out[2]= |  |
The same certificate can be obtained by using ProvablePrimeQ with the option "Certificate"->True:
| In[3]:= |
| Out[3]= |  |
| In[1]:= |
A certificate that can be used to prove that 
is composite:
| In[2]:= |
| Out[2]= |  |
The output is a list of three integers that indicate 
is composite, and that it violates Fermat's little theorem for primes, 
if 
is prime:
| In[3]:= |
| Out[3]= |  |
