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

[Desperato (Farewell)]

※ 引述《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)

F = field of real number

設 R_n = F[x]/(x^n+1)
即實係數多項式除以 x^n+1 的餘數的集合
則 R_n 一個環，可以做加減乘

上述的 (a_0, a_1, ..., a_(n-1))
其實就是 a_0 + a_1 x + ... + a_(n-1) x^(n-1)
並且乘法就是上面那個乘法

: 造出這個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不是個質數。
: 於是，就造出了一個(似乎)可以檢測質數的方法。
: 請問，這個方法可用嗎？有相關證明或否證嗎？

所以你的問題就變成，如果 p 不整除 n 的話

(1+x+...+x^(n-1))^p 除以 (x^n+1) 後的係數 mod p 全部是 1 或 p-1
可不可以拿來判斷 p 是個質數

如果一開始就設 F = Z/pZ 的話
那更省事 連 mod p 都免了

問題變成 p is prime
iff for any p not divide n,
the coeff. of (1+x+..._+x^(n-1))^p are all 1 or -1 in F[x]/(x^n+1)

(原始碼省略)


==============================================================

先不考慮 Z/pZ, 設 F = real number field

Let f(x) = (1+x+...+x^(n-1))^p
consider the coeff. of x^r, a_r, r = 0 to (n-1)p

a_r = # partition of repetition where
        r balls in p baskets, but each basket with at most n-1 ball

Let C(m, n) = binomial coeff. of x^n in (1+x)^m

Let H(p, r) = # partition of repetition where
                r balls in p baskets
            = C(p+r-1, r) = C(p-1+r, p-1)

Then by inc. and exc. principle
a_r = H(p, r) - C(p, 1) H(p, r-n) + C(p, 2) H(p, r-2n) ...

       p      k
    = sum (-1)  C(p, k) H(p, r-kn)
      k=0

現在 quotient 掉 (x^n+1) 之後，設係數為 b_s, s = 0 to n-1

b_s = a_s - a_(s+n) + a_(s+2n) ...

       p      t
    = sum (-1)  a
      t=0        s+tn

       p   p      t+k
    = sum sum (-1)    C(p, k) H(p, s+tn-kn)
      t=0 k=0

       p   p      t+k
    = sum sum (-1)    C(p, k) C(p-1+s+tn-kn, p-1)
      t=0 k=0

p.s. s+tn-kn < 0 iff t-k < 0, i.e. only t >= k gives nonzero C
     so t = 0 to p is actually t = k to p, let u = t-k

       p          p-k     u
    = sum C(p, k) sum (-1)  C(p-1+s+un, p-1)
      k=0         u=0


現在假設 p 是質數，p 不整除 n

則 C(p, k) != 0 (mod p) iff k = 0 or p
而且此時 C(p, k) = 1
o
設 v = p-1+s+un
則 C(v, p-1) != 0 (mod p)
   iff p not divide any of v, v-1, ..., v-p+2
   iff p divide v+1
   iff p divide s+un
而且此時 C(v, p-1) = 1 by Wilson's theorem


因此

       p      u
b_s = sum (-1)  C(p-1+s+un, p-1) + C(p-1+s, p-1)   (mod p)
      u=0

if p divide s

b_s = (-1)^0 + (-1)^p + 1 = 1  (mod p)

if p not divide s, 必恰好有一個 0 < u < p, p divide s+un

b_s = (-1)^u  (mod p)


因此得證 b_s 必定 = 1 or -1 (mod p)

事實上若 -s/n (mod p) 是奇數那就是 -1, 反之是 1



反過來的情況 因為 b_s 很複雜 所以不會XD

所以姑且數學上證明了 p 是質數有你說的結果
p 不是質數的話我也不知道(攤手)


================================================================

For s = 0 to n-1,

       p          p-k     u
b_s = sum C(p, k) sum (-1)  C(p-1+s+un, p-1)
      k=0         u=0


反過來的情況 check all n 是不實際的

至少要能只 check finite many n


(Thm) For any natural number c, q
      C(m+cq, n) = C(m, n)  (mod q)

(pf) it is enough to prove the case q = p^a and 0 <= m < q

     Given finite field F_q, q = p^a
     we have (x+y)^p = x^p + y^p, thus (x+y)^q = x^q + y^q
     C(m+cq, n) the coeff. of x^n of (1+x)^(m+cq)
     while (1+x)^(m+q) = (1+x)^m (1+x^q)^c
     so coeff. of x^n is C(m, n), thus C(m+cq, n) = C(m, n)  (mod q)


加上 n = 1 的情況超廢

因此只要考慮 1 < n < p 的情況就好了


Want: if for all 1 < n < p, b_s = 1 or -1  (mod p), then p is prime

or if p is not prime, then for some n and s, b_s != 1 or -1  (mod p)


Ques: w not prime, which C(w, k) is not a multiple of w?
      w not prime, which C(v, w-1) is not a multiple of w?


(Thm) q = p^a, p prime, then C(qm, qn) = C(m, n)  (mod q)

(pf) In F_q, q = p^a, (1+x)^(qm) = (1+x^q)^m
     thus C(qm, qn) = coeff. of x^(qn)
                    = coeff. of (x^q)^n = C(m, n)  (mod q)

to be continued


--

嗯嗯ow o

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.167.47.216
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1541827284.A.C4A.html
※ 編輯: Desperato (118.167.47.216), 11/10/2018 14:59:22
→ kilva       : 感謝回應，但不要忘了還有p除n不可以餘1這個限制。
→ kilva       : 這是已確定違反上述iff的偽質數可能出現的地方。
→ Desperato   : 其實我看不出來p除n為什麼不能餘1 ow o
→ Desperato   : 如果是說 inverse 的話 那感覺很煩XD
※ 編輯: Desperato (118.167.47.216), 11/10/2018 15:48:33
※ 編輯: Desperato (118.167.47.216), 11/10/2018 16:00:05