23
$\begingroup$

Given a Gaussian integer $G=a+ib$, with $gcd(a,b)=1$, a well-known strategy for factoring $G$ is to first compute its norm $N(G)=a^2+b^2$, factor the norm and finally recover the correct generator corresponding to each prime appearing in the factorization of the norm.

However, this approach neglects the fact that $G$ tells us a bit more than $N(G)$ since it gives a square root of $-1$ modulo $N(G)$ (in general, there is no efficient way to obtain this without factoring).

As a consequence, I am interested to know whether there is a dedicated algorithm for factoring large Gaussian integers that does not start by factoring its norm.

Since there was misunderstanding in the comments, here are some clarifications.

First, since $G=a+ib$ with $gcd(a,b)=1,$ $G$ cannot be divisible by an integer prime $p$. A direct consequence is that all prime factors of the norm of $G$ are congruent to $1$ modulo $4$ and $a/b$ is a square root of $-1$ modulo $N(G)$.

In other words, my question is: it is easier to factor the Gaussian integer $G$ than to factor the integer $N=N(G)$ without knowledge of $G$? An alternative formulation is: can we take advantage of the knowledge that $(a/b)^2\equiv -1 \pmod{N(G)}$ to factor $N(G)$ faster?

Note that I am not interested by the case where we have two elements $G$ and $G'$ with equal norms because then factoring is easy (assuming that we learn two square roots of $-1$ which are neither equal nor opposite).

Improve this question
$\endgroup$
8
  • $\begingroup$ What is the correct generator corresponding to a prime? $\endgroup$
    – Colin McLarty
    Commented Aug 22, 2013 at 19:22
  • $\begingroup$ This is not a very precise question. Of course there are algorithms that don't start by factoring the norm. You can do trial division straight on the Gaussian integers. As there are no algorithms that perform better than general ones if the prime factors are all $3$ modulo $4$, one suspects that there are no factoring algorithms on the Gaussian integers that are better than the corresponding ones for the integers. $\endgroup$
    – Felipe Voloch
    Commented Aug 22, 2013 at 19:23
  • $\begingroup$ @FelipeVoloch The is precisely my question. Typically, if $N=pq$ with $p$ and $q$ large and congruent to $3$ modulo $4$, does it help to be given in addition a square root of $-1$ modulo $N$ (which using continued fraction gives $a+ib$ of norm $N$) ? $\endgroup$
    – minar
    Commented Aug 22, 2013 at 19:33
  • $\begingroup$ There is no square root of $-1$ modulo a product of primes congruent to $3$ modulo $4$. $\endgroup$
    – Felipe Voloch
    Commented Aug 22, 2013 at 19:39
  • $\begingroup$ @ColinMcLarty For simplicity, consider again $N=pq$ with $p$ and $q$ congruent to $3$ modulo $4$. Assume that $G=a+ib$ and $N(G)=N$. If $p$ factors as $p=(a_p+ib_p)(a_p-ib_p)$ you know that either $a_p+ib_p$ or $a_p-ib_p$ divides $G$. To test which one, multiply by the other. If you tried the right one, the result is divisible by $p$. $\endgroup$
    – minar
    Commented Aug 22, 2013 at 19:39

1 Answer 1

Reset to default
1
$\begingroup$

If you are given the prime factorization of a Gaussian integer $G$, then taking the norms of the prime factors immediately gives you the prime(-power) factorization of $N(G)$, so factoring $G$ cannot be any faster than factoring $N(G)$.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ This does not answer the question. You prove that factoring $G$ cannot be faster than factoring $N(G)$ GIVEN a square root of $-1$ modulo $N(G)$. (If I only give you $N(G)$, there is no known way to find $G$ -- except by factoring first.) $\endgroup$
    – minar
    Commented Aug 23, 2013 at 8:00
  • 2
    $\begingroup$ O.K., this is a slightly different question. The title of your post says "Factoring Gaussian integers" rather than "Factoring norms of Gaussian integers"; it starts off by saying, "Given a Gaussian integer G" and then, prior to your later edit, ends by asking for an algorithm for factoring Gaussian integers. You can see how I got the impression that you were trying to factor a given Gaussian integer. Perhaps the title and post should be rewritten to make this clear. $\endgroup$
    – Timothy Chow
    Commented Aug 23, 2013 at 15:30
  • $\begingroup$ Done. Hope it is clear. $\endgroup$
    – minar
    Commented Aug 23, 2013 at 17:18
  • $\begingroup$ Good edits, but I think you missed one: the first time you say "my question is..." still needs to be reworded. $\endgroup$
    – Timothy Chow
    Commented Aug 24, 2013 at 1:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .