任意取两个不等质数p,q，记N=pq,构造Zn，并且证明Zn为群

设计思路

• 利用筛法，求出一定范围内的素数，并将这些素数存在一个list当中
• 从list中随机选出p,q,若p==q则重新选择
• 计算出N，并根据N，构造出Zn*
• 判断是否Zn*中每个元素都含有逆元
• 根据群的性质，判断Zn*是否为群

下面贴出代码

import random
import math
from random import choice

def getRandomPrime(Nmax):
    isPrime = [0]*(Nmax+1)
    primeList = []
    isPrime[2] = 1
    for i in range(3,Nmax,2):
        isPrime[i] = 1
    for i in range(3,int(math.sqrt((Nmax+1)))+1,2):
        if(isPrime[i] == 1):
            for j in range(i*i,Nmax+1,2*i):
                isPrime[j] = 0
    for i in range(2,Nmax+1):
        if (isPrime[i]==1):
            primeList.append(i)
    #使用全局变量，将while里面的取值，取出
    global a,b
    while True:
        p,q = (random.sample(primeList,2))
        if(p!=q):
            a,b = p,q
            break
    return a,b

def isCoprime(a,b):
    flag = 0
    if(b>a):
        a,b = b,a
    while(a%b):
        tmp = b
        b = a%b
        a = tmp
    if(b==1):
        flag = 1
    return flag

def getZnStar(Nmax):
    znStar = []
    p,q = getRandomPrime(Nmax)
    print("p is %d, q is %d"%(p,q))
    N = p*q
    print("N is %d"%N)
    for i in range(1,N):
        if(isCoprime(N,i)==1):
            znStar.append(i)
    print("Zn_star is " + str(znStar))
   # print (type(len(znStar)))
    return znStar,N,p,q

def isEveryInverse(znStar,N):
    count = 0
    size = len(znStar)
    for i in range(0,size):
        for j in range(0,size):
            if((znStar[i] * znStar[j]) % N == 1):
                count = count + 1
                break
    if(count==size):
        print("Every element has its inverse")
        return 1
    else:
        print("Not every element has its inverse")
        return 0

def isGroup(znStar,N):
    closure_flag = 0
    exchange_flag = 0
    unit_flag = 0
    size = len(znStar)
    a,b = random.sample(range(0,size),2)
    c = choice(range(0,size))
    for i in range(0,size):
        if((znStar[a] * znStar[b]) % N == znStar[i]):
            closure_flag = 1
            break
    #print(type(N))
    if ((((znStar[a]*znStar[b])%N)*znStar[c])%N == (((znStar[b]*znStar[c])%N)*znStar[a])%N):
            exchange_flag=1
    if(znStar[0] == 1):
            unit_flag = 1
    if(closure_flag == 1 and exchange_flag == 1 and unit_flag == 1 and isEveryInverse(znStar,N)==1):
            print ("znStar is a group")
    else:
            print ("znStar is not a group")

def Number(znStar,p,q):
    size = len(znStar)
    if (size == (p-1)*(q-1)):
        print ("The size of ZnStar is (p-1)*(q-1)")
    else:
        print("The size of ZnStar is (p-1)*(q-1)")

if __name__=="__main__":
    znStar,N,p,q = getZnStar(100)
    isGroup(znStar,N)
    Number(znStar,p,q)