Feeds:
Posts
Comments

Archive for October, 2007

Mersenne prime is a prime in the form of 2p-1 denoted as Mp, where p must be a prime.
It can be showed by quadratic residue that any divisor q of Mp satisfies that:
1) q = +/-1 (mod 8)
2) q = 1 (mod p)
A deterministic primality test called Lucas-Lehmer test is suitable for testing Mersenne prime.
Let L1=4, Ln+1=Ln*Ln-2, then Mp is prime if and only if Lp-1 = 0 (mod Mp).
Sufficiency Proof:
Let w=2+sqrt(3), v=2-sqrt(3), then Ln=w2n-1+v2n-1
Say R is a divisor of Mp such that R*R <= Mp.
Lp-1=w2p-2+v2p-2 = 0 (mod Mp)
==> w2p-1=-1 (mod Mp)
==> w2p-1=-1 (mod R) 
==> w2p=1 (mod R) 
So the number of elements in the group {a+b*sqrt(3) (mod R) | a+b*sqrt(3) is invertible}
is at least the order of w, 2p.
Then R*R-1 >= 2==> Mp >= 2p, a contradiction.
Necessity Proof:
Say Mp is prime.
It’s easy to show that 3 is not a quadratic residue of Mp by Legendre sign.
We just need prove w2p-1=-1 (mod Mp).
It can be proved that for any a+b*sqrt(3):
(a+b*sqrt(3))Mp = a-b*sqrt(3) (mod Mp)
(a+b*sqrt(3))2p = a*a- 3b*b (mod Mp)
Let z=(1+sqrt(3))/sqrt(2) (mod Mp).
z must exist, because 2 is a quadratic residue of Mp.
So z2 = w (mod Mp) ==> w2p-1 = z2p = (-2/2) = -1 (mod Mp).
Q.E.D.
The generalized  Lucas-Lehmer primality test is not necessary.
Namely, prime p may not pass the test for some specific parameters.
GIMPS is a organization searching Mersenne prime by collecting spare
CPU time of computers in the Internet.
Now, they are searching for one million digits Mersenne prime.

Advertisements

Read Full Post »

G(s,t) denotes a network with source s and destination t.
G'(f) denotes the residual network of G(s,t) with flow f.
Let S*(f) be the set of vertices reachable from s in G'(f).
Let T*(f) be the set of vertices from which t is reachable in G'(f).
Then for any maximum flows f1 and f2S*(f1) =S*(f2) and T*(f1) =T*(f2).
And for any minimum cut (S,T), S*(f) is a subset of S and T*(f) is a subset of T.
Stronger conjecture:
For any flows f1 and f2 with same flow volume, S*(f1) =S*(f2) and T*(f1) =T*(f2).


定义两个不同的最大网络流f1,f2的差网络G(f1-f2)
对原网络的边e,如果f1(e)>f2(e)就向G(f1-f2)中添加容量为f1(e)-f2(e)的方向跟e相同的边,称为正向边;
如果f1(e)<f2(e)就向G(f1-f2)中添加容量为f2(e)-f1(e)的方向跟e相反的边,称为反向边。
最后再去掉G(f1-f2)中入度出度均为0的点,同时保留s,t点。
A.容易看出G(f1-f2)中除s,t点外,其他点的出度入度同时大于0,
    因为容易证明网络G(f1-f2)仍然对所有的点出入平衡。
B.又G(f1-f2)中的所有边都是f2的剩余网络Nr(f2)中的边,
    所以stG(f1-f2)中无路径。
C.有G(f1-f2)中的所有边反向后都是f1的剩余网络Nr(f1)中的边,
    所以t到s在G(f1-f2)中无路径。
由A,B,C可知G(f1-f2)中一定有圈,而且这个圈可以通过在f2中增环流消掉,
增环流后G(f1-f2)的边数减少,即f1f2的差异变小。
一直对f2作增环流操作,可以把f2变成f1
下面证明增环流操作不会改变Nr(f2)s可达的点的集合。
设增环流的圈为V1–>V2–>V3…Vn—>V1.
可以发现,V1–>V2无论是正向边还是反向边,增环流后,V2–>V1一定出现在Nr(f2)中,
所以增环流后,Nr(f2)中存在圈Vn–>Vn-1–>…V1—>Vn,而Nr(f2)中其他边不变。
Nr(f2)中原来有圈V1–V2–V3…Vn—>V1,增环流后有圈Vn–>Vn-1–>…V1—>Vn
而这个圈之外的边不变,显然增环流不影响sV1,V2,..Vn的可达性,所以s到任意点的可达性都不变。

Read Full Post »