Re: Factoring large composite numbers

"SplinterCell" <suren.srikanthan@xxxxxxxxx> writes:

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.
Let y - x = z
Then, x = (sqrt(y) - sqrt(z))(sqrt(y) + sqrt(z))

You mean y is the smallest square larger than x such that...
a) HOw do you find y such that y-x is a square? -- There are very very very
many squares larger than x and most of them are not of the form such that
y-x is a square as well.

b) Your observation forms the basis of the method of a poster here called Stevens who
keeps posting that he has solved the factoring problem. So far he has not
managed to factor any large numbers, despite claiming to have
revolutionised the subject.
Ie, the observation is a very old one. Unfortunately noone has managed to
find a way to use it to make factoring any easier. ( Well, if you happen to
choose your number so that it is one less than some square, then of course
this method says it is very weak.)


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?

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


The subject is centuries old. Ie, the easy methods have been tried. It is
suspected that no polynomial time algorithm exists (ie it is NP-P) but no
proof of that exists (Not least because no proof that NP-P is non-null
exists)

.

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)
  • 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)
  • Re: Integer factorization, basics
    ... > The factoring problem concerns itself with finding non-trivial values ... > So the congruence of squares method works by having the square root ... > Being large primes, they are rare. ...
    (sci.math)
  • Surrogate factoring, objective look
    ... I have found a factorization method which I claim is new and important. ... Congruence of square relies on a simple idea to factor numbers using ... What I did was concentrate on two quadratics instead of one, ... That is how you can see that what I call surrogate factoring is a new ...
    (sci.crypt)
  • Re: Factoring large composite numbers
    ... Now let y = the smallest factor greater than x, where y - x is a square ... It is the first step for more advanced factoring algorithms, ... By itself, it is too inefficient. ...
    (sci.crypt)