Primes With Complex Factors

Lee Brotherston lee at nerds.org.uk
Sun May 11 18:19:01 BST 2008


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.


> 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 
> apparently uncrackable ciphers. Does anybody know more about this?

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

-- 
Lee Brotherston - <lee at nerds.org.uk>




More information about the Ukfreebsd mailing list