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

Ответ 1

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

A Гауссовское целое число является комплексным числом формы

G = a + bi

где я ²= -1, а a и b - целые числа.

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

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

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

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

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

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

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

a +/- bi, с основной нормой a ² + b ², конгруэнтной 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 ², поэтому мы можем ударить другой фактор p из списка остальных факторов нормы (G).

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

Но с небольшой теорией чисел это оказывается не слишком сложным. Рассмотрим целые числа mod p. Предположим, что мы можем найти целое число k такое что k ²= -1 mod p. Тогда k ² +1 = 0 mod p, что эквивалентно говоря, что p делит k ² +1 на целые числа (и, следовательно, также Гауссовские целые числа). В гауссовских целых числах k ² +1 факторы в (к + I) (к-я). p делит продукт, но не делит его фактор. Поэтому p имеет нетривиальный GCD с каждым из факторы (k + i) и (k-i), а 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 mod 4. Нам нужно найти хороший k. Попытка n = 2, n ^(p-1)/2 mod p= 2 ² mod p= 4. 4 согласуется с -1 mod 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 mod 4, поэтому нам нужно найти другое k mod 17. Попытка n = 2, 2 ⁸= 1 mod 17, ничего хорошего. Вместо этого попробуйте n = 3. 3 ⁸= 16 mod 17 = -1 mod 17. Успех! Итак, k = 3 ⁴= 13 mod 17. gcd (17, 13 + i) = u = 4-i, G/u = -99 -96i с остатком -2. Не хорошо, поэтому попробуйте сопряжение (u) = 4 + i. G/u = -133 - 38i с остатком 0. Другой фактор!

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

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

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

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

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

Не теория чисел сладка?

Ответ 2

Используйте плавающую точку для реальных и мнимых компонентов, если вы хотите получить полную одиночную целую точность, и определите gsub, gmul и специальное деление gdivr с закругленными коэффициентами, а не на пол. Это потому, что метод факторизации Полларда rho требует 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

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