Какой хороший метод для вычисления гауссовых целых чисел?

Question

У меня уже есть первичная факторизация (для целых чисел), но теперь я хочу реализовать ее для гауссовых целых чисел, но как мне это сделать? Спасибо!

Answer 1

Это оказалось немного многословно, но я надеюсь, что это полностью отвечает на ваш вопрос...

Гауссово целое число - это комплексное число вида

G = a+bi

где i² = -1, а a и b являются целыми числами.

Гауссовы целые числа образуют уникальную область факторизации. Некоторые из них действуют как единицы (например, 1, -1, i и -i), некоторые как простые числа (например, 1 + i), а остальные составные, которые могут быть разложены как произведение простых чисел и единиц, которые являются уникальными, помимо порядка факторов и наличия набора единиц, чье произведение равно 1.

Норма такого числа G определяется как целое число: норма (G) = a² + b².

Можно показать, что норма является мультипликативным свойством, то есть:

норма (I*J) = норма (I)* норма (J)

Поэтому, если вы хотите вычислить гауссово целое число G, вы можете воспользоваться тем фактом, что любое гауссово целое число I, которое делит G, должно удовлетворять свойству того, что норма (I) делит норму (G), и вы знаете, как найти факторы норма (G).

Простые числа гауссовых целых делятся на три категории:

1 +/- i, с нормой 2,

a +/- bi, с простой нормой a²+ b^2, соответствующей 1 mod 4,

a, где a - простое конгруэнтное с 3 mod 4, с нормой a²

---

Теперь, чтобы превратить это в алгоритм... если вы хотите разложить гауссово целое число G, вы можете найти его норму N, а затем разложить его на простые целые числа. Затем мы продвигаемся вниз по этому списку, снимая простые множители p из N, которые соответствуют простым гауссовым факторам q нашего исходного числа G.

Есть только три случая для рассмотрения, и два из них тривиальны.

Если p = 2, пусть q = (1+i). (Обратите внимание, что q = (1-i) будет работать одинаково хорошо, так как они отличаются только на единичный коэффициент.)

Если p = 3 mod 4, q = p. Но норма q равна p², поэтому мы можем вычеркнуть еще один фактор из списка оставшихся факторов нормы (G).

Случайс p = 1 mod 4- единственный, с которым сложно разобраться. Это эквивалентно проблеме выражения p как суммы двух квадратов: если p = a²+ b², тоa + bi и a-bi образуют сопряженную пару гауссовых простых чисел с нормой p, и один из них будет фактор, который мы ищем.

Но с небольшой теорией чисел оказывается, что это не слишком сложно. Рассмотрим целые числа мода p. Предположим, что мы можем найти такое целое числоk, что k²= -1 mod p. Тогдаk²+1 = 0 mod p, что эквивалентно тому, чтобы сказать, чтоp делит k²+1 на целые числа (а следовательно, и гауссовы целые числа). В гауссовых целых числахk²+1 делится на(k+i)(ki).р делит произведение, но не делит ни один из факторов. Следовательно, p имеет нетривиальную GCD с каждым из факторов (k + i) и (ki), и этот GCD или его сопряженное является фактором, который мы ищем!

Но как нам найти такое целое числоk? Пусть n будет некоторым целым числом от 2 доp-1 включительно. Рассчитайте n^{(p-1) / 2} mod p- это значение будет1 или-1. Если -1, то k = n^{(p-1) / 4}, в противном случае попробуйте другойn. Почти половина возможных значений n даст нам квадратный корень из -1 mod p, поэтому не нужно много догадок, чтобы найти значениеk, которое работает.

Чтобы найти гауссовы простые числа с нормойp, просто используйте алгоритм Евклида(слегка модифицированный для работы с гауссовыми целыми числами), чтобы вычислить GCD из (p, k + i). Это дает один пробный делитель. Если оно равномерно делит гауссово целое число, которое мы пытаемся вычислить (остаток = 0), мы закончили. В противном случае его сопряженный является желаемым фактором.

Алгоритм Евклида GCD для гауссовых целых чисел практически идентичен алгоритму нормальных целых чисел. Каждая итерация состоит из пробного деления с остатком. Если мы ищемgcd (a, b),

q = floor (a / b),остаток = a - q * b, и если остаток не равен нулю, мы возвращаем gcd(b, остаток).

В целых числах, если мы получим дробь как частное, мы округляем ее до нуля.
В гауссовых целых числах, если действительные или мнимые части отношения являются дробными, они округляются до ближайшего целого числа. Кроме того, алгоритмы идентичны.

