Может кто-нибудь объяснить мне эту часть алгоритма факторизации Диксона?
Я пытался реализовать метод факторизации Диксона в Python, и я немного запутался. Я знаю, что вам нужно дать некоторую оценку B и некоторое количество N и искать номера между sqrtN а также N чьи квадраты B-smoothэто означает, что все их факторы находятся во множестве простых чисел, меньших или равных B, Мой вопрос, учитывая N определенного размера, что определяет B так что алгоритм будет производить нетривиальные факторы N? Вот статья в википедии об алгоритме, и если он поможет, вот мой код для моей реализации:
def factor(N, B):
def isBsmooth(n, b):
factors = []
for i in b:
while n % i == 0:
n = int(n / i)
if not i in factors:
factors.append(i)
if n == 1 and factors == b:
return True
return False
factor1 = 1
while factor1 == 1 or factor1 == N:
Bsmooth = []
BsmoothMod = []
for i in range(int(N ** 0.5), N):
if len(Bsmooth) < 2 and isBsmooth(i ** 2 % N, B):
Bsmooth.append(i)
BsmoothMod.append(i ** 2 % N)
gcd1 = (Bsmooth[0] * Bsmooth[1]) % N
gcd2 = int((BsmoothMod[0] * BsmoothMod[1]) ** 0.5)
factor1 = gcd(gcd1 - gcd2, N)
factor2 = int(N / factor1)
return (factor1, factor2)
Может быть, кто-нибудь тоже может помочь немного почистить мой код? Это кажется очень неэффективным.
3 ответа
В этой статье обсуждается оптимальный размер для B: http://vmonaco.com/dixons-algorithm-and-the-quadratic-sieve/. Вкратце, оптимальным значением считается exp((logN loglogN)^(1/2)).
[Я написал это для другой цели, но вы можете найти это интересным. ]
Если x 2 y 2 (mod n) с x ± y, то примерно половина времени gcd (x - y, n) является фактором n. Эта конгруэнтность квадратов, наблюдаемая Морисом Крайтчиком в 1920-х годах, является основой для нескольких методов факторинга. Один из этих методов, благодаря Джону Диксону, важен в теории, потому что его субэкспоненциальное время выполнения может быть доказано, хотя он слишком медленный, чтобы быть полезным на практике.
Метод Диксона начинается с выбора границы b ≈ e √ (log n log log n) и определения факторной базы всех простых чисел, меньших b, которые являются квадратичными вычетами числа n (их символ Якоби равен 1).
function factorBase(n, b)
fb := [2]
for p in tail(primes(b))
if jacobi(n, p) == 1
append p to fb
return fb
Затем несколько раз выберите целое число r в диапазоне 1 < r < n, вычислите его квадрат по модулю n, и если квадрат является гладким по факторной базе, добавьте его в список отношений, останавливаясь, когда в факторе больше отношений, чем факторов база, плюс небольшой резерв для тех случаев, которые терпят неудачу. Идея состоит в том, чтобы идентифицировать набор отношений, используя линейную алгебру, где простые простые числа факторов объединяются в квадрат. Затем возьмите квадратный корень из произведения всех простых оснований фактора в отношениях, возьмите произведение связанного r и вычислите gcd для идентификации фактора.
struct rel(x, ys)
function dixon(n, fb, count)
r, rels := floor(sqrt(n)), []
while count > 0
fs := smooth((r * r) % n, fb)
if fs is not null
append rel(r, fs) to rels
count := count - 1
r := r + 1
return rels
Число n является гладким, если все его факторы находятся в факторной базе, которая определяется пробным делением; smooth Функция возвращает список факторов, который равен нулю, если n не полностью учитывает фактор-базу.
function smooth(n, fb)
fs := []
for f in fb
while n % f == 0
append f to fs
n := n / f
if n == 1 return fs
return []
Коэффициент определяется путем представления накопленных отношений в линейной алгебре конгруэнтности решателя квадратов.
Например, рассмотрим факторизацию 143. Выберите r = 17, поэтому r 2 ≡ 3 (mod 143). Затем выберите r = 19, поэтому r 2 ≡ 75 ≡ 3 · 5 2. Эти два отношения могут быть объединены как (17 · 19) 2 3 3 · 5 2 15 (мод 143), и два фактора: gcd(17·19 - 15, 143) = 11 и gcd(17·19) + 15, 143) = 13. Иногда это не получается; например, отношение 21 2 2 2 2 (mod 143) может быть объединено с отношением 19, но два полученных фактора, 1 и 143, тривиальны.
Спасибо за очень интересный вопрос!
В чистом Python я реализовал с нуля алгоритм факторизации Диксона в трех разных вариантах:
Используя простейшее сито. я создаю
u64массив со всеми числами в диапазоне [N; N * 2), которые означают стоимость. Этот массив содержит результат умножения простых чисел. Затем в процессе просеивания я перебираю все простые числа факторной базы и делаюarray[k] *= pв тех позициях, которые делятся на . Наконец, когда просеянный массив готов, я проверяю, что а) индекс массива является идеальным квадратом, б) иarray[k] == k - N. Второйb)условие означает, что все перемножаетсяpпростые числа дают конечное число, это верно только в том случае, если число делится только на простые числа с основанием, т. е. оно является B-гладким. Это самое простое и самое медленное из моих трех решений.Второе решение использует библиотеку SymPy для факторизации каждого файла . перебираю все что можно
zи делайsympy.factorint(z * z), это дает факторизацию . Если эта факторизация содержит только малые простые числа, т.е. из факторной базы, то я собираю такие z и z^2 для последующей обработки. Эта версия алгоритма тоже медленная, но намного быстрее первой.Третье решение использует вид просеивания, используемый в Quadratic Sieve . Этот процесс просеивания является самым быстрым из всех трех алгоритмов. В основном, что он делает, он находит все корни уравнения
x^2 = N (mod p)для всех простых чисел в факторной базе, так как у меня всего несколько простых чисел, поиск корня выполняется с помощью простого цикла по всем вариантам, для больших простых чисел можно использовать алгоритм поиска корня Шенкса Тонелли , который очень быстр.Только около 50% простых чисел вообще дают корневое решение, следовательно, только половина простых чисел фактически используется в квадратном решете. Корни такого уравнения можно использовать для получения множества решений одновременно, потому чтоroot + k * pтакже верное решение для всехk. Просеивание проводят черезarray[offset(root) :: p] += Log2(p). Здесь вместо умножения первого алгоритма я использовал добавление логарифма простого числа. Во-первых, складывать число немного быстрее, чем умножать. Во-вторых, что более важно, он поддерживает любой размер числа, например, даже 256-битный. При этом умножение возможно только до 64-битного числа, потому что Numpy не поддерживает 128- или 256-битные целые числа. После добавления логарифмов я проверяю, какие логарифмы равны логарифму исходного числа, эти числа являются окончательными просеянными числами.
После того, как все три вышеперечисленных алгоритма просеяли все, я выполняю этап линейной алгебры с помощью алгоритма исключения Гаусса . Этот этап предназначен для нахождения такой комбинации B-гладких чисел, которые после умножения их простых множителей дают итоговое число со всеми ЧЕТНЫМИ степенями простых чисел.
Назовем отношение тройкойz, z^2, prime factors of z^2. В основном все отношения сводятся к этапу исключения Гаусса, где встречаются четные комбинации.
Даже степени простых чисел дают нам равенствоa^2 = b^2 (mod N), откуда мы можем получить множитель, выполнивfactor = GCD(a + b, N), здесь НОД - наибольший общий делитель, найденный с помощью алгоритма Евклида . Этот НОД иногда дает тривиальные множители 1 и N, в этом случае следует проверять другие четные комбинации.
Чтобы быть на 100% уверенным в получении четных комбинаций, я выполняю этап просеивания, пока не найду немного больше, чем количество простых чисел количество отношений, на самом деле около 105% количества простых чисел. Эти дополнительные 5% соотношений гарантируют нам, что мы обязательно получим зависимые линейные уравнения на стадии Гаусса. Все эти зависимые уравнения образуют четные комбинации.
На самом деле нам нужно немного больше зависимых уравнений, не просто на 1 больше, чем количество простых чисел, а примерно на 5%-10% больше, только потому, что некоторые (50-60% из них, как я вижу экспериментально) зависимости дают только тривиальный множитель 1 или N. Следовательно, нужны дополнительные уравнения.
Посмотрите на вывод консоли в конце моего поста. Этот вывод консоли показывает все впечатления от моей программы. Там я запускаю параллельно (многопоточно) и 2-й (Sieve_B), и 3-й (Sieve_C) алгоритмы. 1-й (Sieve_A) не запускается моей программой, потому что он настолько медленный, что вы будете вечно ждать его завершения.
В самом конце исходного файла вы можете настроить переменнуюbits = 64к другому размеру, напримерbits = 96. Это количество битов в составном числе N. Это N создается как произведение всего двух случайных простых чисел одинакового размера. Такой состав, состоящий из двух равных по размеру простых чисел, обычно называют номером RSA.
Также найтиB = 1 << 10, это говорит о степени B-гладкости, в основном факторная база состоит из всех возможных простых чисел< B. Вы можете увеличить этот предел B, это даст более частые ответы просеянныхz^2следовательно, весь факторинг становится намного быстрее. Единственным ограничением огромного размера B является этап линейной алгебры (исключение по Гауссу), потому что с большей базой факторов вам нужно решать больше линейных уравнений большего размера. И мой Гаусс сделан не очень оптимальным образом, например, вместо того, чтобы держать биты какnp.uint8вы можете держать биты как плотныеnp.uint64, это увеличит скорость линейной алгебры в 8 раз.
Вы также можете найти переменнуюM = 1 << 23, который говорит, насколько велик размер просеиваемого массива, другими словами, это размер блока, который обрабатывается сразу. Большой блок немного быстрее, но не намного. Большие значения M не дадут большой разницы, потому что они только говорят, на какой размер задач разбит процесс просеивания, и не влияют на вычислительную мощность. Более того, больший M будет занимать больше памяти, поэтому вы не можете увеличивать его бесконечно, только до тех пор, пока у вас не будет достаточно памяти.
Помимо всех упомянутых выше алгоритмов, я также использовал тест на простоту Ферма , а также решето Эратосфена (для создания базы простых множителей).
Плюс также реализован собственный алгоритм фильтрации квадратных чисел. Для этого я беру составной модуль, близкий к Primorial , напримерmod = 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13. И внутри логического массива я отмечаю все модули чиселmodчто квадраты. Позже, когда нужно проверить любое число K, является ли оно квадратным или нет, я получаюflag_array[K % mod]и если это правда, то число «возможно» квадратное, а если оно ложно, то число «определенно» не квадратное. Таким образом, этот фильтр иногда дает ложные срабатывания, но никогда ложноотрицательные. Этот этап проверки фильтра отфильтровывает 95% неквадратов, оставшиеся 5% возможных квадратов можно перепроверить с помощью math.isqrt().
Пожалуйста, нажмите ниже наTry it online!ссылка, чтобы протестировать мою программу на онлайн-сервере ReplIt. Это создаст наилучшее впечатление, особенно если у вас нет Python или личного ноутбука. Мой код ниже можно просто запустить сразу после установки PIPpython -m pip numpy sympy.
import threading
def GenPrimes_SieveOfEratosthenes(end):
import numpy as np
composites = np.zeros((end,), dtype = np.uint8)
for p in range(2, len(composites)):
if composites[p]:
continue
if p * p >= end:
break
composites[p * p :: p] = 1
primes = []
for p in range(2, len(composites)):
if not composites[p]:
primes.append(p)
return np.array(primes, dtype = np.uint32)
def Print(*pargs, __state = (threading.RLock(),), **nargs):
with __state[0]:
print(*pargs, flush = True, **nargs)
def IsSquare(n, *, state = []):
if len(state) == 0:
import numpy as np
Print('Pre-computing squares filter...')
squares_filter = 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13
squares = np.zeros((squares_filter,), dtype = np.uint8)
squares[(np.arange(0, squares_filter, dtype = np.uint64) ** 2) % squares_filter] = 1
state.extend([squares_filter, squares])
if not state[1][n % state[0]]:
return False, None
import math
root = math.isqrt(n)
return root ** 2 == n, root
def FactorRef(x):
import sympy
return dict(sorted(sympy.factorint(x).items()))
def CheckZ(z, N, primes):
z2 = pow(z, 2, N)
factors = FactorRef(z2)
assert all(p <= primes[-1] for p in factors), (primes[-1], factors, N, z, z2)
return z
def SieveSimple(N, primes):
import time, math, numpy as np
Print('Simple Sieve of B-smooth z^2...')
sieve_block = 1 << 21
rep0_time = 0
for iiblock, iblock in enumerate(range(N, N * 2, sieve_block)):
if time.time() - rep0_time >= 30:
Print(f'Block {iiblock:>3} (2^{math.log2(max(iblock - N, 1)):>5.2f})')
rep0_time = time.time()
iblock_end = iblock + sieve_block
sieve_arr = np.ones((sieve_block,), dtype = np.uint64)
iblock_modN = iblock % N
for p in primes:
mp = 1
while True:
if mp * p >= sieve_block:
break
mp *= p
off = (mp - iblock_modN % mp) % mp
sieve_arr[off :: mp] *= p
for i in range(1 if iblock == N else 0, sieve_block):
num = iblock + i
z2 = num - N
if sieve_arr[i] < z2:
continue
assert sieve_arr[i] == z2, (sieve_arr[i], round(math.log2(sieve_arr[i]), 3), z2)
is_square, z = IsSquare(num)
if not is_square:
continue
#Print('z', z, 'z^2', z2)
yield CheckZ(z, N, primes)
def SieveFactor(N, primes):
import math
Print('Factor Sieve of B-smooth z^2...')
for iz, z in enumerate(range(math.isqrt(N - 1) + 1, math.isqrt(N * 2 - 1) + 1)):
z2 = z ** 2 - N
assert 0 <= z2 and z2 < N, (z, z2)
factors = FactorRef(z2)
if any(p > primes[-1] for p in factors):
continue
#Print('iz', iz, 'z', z, 'z^2', z2, 'z^2 factors', factors)
yield CheckZ(z, N, primes)
def BinarySearch(begin, end, Test):
while begin + 1 < end:
mid = (begin + end - 1) >> 1
if Test(mid):
end = mid + 1
else:
begin = mid + 1
assert begin + 1 == end and Test(begin), (begin, end, Test(begin))
return begin
def ModSqrt(n, p):
n %= p
def Ret(x):
if pow(x, 2, p) != n:
return []
nx = (p - x) % p
if x == nx:
return [x]
elif x <= nx:
return [x, nx]
else:
return [nx, x]
#if p % 4 == 3 and sympy.isprime(p):
# return Ret(pow(n, (p + 1) // 4, p))
for i in range(p):
if pow(i, 2, p) == n:
return Ret(i)
return []
def SieveQuadratic(N, primes):
import math, numpy as np
# https://en.wikipedia.org/wiki/Quadratic_sieve
# https://www.rieselprime.de/ziki/Multiple_polynomial_quadratic_sieve
M = 1 << 23
def Log2I(x):
return int(round(math.log2(max(1, x)) * (1 << 24)))
def Log2IF(li):
return li / (1 << 24)
Print('Quadratic Sieve of B-smooth z^2...')
plogs = {}
for p in primes:
plogs[int(p)] = Log2I(int(p))
qprimes = []
B = int(primes[-1]) + 1
for p in primes:
p = int(p)
res = []
mp = 1
while True:
if mp * p >= B:
break
mp *= p
roots = ModSqrt(N, mp)
if len(roots) == 0:
if mp == p:
break
continue
res.append((mp, tuple(roots)))
if len(res) > 0:
qprimes.append(res)
qprimes_lin = np.array([pinfo[0][0] for pinfo in qprimes], dtype = np.uint32)
yield qprimes_lin
Print('QSieve num primes', len(qprimes), f'({len(qprimes) * 100 / len(primes):.1f}%)')
x_begin0 = math.isqrt(N - 1) + 1
assert N <= x_begin0 ** 2
for iblock in range(1 << 30):
if (x_begin0 + (iblock + 1) * M) ** 2 - N >= N:
break
x_begin = x_begin0 + iblock * M
if iblock != 0:
Print('\n', end = '')
Print(f'Block {iblock} (2^{math.log2(max(1, x_begin ** 2 - N)):>6.2f})...')
a = np.zeros((M,), np.uint32)
for pinfo in qprimes:
p = pinfo[0][0]
plog = np.uint32(plogs[p])
for imp, (mp, roots) in enumerate(pinfo):
off_done = set()
for root in roots:
for off in range(mp):
if ((x_begin + off) ** 2 - N) % mp == 0 and off not in off_done:
break
else:
continue
a[off :: mp] += plog
off_done.add(off)
logs = np.log2(np.array((np.arange(M).astype(np.float64) + x_begin) ** 2 - N, dtype = np.float64))
logs2if = Log2IF(a.astype(np.float64))
logs_diff = np.abs(logs - logs2if)
for ix in range(M):
if logs_diff[ix] > 0.3:
continue
z = x_begin + ix
z2 = z * z - N
factors = FactorRef(z2)
assert all(p <= primes[-1] for p, c in factors.items())
#Print('iz', ix, 'z', z, 'z^2', z2, f'(2^{math.log2(max(1, z2)):>6.2f})', ', z^2 factors', factors)
yield CheckZ(z, N, primes)
def LinAlg(N, zs, primes):
import numpy as np
Print('Linear algebra...')
Print('Factoring...')
m = np.zeros((len(zs), len(primes) + len(zs)), dtype = np.uint8)
def SwapRows(i, j):
t = np.copy(m[i])
m[i][...] = m[j][...]
m[j][...] = t[...]
def MatToStr(m):
s = '\n'
for i in range(len(m)):
for j in range(len(m[i])):
s += str(m[i, j])
s += '\n'
return s[1:-1]
for iz, z in enumerate(zs):
z2 = z * z - N
fs = FactorRef(z2)
for p, c in fs.items():
i = np.searchsorted(primes, p, 'right') - 1
assert i >= 0 and i < len(primes) and primes[i] == p, (i, primes[i])
m[iz, i] = (int(m[iz, i]) + c) % 2
m[iz, len(primes) + iz] = 1
Print('Gaussian elemination...')
#Print(MatToStr(m)); Print()
one_col, one_rows = 0, 0
while True:
while True:
for i in range(one_rows, len(m)):
if m[i, one_col]:
break
else:
one_col += 1
if one_col >= len(primes):
break
continue
break
if one_col >= len(primes):
break
assert m[i, one_col]
assert np.all(m[i, :one_col] == 0)
for j in range(len(m)):
if i == j:
continue
if not m[j, one_col]:
continue
m[j][...] ^= m[i][...]
SwapRows(one_rows, i)
one_rows += 1
one_col += 1
assert np.all(m[one_rows:, :len(primes)] == 0)
zeros = m[one_rows:, len(primes):]
Print(f'Even combinations ({len(m) - one_rows}):')
Print(MatToStr(zeros))
return zeros
def ProcessResults(N, zs, la_zeros):
import math
Print('Computing final results...')
factors = []
for i in range(len(la_zeros)):
zero = la_zeros[i]
assert len(zero) == len(zs)
cz = []
for j in range(len(zero)):
if not zero[j]:
continue
z = zs[j]
z2 = z * z - N
cz.append((z, z2, FactorRef(z2)))
a = 1
for z, z2, fs in cz:
a = (a * z) % N
cnts = {}
for z, z2, fs in cz:
for p, c in fs.items():
cnts[p] = cnts.get(p, 0) + c
cnts = dict(sorted(cnts.items()))
b = 1
for p, c in cnts.items():
assert c % 2 == 0, (p, c, cnts)
b = (b * pow(p, c // 2, N)) % N
factor = math.gcd(a + b, N)
Print('a', str(a).rjust(len(str(N))), ' b', str(b).rjust(len(str(N))), ' factor', factor if factor != N else 'N')
if factor != 1 and factor != N:
factors.append(factor)
return factors
def SieveCollectResults(N, its):
import time, threading, queue, traceback, math
K = len(its)
qs = [queue.Queue() for i in range(K)]
last_dot, finish = False, False
def Get(it, ty, need, compul):
nonlocal last_dot, finish
try:
cnt = 0
for iz, z in enumerate(it):
if finish:
break
if iz < 4:
z2 = z * z - N
Print(('\n' if last_dot else '') + 'Sieve_' + ('C', 'B', 'A')[K - 1 - ty], ' iz', iz,
'z', z, 'z^2', z2, f'(2^{math.log2(max(1, z2)):>6.2f})', ', z^2 factors', FactorRef(z2))
last_dot = False
else:
Print(('.', 'b', 'a')[K - 1 - ty], end = '')
last_dot = True
qs[ty].put(z)
cnt += 1
if cnt >= need:
break
except:
Print(traceback.format_exc())
thr = []
for ty, (it, need, compul) in enumerate(its):
thr.append(threading.Thread(target = Get, args = (it, ty, need, compul), daemon = True))
thr[-1].start()
for ithr, t in enumerate(thr):
if its[ithr][2]:
t.join()
finish = True
if last_dot:
Print()
zs = [[] for i in range(K)]
for iq, q in enumerate(qs):
while not qs[iq].empty():
zs[iq].append(qs[iq].get())
return zs
def DixonFactor(N):
import time, math, numpy as np, sys
B = 1 << 10
primes = GenPrimes_SieveOfEratosthenes(B)
Print('Num primes', len(primes), 'last prime', primes[-1])
IsSquare(0)
it = SieveQuadratic(N, primes)
qprimes = next(it)
zs = SieveCollectResults(N, [
#(SieveSimple(N, primes), 3, False),
(SieveFactor(N, primes), 3, False),
(it, round(len(qprimes) * 1.06 + 0.5), True),
])[-1]
la_zeros = LinAlg(N, zs, qprimes)
fs = ProcessResults(N, zs, la_zeros)
if len(fs) > 0:
Print('Factored, factors', sorted(set(fs)))
else:
Print('Failed to factor! Try running program again...')
def IsPrime_Fermat(n, *, ntrials = 32):
import random
if n <= 16:
return n in (2, 3, 5, 7, 11, 13)
for i in range(ntrials):
if pow(random.randint(2, n - 2), n - 1, n) != 1:
return False
return True
def GenRandom(bits):
import random
return random.randrange(1 << (bits - 1), 1 << bits)
def RandPrime(bits):
while True:
n = GenRandom(bits) | 1
if IsPrime_Fermat(n):
return n
def Main():
import math
bits = 64
N = RandPrime(bits // 2) * RandPrime((bits + 1) // 2)
Print('N to factor', N, f'(2^{math.log2(N):>5.1f})')
DixonFactor(N)
if __name__ == '__main__':
Main()
Вывод консоли:
N to factor 10086068308526249063 (2^ 63.1)
Num primes 172 last prime 1021
Pre-computing squares filter...
Quadratic Sieve of B-smooth z^2...
Factor Sieve of B-smooth z^2...
QSieve num primes 78 (45.3%)
Block 0 (2^ 32.14)...
Sieve_C iz 0 z 3175858067 z^2 6153202727426 (2^ 42.48) , z^2 factors {2: 1, 29: 2, 67: 1, 191: 1, 487: 1, 587: 1}
Sieve_C iz 1 z 3175859246 z^2 13641877439453 (2^ 43.63) , z^2 factors {31: 1, 61: 1, 167: 1, 179: 1, 373: 1, 647: 1}
Sieve_C iz 2 z 3175863276 z^2 39239319203113 (2^ 45.16) , z^2 factors {31: 1, 109: 1, 163: 1, 277: 1, 311: 1, 827: 1}
Sieve_C iz 3 z 3175867115 z^2 63623612174162 (2^ 45.85) , z^2 factors {2: 1, 29: 1, 41: 1, 47: 1, 61: 1, 127: 1, 197: 1, 373: 1}
.........................................................................
Sieve_B iz 0 z 3175858067 z^2 6153202727426 (2^ 42.48) , z^2 factors {2: 1, 29: 2, 67: 1, 191: 1, 487: 1, 587: 1}
......
Linear algebra...
Factoring...
Gaussian elemination...
Even combinations (7):
01000000000000000000000000000000000000000000000000001100000000000000000000000000000
11010100000010000100100000010011100000000001001001001001011001000000110001010000000
11001011000101111100011111001011010011000111101000001001011000001111100101001110000
11010010010000110110101100110101000100001100010011100011101000100010011011001001000
00010110111010000010000010000111010001010010111001000011011011101110110001001100100
00000010111000110010100110001111010101001000011010110011101000110001101101100100010
10010001111111101100011110111110110100000110111011010001010001100000010100000100001
Computing final results...
a 9990591196683978238 b 9990591196683978238 factor 1
a 936902490212600845 b 3051457985176300292 factor 3960321451
a 1072293684177681642 b 8576178744296269655 factor 2546780213
a 1578121372922149955 b 1578121372922149955 factor 1
a 2036768191033218175 b 8049300117493030888 factor N
a 1489997751586754228 b 2231890938565281666 factor 3960321451
a 9673227070299809069 b 3412883990935144956 factor 3960321451
Factored, factors [2546780213, 3960321451]