Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email email@example.com
From: David Wagner (dawmozart.cs.berkeley.edu)
Date: Tue Nov 13 2001 - 09:11:00 CST
Matthew Dascombe wrote:
>* Factorising is an NP complete problem, [...]
No, it's not. (More precisely, it's not known to be, and considered
unlikely to be NP-complete, unless P = NP.)
By the way, your suggestion to write Z = W^2 - V^2 is known as
Fermat factoring (I think?). It is well-studied, and known to be
very slow for the sort of modulus found in cryptographic applications.
Modern algorithms are much faster.