New Factorization Algorithm (not complete)
Joe Fitzsimons
Here's an idea for a factorization algorithm that I have been having some
sucesses with. The basis for the idea is matrix determinant theory. Its
fairly simple : det(AB) = det(A) * det(B), where A and B are matrices. My
idea is as follows: take a large number n, which you are trying to factor,
and create a 2x2 matrix N, such that det(N) = n.
Now there exists two matrices P and Q such that P*Q=N. Now the advantages of
using determinant theory here is that there are and infinite number of
matrices, P and Q, which satisfy the above equation. It is important to note
here that det(P)=p and det(Q)=q, such that p and q are integers, and p*q=n.
This is the general case.
It is possible to put constraints on one of the matrices, as long as it can
be translated into the required form by elementary row opperations. If it
requires column operations, it will not work. Here is a constraint I propose
(although I am sure there are better ones out there) ;
let P = [ a b ]
[ c d ]
let Q = [ x y ]
[ 1 1 ]
where a,b,c,d,x,y are unknown
N = [ e f ]
[ g h ]
such that e*h - f*g = n, their actual values don't matter.
Now from above, multiplying P by Q yields:
PQ = [ (a*x + b) (a*y + b) ] = [ e f ] = N
[ (c*x + d) (c*y + d) ] [ g h ]
This implies that e - f = a*(x - y)
g - h = c*(x - y)
But det(Q) = q = x*1 - y*1 = x - y
Therefore gcd(e-f, g-h) is a factor of n.
I would be greatful for any feedback on this idea.
Thanks,
Joe
Mok-Kong Shen
Joe Fitzsimons wrote:
>
> Here's an idea for a factorization algorithm that I have been having some
> sucesses with. The basis for the idea is matrix determinant theory. .......
[snip]
Are you aware that RSA offers monetary rewards for
factorization of certain integers?
M. K. Shen
Joe Fitzsimons
> Are you aware that RSA offers monetary rewards for
> factorization of certain integers?
>
> M. K. Shen
Yes, I am, But thamks for pointing it out. I haven't really tested this on
anything more that about 10^30. I am not entirely surely on the best way to
estimate the effectiveness of this method on larger moduli, since it depends
on whether column opperations must be performed, which is dependent on the
choice of the matrix N.
Joe.
Joe Fitzsimons
the matrices, P and Q, I am more than open to suggestions.
Thanks,
Joe
Mok-Kong Shen
Joe Fitzsimons wrote:
>
> Yes, I am, But thamks for pointing it out. I haven't really tested this on
> anything more that about 10^30. I am not entirely surely on the best way to
> estimate the effectiveness of this method on larger moduli, since it depends
> on whether column opperations must be performed, which is dependent on the
> choice of the matrix N.
Frankly, I haven't studied the details of your post,
but I have the impression that what you do is very
possibly a more complicated (hence inefficient) way of
doing things than working directly with the integers.
M. K. Shen
Joe Fitzsimons
As regards being inefficient, it illiminates the need
Joe Fitzsimons
iterations as it yields results immediately. Sorry about the last post, it
was sent prematurely. Anyway, by using matrices there are an unlimited
number of factors, since for each factor of n, there exist an unlimited
number of matrices with it as their determinant.
Regards,
Joe
m...@my-deja.com
> By the way, for anyone that has an idea for a better constraint to place on
> the matrices, P and Q, I am more than open to suggestions.
Hm. Maybe if you set:
P = [ p 0 ] Q = [q 0]
[ 0 1 ] [0 1]
where n=p*q?
Wait a minute ...
Bryan Olson
> Okay,
> Here's an idea for a factorization algorithm that I have been having
> some sucesses with.
Could you describe the "successes". Given that I'm impressed at
quantum computers factoring 15, I don't expect the method to advance
the state of art just yet. What I'd like to know is how you
factored using your method without clearly solving the same
factorization problem directly in the integers.
> The basis for the idea is matrix determinant theory. Its
> fairly simple : det(AB) = det(A) * det(B), where A and B are matrices. My
> idea is as follows: take a large number n, which you are trying to
factor,
> and create a 2x2 matrix N, such that det(N) = n.
> Now there exists two matrices P and Q such that P*Q=N. Now the
advantages of
> using determinant theory here is that there are and infinite number of
> matrices, P and Q, which satisfy the above equation. It is important
to note
> here that det(P)=p and det(Q)=q, such that p and q are integers, and
p*q=n.
> This is the general case.
Count me as skeptical. I do not see that as a promising avenue. The
infinite number matrices P and Q holds in the reals, but not the
integers. If n is odd, factoring it into 2 and n/2 isn't useful.
--Bryan
Joe Fitzsimons
>
> P = [ p 0 ] Q = [q 0]
> [ 0 1 ] [0 1]
>
> where n=p*q?
>
That doesn't work, since it yields:
[ pq 1 ] = [ n 0 ]
[ 1 0 ] [ 0 1 ]
which is equivalent to trial division.
Joe Fitzsimons
about 50 % of the time it yields a factor for numbers made of two large
primes under 100000.
I haven't tried it for enough larger numbers to know how well this holds for
them.
> What I'd like to know is how you
> factored using your method without clearly solving the same
> factorization problem directly in the integers.
It is directly in integers, just another way of looking at the problem.
> Count me as skeptical. I do not see that as a promising avenue. The
> infinite number matrices P and Q holds in the reals, but not the
> integers. If n is odd, factoring it into 2 and n/2 isn't useful.
There are actually an infinite number of matrices with only integer entries,
which have a specific determinant. For example, if you want a matrix with
integer entries, which has a determinant of x, any matrix of the form:
[ y (y-x) ]
[ 1 1 ]
has the determinant x and only integer entries (as long as y is an integer)
. Since there are an infinite number of integers, y can have an infinite
number of infinite number of integer values. Hence there are an infinite
number of matrices with integer entries which satisfy the equation.
I should point out that my example above is only one of many forms which
yield the matrices with determinant x and only integer entries.
Joe
Phil Carmody
The objects that you work with have very little bearing on the
efficiency of the algorithm, it's what you _do_ with them (i.e the
algorithm) that defines the efficiency. The 'objects' in the Number
Field Sieve are complicated beasts, however, it's a fast algorithm.
The P+1 algorithm can be implemented using matrices, and the the
Hypergeometric factoring algorithm is typically presented as using
matrices, for example, so there's nothing intrinsically wrong about
matrices.
(I'm deliberately ignoring the linear algebra matrix stage of the sieve
techniques, as that use of matrices is in a different context.)
I've not had a chance to look at the actual algorithm yet, but I'm
always interested in such developments even if they are isomorphic to
current techniques, simply hiding under a different guise!
Phil
Scott Contini
I'm not sure I fully understand your algorithm, but I am very skeptical.
Are you trying to say that you just need to find equations of the form
e*h - f*g = n and then gcd(e-f,g-h) may be a proper factor? If this
is indeed your argument, then I think you will have very little success
for large integers. Hmmmmm: essentially you are writing n as the
difference of that area of two rectangles. It is well known that writing
it as the difference of two squares allows you to factor, but that is
much harder to do!
Scott
Jakob Jonsson
news:mWh58.31406$8s4.1...@news.indigo.ie...
> let P = [ a b ]
> [ c d ]
>
> let Q = [ x y ]
> [ 1 1 ]
>
> where a,b,c,d,x,y are unknown
>
> N = [ e f ]
> [ g h ]
>
> such that e*h - f*g = n, their actual values don't matter.
>
> Now from above, multiplying P by Q yields:
>
> PQ = [ (a*x + b) (a*y + b) ] = [ e f ] = N
> [ (c*x + d) (c*y + d) ] [ g h ]
>
> This implies that e - f = a*(x - y)
> g - h = c*(x - y)
>
> But det(Q) = q = x*1 - y*1 = x - y
>
> Therefore gcd(e-f, g-h) is a factor of n.
Since you choose e,f,g,h in advance in an arbitrary manner, it is unlikely that
gcd(e-f,g-h) is a prime factor of n. It is more likely that the gcd equals 1 or
n, in which case we don't gain anything.
Jakob
Joe Fitzsimons
that
> gcd(e-f,g-h) is a prime factor of n. It is more likely that the gcd equals
1 or
> n, in which case we don't gain anything.
Choosing e*h < 2*n avoids the possibility that gcd(e-f,g-h) = n.
Duran Castore
> Here's an idea for a factorization algorithm that I have been having
some
> sucesses with. The basis for the idea is matrix determinant theory.
Its
> fairly simple : det(AB) = det(A) * det(B), where A and B are matrices.
My
> idea is as follows: take a large number n, which you are trying to
factor,
> and create a 2x2 matrix N, such that det(N) = n.
> Now there exists two matrices P and Q such that P*Q=N. Now the
advantages of
> using determinant theory here is that there are and infinite number of
> matrices, P and Q, which satisfy the above equation. It is important
to note
> here that det(P)=p and det(Q)=q, such that p and q are integers, and
p*q=n.
> This is the general case.
How do you choose a suitable matrix N? There are infinite matrices, with
determinant N, to choose from.
The remainder of the algorithm is okay; rephrasing you, choose matrices
P and Q, within constraints, to find easily det(P)=p and det(Q)=q, given
a minimum of known entries on P and Q. Construct a system N = P * Q,
solve for some unknowns within P or Q, and, using usual algebra, find p
or q.
What if the system does not have a solution, or infinite solutions?
---------------------------------------
Duran Castore (duran_...@yahoo.com)
Bryan Olson
[Bryan Olson wrote:]
>>Could you describe the "successes".
>>
>
> about 50 % of the time it yields a factor for numbers made of two large
> primes under 100000.
>
> I haven't tried it for enough larger numbers to know how well this
holds for
> them.
>
>
>>What I'd like to know is how you
>>factored using your method without clearly solving the same
>>factorization problem directly in the integers.
>>
>
> It is directly in integers, just another way of looking at the problem.
The way I read your method, you've defined a reduction. You've
reduced the integer factorization problem (IF) to the problem of
finding matrices of integer that multiply in the way you described.
What I'm asking about is whether your solution to the matrix problem
actually ends up reducing back to the same IF problem, or to some
problem instance to which we already know how to reduce IF.
>>Count me as skeptical. I do not see that as a promising avenue. The
>>infinite number matrices P and Q holds in the reals, but not the
>>integers. If n is odd, factoring it into 2 and n/2 isn't useful.
>>
>
> There are actually an infinite number of matrices with only integer
entries,
> which have a specific determinant. For example, if you want a matrix with
> integer entries, which has a determinant of x, any matrix of the form:
>
> [ y (y-x) ]
> [ 1 1 ]
O.K. I see what you mean. (But count me as still skeptical.)
--Bryan
Vedat Hallac
> How do you choose a suitable matrix N? There are infinite matrices, with
> determinant N, to choose from.
>
> The remainder of the algorithm is okay; rephrasing you, choose matrices
> P and Q, within constraints, to find easily det(P)=p and det(Q)=q, given
> a minimum of known entries on P and Q. Construct a system N = P * Q,
> solve for some unknowns within P or Q, and, using usual algebra, find p
> or q.
>
> What if the system does not have a solution, or infinite solutions?
possible matrices N until there is a solution, and the solution can
only occur if you find values e and f such that (e-f) is a multiple of
q. Th eother possibility (infinite number of solutions) probably is
never the case, because then you would simply pick one, and use it to
factorize. There is one more possibility, and that is when a is a
multiple of p, which makes e-f a multiple of N, instead of q. However
in one of the later posts, an additional constraint was presented
which eliminates this case.
There might still be something in the form
e*h - g*f = n
which steers the search towards e and f values which make e-f a
multiple of q, but I failed to see how or why it would. Perhaps it is
something to check, because one of the claims was that the method
succeeded 50% of the time.
One thing I tried starting from the idea of writing N as a matrix was
to apply Cayley-Hamilton theorem (if memory serves me right. The one
that says every matrix satisfies its own char. equation). The char.
equation of N is always:
lam^2 - (e+h)*lam + n = 0 (lam is the eigenvalue, lambda)
therefore,
N^2 - (e+h)*N + n*I = 00 (I is the identity matrix, and 00 is the zero
matrix)
Just get two N matrices (N1 and N2), and write
N1^2 - (e1+h1)*N1 + n*I = 00
N2^2 - (e2+h2)*N2 + n*I = 00
subtract them
(N1^2 - N2^2) -(e1+h1)*N1 +(e2+h2)*N2 == 0
if N1*N2 == N2*N1 (I'll come back to this),
(N1 - N2)*(N1 + N2 - (e1 + h1)*I) == ((e2 + h2) - (e1 + h1)*N2
take the determinants
det(N1-N2)*det(N1 + N2 - (e1 + h1)*I) == ((e2 + h2) - (e1 +
h1)*det(N1)
thus, there is a good chance that one of the determinants will be a
multiple of q or p. Of course I couldn't validate the claim, because
one requirements I set above, namely, N1*N2 = N2*N1 requires N1, N2 to
have the form:
[a b]
[b a]
Looks familiar? You need to find a^2 - b^2 = n to use all the crap
I've shown above. Call it a cosmic joke, call it stupidity.
The funny thing is, when I forgot about the commutativity requirement,
and used small (pencil/paper testable) numbers 91 and 403, the first
two matrices I have chosen for each set yielded one of the factors. I
was so happy until I noticed that the numbers did not add up. ;-) So I
have solved the factorization problem for about ten minutes. Probably
more than anyone can claim. Hehe.
I'm posting the wrong steps, in the hope that someone can find a way
to wriggle around the commutativity requirement. The moral of the
story? If Joe did not post his findings, I would not think of trying
matrices in the first place, so there is still value in the incorrect
results.
Cheers,
VedaT
Vedat Hallac
> Joe Fitzsimons wrote:
>
> [Bryan Olson wrote:]
> >>Could you describe the "successes".
> >>
> >>
> > about 50 % of the time it yields a factor for numbers made of two
> > large primes under 100000.
> >
> > I haven't tried it for enough larger numbers to know how well this
> holds for
> > them.
> >
> >
> >>What I'd like to know is how you
> >>factored using your method without clearly solving the same
> >>factorization problem directly in the integers.
> >>
> >>
> > It is directly in integers, just another way of looking at the
> > problem.
>
> The way I read your method, you've defined a reduction. You've reduced
> the integer factorization problem (IF) to the problem of finding
> matrices of integer that multiply in the way you described.
>
> What I'm asking about is whether your solution to the matrix problem
> actually ends up reducing back to the same IF problem, or to some
> problem instance to which we already know how to reduce IF.
You are probably right. I managed to prove (well only a sketch of the
proof, really) the following:
if the eigenvalues of the matrix
[e f] = N
[g h]
are the factors of n, where n=det(N), then e-f=p, where p is one of the
prime factors. I have a strong hunch that it is possible to prove the
opposite. That is, e-f=p iff lam1*lam2=n, lam1, lam2 are integers, and
are the eigenvalues of N. Since the eigenvalues can take on non-integer
values (including complex ones) even when all for entries, e, f, g, and h
are integers, if my hunch is correct, you can use this method to
factorize only if you hit a matrix whose eigenvalues are the factors in
the first place. So what are the chances of this happening? If you have
no further restrictions on e, f, g, and h, I would say lower than
factoring the integer by chance (now, the set of all trial matrices
include the ones with complex eigenvalues as well). You can get rid of
the complex eigenvalued matrices by the simple constraint
(e+h)^2 > 4n
because the characteristic equation is
lam^2 - (e+h)*lam + n = 0
However, forcing the previous equation to have integer roots with the
choice of e and f would prove to be a very hard problem (equivalent to
factoring n?).
The reverse of the argument might be a bit more involved. i.e. I might
need to prove that gcd(n,e-f)=p if lam1=p and lam2=q, but I don't think
I'll spend the time on it. Too hard for me. ;-)
One thing I am still looking at is the classification of all the matrices
with integer elements, and with eigenvalues equal to the factors of n.
The easiest way to generate all matrices with a particular eigenvalue is
to "rotate" the matrix with the factors of n in the diagonal using a unit
matrix U (det(U)=1) via U*N*(U^-1), but I can't see how this can be used
to generate matrices with integer entries. This line of thinking might lead
to more constraints on e, f, g, h which will allow you to choose a matrix
that would lead to a factorization, instead of trusting your luck. :-)
One final note about using matrices to factorize numbers: since all
matrices can be diagonalized, where the diagonal elements are the
eigenvalues, the most natural choice of the matrix dimension is the
number of factors of n. Too little, and some of the eigenvalues are
composites; too large, and some of the eigenvalues are 1.
Cheers,
VedaT
Joe Fitzsimons
important in this context, I do see where you are comming from. However, in
the 2x2 matrix equation P*Q = N, if all the entries in the matrices are
integers, then their determinants must also be integers:
det[ a b ] = (a*d)-(b*c)
[ c d ]
and since det(X)*det(Y) = det(X*Y), the determants of P and Q must be a pair
of factors of n = det(N).
Hope this clarifies my reasoning a little,
Joe
Joe Fitzsimons
a variation of the above method. Here is a cut down version if you want to
try it out.
For sufficiently large numbers x and y (x ~ 2*y), satisfying the equation
x - y = n, the number to be factored, there exist integers a,b,c and d,
which satisfy the following equations:
a*b = x
c*d = y
gcd((a+c),(b+d)) = p
such that k*p = N for some k.
Hence factoring x and y allows you to factor n. I should point out that this
does not always work, but it works a supprisingly well for small numbers.
Also not all a,b,c,d satisfy this equation, but there seems to be one
combination for each x and y choosen ( if they are sufficiently large). I
know now that this does not hold well for larger numbers, but maybe its
worth a look.
Joe