Таким образом, алгоритм факторизации гауссова целого числаG выглядит примерно так:

Вычислитенорму (G), затем разложите норму (G) на простые числа p₁,p₂...p_n.

For each remaining factor p:
   if p=2, u = (1 + i).   
      strike p from the list of remaining primes.
   else if p mod 4 = 3, q = p, and strike 2 copies of p from the list of primes.
   else find k such that k^2 = -1 mod p, then u = gcd(p, k+i)
       if G/u has remainder 0, q = u
       else q = conjugate(u)
       strike p from the list of remaining primes.
   Add q to the list of Gaussian factors.
   Replace G with G/q.
endfor

В конце этой процедурыG является единицей с нормой 1. Но это не обязательно 1- это может быть-1, i или -i, и в этом случае добавьте G в список факторов, чтобы сделать знаки правильными, когда вы умножаете все факторы, чтобы увидеть, соответствует ли продукт Первоначальное значение G.

---

Вотрабочий пример: множитель G = 361 - 1767i над гауссовыми целыми числами.норма (G) = 3252610 = 2 * 5 * 17 * 19 * 19 * 53

Учитывая 2, мы пробуем q = (1+i) и находим G/q = -703 - 1064i с остатком 0.

G <= G/q = -703 - 1064i

Рассматривая 5, мы видим, что это совпадает с 1 модом 4. Нам нужно найти хороший к. Пытаясь n = 2, n^{(p-1) / 2} mod p = 2² mod p = 4. 4 соответствует -1 мод 5. Успех! k = 2¹ = 2. u = gcd (5, 2 + i), который получается 2 + i.G / u = -494 - 285i с остатком 0, поэтому находим q = 2 + i.

G <= G / q = -494 - 285i

Учитывая 17, он также соответствует 1 моду 4, поэтому нам нужно найти другойk мод 17. Попытка n = 2, 2⁸ = 1 мод 17, ничего хорошего. Попробуйте вместо этого n=3.3⁸ = 16 мод 17 = -1 мод 17. Успех! Так что к = 3⁴ = 13 мод 17.gcd (17, 13 + i) = u = 4-i, G / u = -99 -96i с остатком -2. Ничего хорошего, поэтому попробуйте сопрягать (и) = 4+ я. G / u = -133 - 38i с остатком 0. Еще один фактор!

G <= G / (4 + i) = -133 - 38i

Учитывая 19, это совпадает с 3 мод 4. Таким образом, наш следующий фактор - 19, и мы удаляем вторую копию 19 из списка.

G <= G / 19 = -7 - 2i

Учитывая 53, это соответствует 1 мод 4. Снова с процессом k... Попробуем n = 2, 2²⁶ = 52 mod 53 = -1 mod 53. Тогда k = 2¹³ mod 53 = 30.gcd (53,30 + i) = u = -7 - 2i. Это идентично G, так что конечный фактор G / (- 7-2i) = 1, и нет никаких факторов -1, i или -i, о которых нужно беспокоиться.

Мы нашли факторы (1 + i) (2 + i) (4 + i) (19 + 0i) (- 7-2i). И если вы умножите это (оставленное как упражнение для читателя...), и вот, продукт будет 361-1767i, с которого мы начали.

Разве теория чисел не сладка?

Answer 2

Используйте плавающую точку для вещественных и мнимых компонентов, если вам нужна полная целочисленная точность для одной ячейки, и определите gsub, gmul и специальный gdivr с округленными коэффициентами, а не по полу. Это потому, что метод факторизации Полларда нуждается в gcd с помощью алгоритма Евклида с немного измененным gmodulo:

gmodulo((x,y),(x',y'))=gsub((x,y),gmul((x',y'),gdivr((x,y),(x',y'))))

Поллард Ро

def poly((a,b),(x,y))=gmodulo(gsub(gmul((a,b),(a,b)),(1,0)),(x,y))

input (x,y),(a,b) % (x,y) is the Gaussian number to be factorized
(c,d)<-(a,b)
do 
   (a,b)=poly((a,b),(x,y))
   (c,d)=poly(poly((c,d),(x,y)),(x,y))
   (e,f)=ggcd((x,y),gsub((a,b),(c,d)))
   if (e,f)=(x,y) then return (x,y) % failure, try other (a,b)
until e^2+f^2>1
return (e,f)

Нормальным начальным значением является a=1, b=0.

Я использовал этот метод, запрограммированный в Forth на моем блоге http://forthmath.blogspot.se/

В целях безопасности используйте округленные значения во всех вычислениях, используя числа с плавающей запятой для целых чисел.