Timeline for Difficulty of factoring a Gaussian integer (compared to factoring its norm)
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Aug 24, 2013 at 12:30 | history | suggested | James Cranch | CC BY-SA 3.0 |
improved the wording slightly
|
| Aug 24, 2013 at 12:08 | review | Suggested edits | |||
| S Aug 24, 2013 at 12:30 | |||||
| Aug 24, 2013 at 6:20 | history | edited | minar | CC BY-SA 3.0 |
added 1 characters in body
|
| Aug 23, 2013 at 17:11 | history | edited | minar | CC BY-SA 3.0 |
More emphasis on the difference between factoring $G$ and factoring its norm
|
| Aug 22, 2013 at 23:39 | answer | added | Timothy Chow | timeline score: 1 | |
| Aug 22, 2013 at 20:34 | history | edited | minar | CC BY-SA 3.0 |
added 221 characters in body
|
| Aug 22, 2013 at 20:07 | history | edited | minar | CC BY-SA 3.0 |
Added clarification after comments
|
| Aug 22, 2013 at 19:58 | review | Close votes | |||
| Aug 22, 2013 at 20:57 | |||||
| Aug 22, 2013 at 19:50 | comment | added | minar | @FelipeVoloch Same mix-up. Here is an example. $N=221$ then $G=14+5i$. Since $13$ divides $N$ and $13=(2+3i)(2-3i)$, one of $2\pm 3i$ divides $G$. Check that $G(2+3i)=13+52i$ is divisible by $13$. Conclude that $2-3i$ divides $G$ and $G=(2-3i)(1+4i)$. | |
| Aug 22, 2013 at 19:42 | comment | added | Felipe Voloch | What is $G$ (in your reply to Colin) if $N=21$? | |
| Aug 22, 2013 at 19:42 | comment | added | minar | @FelipeVoloch Sorry, I did not pay attention and copied the $3$ from your comment. I am interested by the case where both $p$ and $q$ factor in $\mathbf{Z}[i]$, i.e. $p$ and $q$ congruent to $1$ modulo $4$. | |
| Aug 22, 2013 at 19:39 | comment | added | minar | @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$. | |
| Aug 22, 2013 at 19:39 | comment | added | Felipe Voloch | There is no square root of $-1$ modulo a product of primes congruent to $3$ modulo $4$. | |
| Aug 22, 2013 at 19:33 | comment | added | minar | @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$) ? | |
| Aug 22, 2013 at 19:23 | comment | added | Felipe Voloch | 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. | |
| Aug 22, 2013 at 19:22 | comment | added | Colin McLarty | What is the correct generator corresponding to a prime? | |
| Aug 22, 2013 at 18:52 | history | asked | minar | CC BY-SA 3.0 |