105 lines
2.7 KiB
Python
105 lines
2.7 KiB
Python
def is_prime(N):
|
|
"""
|
|
Тест Миллера-Рабина проверки числа на простоту.
|
|
"""
|
|
if N < 2:
|
|
return False
|
|
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
|
|
if N % p == 0: return N == p
|
|
d = N - 1
|
|
s = 0
|
|
while d % 2 == 0:
|
|
d >>= 1
|
|
s += 1
|
|
for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
|
|
if a >= N: continue
|
|
x = pow(a, d, N)
|
|
if x == 1 or x == N - 1: continue
|
|
for _ in range(s - 1):
|
|
x = pow(x, 2, N)
|
|
if x == N - 1: break
|
|
else: return False
|
|
return True
|
|
|
|
def primes(B):
|
|
"""
|
|
Возвращает список всех простых чисел до B.
|
|
"""
|
|
primes_list = []
|
|
is_prime = [True] * (B + 1)
|
|
is_prime[0] = is_prime[1] = False
|
|
for p in range(2, B + 1):
|
|
if is_prime[p]:
|
|
primes_list.append(p)
|
|
for i in range(p * p, B + 1, p):
|
|
is_prime[i] = False
|
|
return primes_list
|
|
|
|
def first_primes(n):
|
|
"""
|
|
Возвращает список первых n простых чисел.
|
|
"""
|
|
primes_list = []
|
|
candidate = 2
|
|
while len(primes_list) < n:
|
|
is_prime = True
|
|
for p in primes_list:
|
|
if p * p > candidate:
|
|
break
|
|
if candidate % p == 0:
|
|
is_prime = False
|
|
break
|
|
if is_prime:
|
|
primes_list.append(candidate)
|
|
candidate += 1
|
|
return primes_list
|
|
|
|
def is_smooth(n, base):
|
|
"""
|
|
Проверяет, является ли число гладким относительно factor_base
|
|
"""
|
|
if n == 0: return None
|
|
fact = [0] * len(base)
|
|
for i, p in enumerate(base):
|
|
if n == 1: break
|
|
while n % p == 0:
|
|
n //= p
|
|
fact[i] += 1
|
|
if n != 1:
|
|
return None
|
|
return fact
|
|
|
|
def legendre(a, p):
|
|
"""Вычисление символа Лежандра"""
|
|
if a % p == 0:
|
|
return 0
|
|
return pow(a, (p - 1) // 2, p)
|
|
|
|
def tonelli(n, p):
|
|
"""Реализует алгоритм Тонелли-Шенкса для нахождения квадратного корня числа"""
|
|
q = p - 1
|
|
s = 0
|
|
while q % 2 == 0:
|
|
q //= 2
|
|
s += 1
|
|
if s == 1:
|
|
return pow(n, (p + 1) // 4, p)
|
|
z = 2
|
|
while legendre(z, p) != p - 1:
|
|
z += 1
|
|
c = pow(z, q, p)
|
|
r = pow(n, (q + 1) // 2, p)
|
|
t = pow(n, q, p)
|
|
m = s
|
|
while t != 1:
|
|
t2 = t
|
|
i = 0
|
|
while t2 != 1 and i < m:
|
|
t2 = pow(t2, 2, p)
|
|
i += 1
|
|
b = pow(c, 2 ** (m - i - 1), p)
|
|
r = (r * b) % p
|
|
c = (b * b) % p
|
|
t = (t * c) % p
|
|
m = i
|
|
return r |