代码实现¶
快速幂¶
Python
def square_and_multiply(a, e, N):
a = a % N # a mod N for the first time.
temp = 1 # Define a
while e > 0:
if (e & 1):
temp = temp * a % N
a = a * a % N
e >>= 1
return temp
a = 26430018304661698227244889550916468317489455778956328592921983469699792309163665193972706206594036869415691968221117606771494540098970766552365207210568611105852640630040412543297842462434526788081852074542946114404279053789976397875435006094029065093695673255562607050336148424707698012085470002233698228862346738763599120210887024055251199687451392437357330469313875769415203278005429487989371958004062135384988676187092753933346466785135069682592239769739616884935612245424974736666329142491909330198993521032748920319427468193197363789859738402941190883470502934385251934875320122360082927644910373611459923294476
e = 14409405982160132058252555071975393865919464165649477935316970889691161917952938338402420626169849869240199817340818785857661040902521177902522865655959315955027296333658575625679171649648237486715107874038848080146760431808160047758267886816563159460881275453304962088598750789947602763231536498803689415008248542306983990585872732303067442760485939483530499206750926623632218337793608305495353477797937055213103722548287089239675029998455237837122665431788486963392282333218897305536581935858534831705616909506614608137265328584496490209976683510539438184418619421230489065033982087166936851293061923363455338233631
N = 64543139452648583804777033627501791038942806480746416798824757337964931888296539408775325373896296201833019433336591701850604192958009038518829207716785069084776737389127085606861435151087914978789508354621086437098048489783165288663090667930959738070532371062440986402482696167926970371372070378265809277766155735077364001364843786628965534680520817227913435893489039438222319565950285009689464886596531381136997433211960842826747978689934063604682788246549928760755145469051762866022916315234333425333466441336354964665001026523519003032764174124744508998760069425321286184310908109489080474275209430911312055696378
print(square_and_multiply(a, e, N))
EEA¶
Python
def Exgcd(a : int, b : int):
if b == 0:
return a, 1, 0
d, x, y = Exgcd(b, a % b)
return d, y, x - (a // b) * y
a = 16680223846514478258525934578333599539857711346377301265204970111653892397676043794016150507259410995658188057040712085903607220122413595420007489488405731334280061988395608779010713411287131295428179813333359977034173092335579409810742439731878889187445253126904842513990354679981309972227336575079548411574454057133261948502170654953266704862335547650976687291747849350782598464591428327947848142796066981940848596121777048411057049426221708373813396661449882414643261467806037889440842533384968180620271785010057924587366185944297155319798570577070773474129972107871623872384643401132513116574551025071336188925411
b = 17855770299870519367242059681390424418096182155342041137488796879671107478743572864002383145021454681629377265833889126584206834902794697518171431222912791170447567040871094490052067407306798661337490592199170717969818501521767458577818192499457245780503918087449739410569911194050665897532807959319750868264903299819242751930003066441776015464336357481344549028678389909625259705769654505066857444104947192647667108605714724299029223354866042954807541588937325411249097096068333555976598698947608331063572282201472029299051787515328011628625087966449702534156436266476618723897816432054896528012909122280046552133534
d, x, y = Exgcd(a, b)
print(x)
print(y)
线性同余方程组¶
Python
def Exgcd(a : int, b : int): # d = gcd(a, b) = a * s + b * t
if b == 0:
return a, 1, 0
d, s, t = Exgcd(b, a % b)
return d, t, s - (a // b) * t
def verify(x : int, b_i : list, n_i : list):
for i in range(len(b_i)):
if x % n_i[i] != b_i[i]:
return False
return True
def CRT(b_i : list, n_i : list):
n = 1; ans = 0
for i in range(len(b_i)): # Calculate n
n = n * n_i[i]
for i in range(len(b_i)): # Calculate m_i
m = n // n_i[i]
d, b, t = Exgcd(m, n_i[i]) # b * m mod n_i[i] = 1
ans = (ans + b_i[i] * m * b % n) % n
print(verify((ans % n + n) % n, b_i, n_i))
return (ans % n + n) % n, n
b_i, n_i = [1, 4], [6, 15]
print(CRT(b_i, n_i))
生成元¶
Python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
def is_generator(g, n):
seen = set()
for k in range(1, n):
seen.add(pow(g, k, n))
return len(seen) == n - 1
def find_generators(n):
generators = []
for g in range(1, n):
if gcd(g, n) == 1: # g 与 n 互质
if is_generator(g, n):
generators.append(g)
return generators
print(find_generators(107))