Статья Автор: Лебедев Дмитрий Алексеевич

Факторизация

# Вычисление функции Эйлера может быть основано на последней формуле или на следующем (аналогичном) способе:
from time import process_time as prt

import sympy as sp
#from sympy.ntheory import mod_inverse
#import sympy.ntheory as spt
def min_del(n):
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 3
    while d * d <= n :
        if n % d ==0 : return d
        d += 2
    return n

def eyler (n):
    ans1, ans2 = n, min(1, n -1)
    while n > 1 :
        d = min_del(n)
        ans1 //= d
        ans2 *= (d-1)
        while n % d == 0 :
            n //= d
    return ans1 * ans2
t0 = prt()
print(sp.prime(10**9), prt()-t0)
'''
#n = 1213536676883*1213876537547
#n = sp.Integer(1276812967623946997) * sp.Integer(2915342618762345659)
n = 111111152925239523917713913737319 * 111111346732889223371771179919737
e = sp.Integer(2**16+1)
phi = 2#eyler(n)
a = int(sp.totient(n))
t1 = prt()
d = pow(e, -1, a)
#d = 1213536676883
print((d*e)%a)
t2 = prt()
print (a, d, t1-t0, t2 - t1)

23399339
29399999
37337999
59393339
73939133
'''
print(pow(3,-1,20))

# Вычисление функции Эйлера может быть основано на последней формуле или на следующем (аналогичном) способе:
from time import process_time as prt

def min_del(n):
    if n % 2 == 0 : return 2
    if n < 9 : return n
    d = 3
    while d * d <= n :
        if n % d ==0 : return d
        d += 2
    return n

def eyler (n):
    ans1, ans2 = n, min(1, n -1)
    while n > 1 :
        d = min_del(n)
        ans1 //= d
        ans2 *= (d-1)
        while n % d == 0 :
            n //= d
    return ans1 * ans2
t0 = prt()
pp, qq = 13, 17
nn = pp*qq
phi = (pp-1)*(qq-1)
ee = 31
dd = pow(ee,-1, phi)
print(f'{nn=} {phi=} {ee=} {dd=} {ee*dd%phi=}')
Alf = {}
for i in range (nn) :
  Alf[i] = pow(i,ee,nn)
ss = input()
si =[ord(s) for s in ss]
tt = ''
ti =[]
for s in si :
  t = Alf[s]
  ti.append(t)
ri = []
for t in ti :
  i = pow(t, dd, nn)
  ri.append(i)
print(f'{si=}\n{ti=}\n{ri=}')
tt = ''
for t in ti : tt+=chr(t)
rr = ''
for r in ri : rr+=chr(r)
print(f'{ss=}\n{tt=}\n{rr=}')

Печать