Matthew Dascombe wrote:

> * Factorising is an NP complete problem, and all NP problems are related

No. See Wagner's comment.

No known algorithm for factoring runs in time that is only polynomial in
the number of bits, and it is widely thought that no poly-time algorithm
exists, but this is unproven.
 
> * Factorisation of a product prime can be written as X * Y = Z, which can
> obviously be pretty huge
> * If Z has two factors, they must both be prime, and therefor the
> difference between them must be even. This means that there is always
> a number half way between them, W, by which each differ by half the
> difference between the prime factors, V. This means that X * Y = Z, is
> also X * Y = Z = (W+V) * (W-V).
> * This can be facotised to (W*W) - (V*V) ala First Grade Math.
> * This means there is only one point, where Z= (W*W)-(V*V), from which the
> facors can be found.

This method has been known since Fermat, in the 1600s.

If you know that the two primes are close in value, near root(Z), then V
is small and you can factor efficiently by just running through values
for V until you hit one that makes X*Y + V*V a perfect square.

The trouble is that in general, you don't know that and (unless you've
got some clever way to try the right V early in the process) there are
too many possible Vs for this to work well.

In the general case, I think this is about as efficient (root(N) tries)
as trial division. Each works well in a special case - Fermat if the two
factors are near root(N), trial divsion if one is small -- but neither
is good in general.

> * Because Z is a product prime, one of W(and w*w) or V(and v*v) must
> always be odd, and the other must always be even.
> * The difference between one square and the next is equal to
> 2(root(n)+.5), which is obviously always odd.
> * The difference between any two squares can therefor always be written as
> a seriers of consecutive odd numbers.

Actually, there's a theorem that n squared = the sum of the first n odd
numbers for any positive integer n. I think that one is old as well. The
proof is by induction. The difference of two successive squares, is just

        x^2 - (x-1)^2 = 2x - 1 = the x-th odd integer

> * Because one of W and V is always odd, the difference between w*w and v*v
> can always be represented as a series off an odd number of
> consecutive odd numbers,

Yes.

> and because (w*w)-(v*v)=x*y, this is also
> true for product primes - they can only be represented as an odd series
> of consecutive odd numbers.

I'm doubtful about the word "only" there.

> * I beleive this is closely related to the knapsack problem,

Why?

> and may result in a possibly faster prime-product searching algorythm.

Perhaps, but I cannot see how.

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]