Re: Factoring large composite numbers

SplinterCell wrote:
> Let us take an integer which we wish to factor: x.
> Now let y = the smallest factor greater than x, where y - x is a square
> number.

I think you mean
  "let y = the smallest *square* greater than x, where y - x is a
square number."

> Let y - x = z
> Then, x = (sqrt(y) - sqrt(z))(sqrt(y) + sqrt(z))
>
> For example:
>
> Let x = 15
> Let y = 16
> y - x = 1 = z
> sqrt(z) = +1 or -1
> x = (4 - 1)(4 + 1)
> = 3 * 5
>
>
> Does this hold much promise or is this a dead end?
>

It is the first step for more advanced factoring algorithms, known as
"combination
of congruence algorithms". By itself, it is too inefficient. You
should try to
analyse this algorithm to understand why it is inefficient. Hint: if n
= p*q , then
the running time depends upon the difference of the primes.

To get to the next step (i.e. learning more efficient algorithms), you
will have to
learn modular arithmetic.

> Please be aware that I am only 15 years old, but I am extremely
> interested in cryptography and factorising large numbers.

For someone of your age, this book may be helpful:

Bressoud, D. M. Factorization and Primality Testing. New York:
Springer-Verlag, 1989.

Good luck.

Scott
Received on Mon May 1 01:54:01 2006