Re: JSH: SF Algorithm
- From: hagman <google@xxxxxxxxxxxxx>
- Date: Thu, 13 Sep 2007 13:50:14 -0700
On 12 Sep., 00:30, Joshua Cranmer <Pidgeo...@xxxxxxxxx> wrote:
JSH wrote:
Oh well, enough bravado on my part as I'm not certain this will work
and waiting for Wednesday just seems silly. The Bulletin of the AMS
did reject. Why would they change their minds between now and then?
I try to keep an open mind, and I am willing to give you the benefit of
the doubt. My forays into sci.math only started very recently, so I do
not have the large amount of a priori expectations that other people
have. However, it is beginning to appear that I am giving you more than
you are giving yourself: after doing some heavy grandstanding recently,
implying that you were on the cusp of a factoring algorithm capable of
easily factoring the RSA challenges, you are now beginning to express
degrees of self-doubt:
The expert opinion is noted. Here is what my research says, which
presumably then will not work, but I do not know why it would not.
Given a target composite T, from theory using x^2 = y^2 mod T and k =
2x mod T, it can be proven that
(x+k)^2 = y^2 + 2k^2 mod T
must be true for any solution of a difference of squares.
Explicitly to solve you need solutions for
(x+k)^2 = y^2 + 2k^2 + nT.
Makes sense for me so far.
The algorithm picks x directly, choosing x = floor(sqrt(T)),
There is a tradition in many algorithms to explain why seemingly
arbitrary choices (magic numbers) are made. While my experience in
factoring algorithms is sparse, I believe that the basic idea for
Fermat's little theorem-based methods is to try to find good candidates
for x.
Furthermore, your basis is x^2 = y^2 mod T. If T is not a perfect
square, then x = y for this choice of x. That reduces your solution
equation to
x^2 + 2xk + k^2 = x^2 + 2k^2 + nT
2xk + k^2 = 2k^2 + nt
2kx = 2k + nT
so k = 2x,
further reducing to:
4x^2 = 4x + nT
4x(x + 1)/T = n
If T is a perfect square, then any operation beyond calculating x is
pointless since we have found a nontrivial factor.
> and then ranges for the n's from
n_max = floor(((x+k)^2 - 2k^2)/T)
and
n_min = floor((4(x+k-1) - 2k^2)/T)
But we have already determined n using algebra.
[ snip some more explanation of theory ]
It is so weirdly simple and I think the theory is correct, but I guess
I could be wrong.
Point 1: see top of post.
The underlying idea -- that factoring another number can help factor the
current number -- is suspect to me, for these reasons:
1. I do not see why S and T should have common factors.
There is no necessity for common factors, but they might be otherwise
related.
Making use of a (full or partial) factorization of T-1 and/or T+1
is a well-known method to help factor T (or at least prove T prime
or composite). Some methods even do use substantially bigger numbers
like
S:=T^2+1, T^2+T+1, T^2-T+1.
So the *idea* behind surrogate factoring is not totally wrong.
However, the methods I mentioned are useful only if
- T is of some special form (like 2^n+1) or
- partial factorization (e.g. casting out all primes <10^6) are
helpful enough
The simplicity condition does not hold for general numbers, esp. not
for
RSA numbers and JSHs method does not seem to produce good results
from
partial factorizations.
Therefore you are of course right with...
2. From what I understand, S is larger, and thus generally harder to
factor, than T. It seems that the program would spiral out of control
until it happens to trip over a factor.
That said, your application appears to trip up by making some
assumptions and then discarding the reasoning behind some of the
assumptions.
Correct me if I am wrong, but the point of the factoring algorithm
should be to find the suitable x's for an (x+y)(x-y) factorization; to
make that feasible x must be greater than sqrt(T).
I am not confident that I can work that problem out so what I said
earlier was bravado on my part.
Once again, see the top of my post.
.
- References:
- JSH: SF Algorithm
- From: JSH
- Re: JSH: SF Algorithm
- From: Joshua Cranmer
- JSH: SF Algorithm
- Prev by Date: Re: Region of convergence
- Next by Date: TOMMY1729 STRIKES AGAIN !!! what ? g( g(x) ) = f(x) is too easy for you ???
- Previous by thread: Re: JSH: SF Algorithm
- Next by thread: Re: JSH: SF Algorithm
- Index(es):
Relevant Pages
|
