# Primes With Complex Factors

Frank Shute frank at shute.org.uk
Sun May 11 20:12:07 BST 2008

```On Sun, May 11, 2008 at 06:19:01PM +0100, Lee Brotherston wrote:
>
> On Sun, May 11, 2008 at 01:53:34PM +0100, Frank Mitchell wrote:
>
> > When Gauss discovered Complex Numbers he found he could use them
> > to factorise Primes.
>
>
> I'm no mathematical genius but I thought that by definition primes
> cannot be factored, other than by one and themselves.
>
>
> > For instance 2 can be factorised as (1+i)*(1-i).
>
> Again it's been a while since I've done maths, but that doesn't seem
> to add up to me:
>
> (1+i)*(1-i) = 2
> 1-i+i-i^2 = 2
> 1+i^2 = 2
> i^2 = 1
> i = sqrt(1)
>
> If i is the squareroot of 1, it's not a whole number and therefore not
> a factor.

(1+i)(1-i)=2

expanding LHS:

1 + i - i - (i)^2 = 2

simplifying LHS:

1 - (i)^2 = 2

since (i)^2 = -1:

1 - (-1) = 2

so

2 = 2

as originally postulated.

I'd like to see some higher primes than 2 factored with complex
numbers. Two's a bit of a special case (only even prime) and small.

>
>
> > Recently this topic seems to have attracted further research, and it seems to
> > me this could be connected with Cryptography and its use of enormous Primes.
> > Apparently the People's Republic of China are getting expert at cracking
>
> Cryptography relies on factoring a huge semiprime, this means a large
> number that can only be factored into two primes.
>
> If there are governments making large advances in cracking
> ciphers I would suspect one of three things are taking place:
>
> - New hardware has been sourced to just throw processing power at the
>   problem.  I seem to recall that the hardware in some HDTVs, and
>   PS3's can be harnessed for some pretty impressive cracking times due
>   to the graphics chips, this means that hardware can be aquired at
>   a reasonable price to create a cracking farm.
>
> - Holes have been discovered in specific ciphers (or implimentations
>   of ciphers) which enable the shortcutting of the cracking process.
>
> - Memory to processing tradeoff techniques (along the lines of Rainbow
>   tables) could be used if suitably funded to generate the tables in
>   the first place.
>
>
> I could of course be completely wrong, as it's a boiling hot sunday
> afternoon, I'm tired and I've not attempted maths for quite some time
> :)
>
>
> Cheers
>
>   Lee

Regards,

--

Frank

Contact info: http://www.shute.org.uk/misc/contact.html

```