import?math
from?functools?import?reduce????#用于合并字符
from?os?import?urandom??????????#系統隨機的字符
import?binascii?????????#二進制和ASCII之間轉換

#===================================================
def?Mod_1（xn）:
????????‘‘‘取模負1的算法:計算x2=?x^-1?（mod?n）的值，
r?=?gcd（a?b）?=?ia?+?jb?x與n是互素數‘‘‘
????????x0?=?x??
????????y0?=?n
????????x1?=?0
????????y1?=?1
????????x2?=?1
????????y2?=?0
????????while?n?!=?0:
????????????????q?=?x?//?n
????????????????（x?n）?=?（n?x?%?n）
????????????????（x1?x2）?=?（（x2?-?（q?*?x1））?x1）
????????????????（y1?y2）?=?（（y2?-?（q?*?y1））?y1）
????????if?x2?????????????????x2?+=?y0?
????????if?y2?????????????????y2?+=?x0?
????????return?x2??????
#===================================================
def?Fast_Mod（apm）:
????????‘‘‘快速取模指數算法:計算?（a?^?p）?%?m?的值‘‘‘
????????apm=int（a）int（p）int（m）
????????if?（p?==?0）?:
????????????????return?1
????????r?=?a?%?m
????????k?=?1
????????while?（p?>?1）:
????????????????if?（（p?&?1）!=0）:
????????????????????????k?=?（k?*?r）?%?m
????????????????r?=?（r?*?r）?%?m
????????????????p?>>=?1
????????return?（r?*?k）?%?m
#===================================================
def?randint（n）:
????????‘‘‘random是偽隨機數，需要更高安全的隨機數產生，
所以使用os.urandom（）或者SystmeRandom模塊，
生成n字節的隨機數（8位/字節）返回16進制轉為10進制整數返回‘‘‘
????????randomdata?=?urandom（n）
????????return?int（binascii.hexlify（randomdata）16）????
#===================================================
def?primality_testing_1（n）:
????????‘‘‘測試一，小素數測試，用100以內的小素數檢測隨機數x，
可以很大概率排除不是素數#創建有25個素數的元組‘‘‘
????????Sushubiao=（2357111317192329313741
???????????????????434753596167717379838997）
????????for?y?in?Sushubiao:
????????????????if?n%y==0:
????????????????????????return?False
????????return?True
#===================================================
def?primality_testing_2（n?k）:
????????‘‘‘測試二用miller_rabin算法對n進行k次檢測‘‘‘
????????if?n?????????????????return?False
????????d?=?n?-?1
????????r?=?0
????????while?not?（d?&?1）:
????????????????r?+=?1
????????????????d?>>=?1
????????for?_?in?range（k）:
????????????????a?=?randint（120）????????