[分析] 一個質數檢測的方法

[kilva (嗡嗡)]

首先，我觀察到一個質數會有的性質。
然後，有一些非質數也會滿足該性質。
最後，上述的非質數可以簡單地排除。
因此，就找出了一個質數檢測的方法。
問題，我不知道偽質數是否只有那些。

--------

接下來是正題。

假設i^2=-1，(a+ib)*(c+id)=(ac-bd)+i(ad+bc)，因此可得一二元組，其運算
為(a,b)*(c,d)=(ac-bd,ad+bc)。

接下來，推廣到三元組，設i^3=-1，
(a+ib+i^2*c)*(d+ie+i^2*f)=(ad-bf-ce)+i(ae+bd-cf)+i^2(af+be+cd)，可得
三元組的運算為(a,b,c)*(d,e,f)=(ad-bf-ce,ae+bd-cf,af+be+cd)

最後，到任意n元組，
(a1,a2,...,an)*(b1,b2,...,bn)=
(a1*b1-a2*bn-...-an*b2,
 a1*b2+a2*b1-a3*bn-...-an*b3,
 ....,
 a1*bi+a2*b{i-1}...+ai*b1-a{i+1}*bn-a{i+2}*b{n-1}-...-an*b{i+1},
 ....,
 a1*bn+...+an*b1)

造出這個n元組的目的在於，其具有下列的指數性質，
(a,b,c)^(d*e)=((a,b,c)^d)^e, (a,b,c)^(d+e)=(a,b,c)^d*(a,b,c)^e

借由上述的n元組，可觀察到對任意非n因子的質數p，
(1,1,...,1)^p%p的每個元素不是1，就是p-1。
其中，(1,1,...,1)^p%p的意思是將(1,1,...1)相乘p次後，對其每個元素餘p，
如(1,1,1)^8%8=(-85%8,85%8,171%8)=(3,5,3)
(1,1,1)^17%17=(43691%17,-43691%17,-87381%17)=(1,16,16)

但是其中有些非質數也會有相同的性質，如
(1,1,1)^4%4=(3,1,3)

不過，可以發現這些偽質數q，其q%n均會是1；亦即我們只要取一個q%n不等於
1的n，即可避免這個問題，如
(1,1,1,1,1)^191351%191351=(1,1,1,1,1)，但
(1,1,1,1,1,1)^191351%191351=(81623,109728,59071,717,717,59071)
可知，191351不是個質數。

於是，就造出了一個(似乎)可以檢測質數的方法。

請問，這個方法可用嗎？有相關證明或否證嗎？

--------

下面是上述方法用Python寫出的原始碼：

def checkprime(n):
    arity=2
    while n%arity==1:
        arity+=1
    for x in exp(arity,n,n):
        if x!=1 and x!=n-1:
            return False
    return True

def exp(arity, power, modulus):
    base = [1]*arity
    result = [1].__add__([0]*(arity-1))
    while power > 0:
        if power%2==1:
            temp = [0]*arity
            for i in range(arity):
                for j in range(i+1):
                    temp[i]+=result[j]*base[i-j]
                for j in range(i+1,arity):
                    temp[i]-=result[j]*base[arity+i-j]
            for i in range(arity):
                result[i]=temp[i]%modulus
        temp = [0]*arity
        for i in range(arity):
            for j in range(i+1):
                temp[i]+=base[j]*base[i-j]
            for j in range(i+1,arity):
                temp[i]-=base[j]*base[arity+i-j]
        for i in range(arity):
            base[i]=temp[i]%modulus
        power=power//2
    return result

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.238.104
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1541812947.A.208.html
推 RicciCurvatu: 根本不需要造這樣的東西吧 如果p 是質數 任何數的p
→ RicciCurvatu: 次放方 餘p 要嘛是0要嘛是1 基礎群論就有的結果
你是說a^p%p=a嗎？
用費馬小定理來檢測質數最麻煩的地方在於會有偽質數存在，而上述方法則似乎
可以簡單地將偽質數排除，只是我也不知道是否可100%排除。
※ 編輯: kilva (61.228.238.104), 11/10/2018 09:53:10
推 RicciCurvatu: 的確質數的結果用費馬就能解釋 下一篇有解釋你可以
→ RicciCurvatu: 把你的計算看成是在Z[x]/(p, x^n+1) , p是你想檢測
→ RicciCurvatu: 的數 然後n 是你考慮的維度， 在做quation之前 你考
→ RicciCurvatu: 慮的檢測函數是x^(n-1)+x^(n-2)+...+1 把這個函數做
→ RicciCurvatu: n次方得到什麼呢? 你回想一下如果n=1 (1+x)展開會得
→ RicciCurvatu: 到二項式 在高微度也有類似的東西 請wiki"multinomi
→ RicciCurvatu: al throrem" 你想討論的東西 就是你的p對這些係數的
→ RicciCurvatu: 整除性，有一個定理就是專門講這個整除性 Wiki"Kumm
→ RicciCurvatu: er's theorem" 我目前還不太確定這個這個定理跟你這
→ RicciCurvatu: 個推論的關係 但應該已經足夠接近答案 或是可以簡單
→ RicciCurvatu: 的問 (1+x)^n 如果n不是質數 是不是就一定有某個係
→ RicciCurvatu: 數不被n整除 這個我不太確定 但證明應該不會太trivi
→ RicciCurvatu: al
推 Sfly        : google "prime is in p"