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

.

Relevant Pages

  • Re: JSH: SF: Simpler factoring idea, but does it work?
    ... Here the square roots mean that expression can't just factor S, ... Including a rigorous proof that it was in fact 100% useless -- although some ... and you need S, and can use any square you like, so it's easiest just ... But does it work beyond toy examples like factoring 15? ...
    (sci.math)
  • Re: SF: Generalized SFTs
    ... I don't know if I can describe the feeling, ... He knows darned well too that his previous rounds of "proven correct" factoring algorithms were proved wrong by trying examples, ...
    (sci.math)
  • Integer factorization, basics
    ... The factoring problem concerns itself with finding non-trivial values ... square that adds to 4M to get a square, then you have a value of 'b' ... and you may choose to do so now, for whatever reasons are motivating ...
    (sci.math)
  • SF: Back to theory
    ... I see a lot of negative postings about my ideas, ... factoring is getting a lot of bashing, but hey, it's just an idea. ... Basically with the latest surrogate factoring I've been analyzing the ... algorithms, which I'll get to later, require that both j and T be ...
    (sci.math)
  • SF: Back to theory
    ... I see a lot of negative postings about my ideas, ... factoring is getting a lot of bashing, but hey, it's just an idea. ... Basically with the latest surrogate factoring I've been analyzing the ... algorithms, which I'll get to later, require that both j and T be ...
    (sci.crypt)