Simple integer factorization algorithm

J

JSH

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 =
T, where T is a composite to be factored.

With all positive integers:

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p

and 'a' is related to k mod p by

a^2 = (T)(k^2)^{-1} - 1 mod p

where p is what I call a helper prime.

Notice that because f_1 = ak mod p, ak must be greater than p, if f_1
is less than p, if k is coprime to T.

Note that a^{-1} mod p is the modular inverse mod p, as is (k^2)^{-1}
mod p.

To get the direct solution you pick p a prime where p>sqrt(T) and pick
for k a positive integer near p, coprime to p, if you accidentally
have a factor in common with T then you have factored it, which I
mention only because in programming the algorithm you need to check
for that case.

You then find if 'a' exists for your k and if it does you check if ak
is greater than p, if it is, then you solve for f_1, if not you
decrement k, and try again. There is a 50% chance of success for each
k that 'a' exists.

Example: Let T=119. Then p=11 is greater than sqrt(119), and trying
k=10 gives

a^2 = (119)(10^2)^{-1} - 1 mod 11 = 8 mod 11,

but 8 is not a quadratic residue modulo 11, so no 'a' exists for this
case. Trying now k=9, gives

a^2 = (119)(9^2)^{-1} - 1 mod 11 = 4 mod 11

so a=2 is a solution. And ak = 18, which is greater than 11, so

f_1 = ak = 18 mod 11 = 7 mod 11.

And you have a non-trivial factorization, as 7 is a factor of 119.

The algorithm you'll note is polynomial time and uses residues when
conventional wisdom was that you couldn't solve for integer factors
with residues, but the key here appears to be quadratic residues,
where you get an interlocking mechanism.


James Harris
 
A

Arne Vajhøj

JSH said:
The algorithm you'll note is polynomial time and uses residues when
conventional wisdom was that you couldn't solve for integer factors
with residues, but the key here appears to be quadratic residues,
where you get an interlocking mechanism.

Please post Java code here and math in an appropriate group.

Arne
 
J

Joshua Cranmer

JSH said:
I've found that you can solve directly for f_1 and f_2 when f_1*f_2 =
T, where T is a composite to be factored.

What does this have to do with Java?

While I must admit computer science and math are quite related, strictly
speaking, c.l.j.p is not a computer science-related newsgroup but a Java
programming-related one. Please post this to more related newsgroups,
such as sci.math and kill off this thread immediately as it is woefully
off-topic.

Please refrain from posting on this topic on the future unless you are
willing to provide Java code yourself. Even then, please restrict the
discussion to the Java code and any questions you have on it.


*WARNING*
I apologize to anyone who feels they may be insulted by the following
statement. I do not intend to imply anything about anyone except JSH.
*WARNING*

We have enough problems with trolls and spam as it is, thank you very much.
 
J

JSH

What does this have to do with Java?

I want it coded in java, and need some help with an implementation.

Any Java coders interested?

I'd like code to test the algorithm, please.

I simply prefer Java, that's all. If it's terribly off-topic to give
a coding opportunity here, I so apologize.


James Harris
 
J

Joshua Cranmer

JSH said:
I simply prefer Java, that's all. If it's terribly off-topic to give
a coding opportunity here, I so apologize.

Yes, it is off-topic here. This is not an advertising board.
 
J

JSH

Yes, it is off-topic here. This is not an advertising board.

Sorry guess I'm really kind of showing off.

Looks like I've discovered the world's first polynomial time integer
factorization algorithm!!!

Thought I'd toss it out there for other Java coders to appreciate and
admire.

Never been done people. History in the making.

Just wanted you all to be a part of it.


James Harris
 
O

Owen Jacobson

I wouldn't normally bother with this, but in the hopes of encouraging
Mr. Harris to go back to sci.math, where there are people who can help
him refine his ideas and to stop bothering programming newsgroups with
quarter-baked ideas...

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 =
T, where T is a composite to be factored.

With all positive integers:

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p

and 'a' is related to k mod p by

a^2 = (T)(k^2)^{-1} - 1 mod p

There is no supporting proof that both f_1 and f_2 are not equal to 1
or 0.
where p is what I call a helper prime.

Notice that because f_1 = ak mod p, ak must be greater than p, if f_1
is less than p, if k is coprime to T.

Note that a^{-1} mod p is the modular inverse mod p, as is (k^2)^{-1}
mod p.

To get the direct solution you pick p a prime where p>sqrt(T)

Your algorithm now depends on the complexity of selecting a prime
number within a certain range. To declare your algorithm "polynomial
time" you'll have to prove, or cite an existing proof, that this step
can be completed in polynomial time and that its contribution to the
algorithm's overall complexity is polynomial.
and pick
for k a positive integer near p, coprime to p

As p is a prime, all integers save p are coprime to p. Rigor matters.
In a formal description of an algorithm, this and the previous step
("pick a prime") would have to be more fully specified: algorithms do
not, generally, leave room for stereotypically human actions like
"picking a value", preferring rules for doing the picking
mechanically.
You then find if 'a' exists for your k

'a' demonstrably exists for all T, k, p tuples - but may not be an
integer. Rigor matters: if you mean "You then find if 'a' is an
integer for your k", say so.
and if it does you check if ak
is greater than p, if it is, then you solve for f_1, if not you
decrement k, and try again.  There is a 50% chance of success for each
k that 'a' exists.

Conjecture without supporting proof or citation.
Example: Let T=119. Then p=11 is greater than sqrt(119), and trying
k=10 gives

a^2 = (119)(10^2)^{-1} - 1 mod 11 = 8 mod 11,

but 8 is not a quadratic residue modulo 11, so no 'a' exists for this
case.  Trying now k=9, gives

a^2 = (119)(9^2)^{-1} - 1 mod 11 = 4 mod 11

so a=2 is a solution.  And ak = 18, which is greater than 11, so

f_1 = ak = 18 mod 11 = 7 mod 11.

And you have a non-trivial factorization, as 7 is a factor of 119.

The algorithm you'll note is polynomial time

Conjecture without supporting proof or citation.
and uses residues when
conventional wisdom was that you couldn't solve for integer factors
with residues, but the key here appears to be quadratic residues,
where you get an interlocking mechanism.

James Harris

If you are able to address the issues above, then I am perfectly happy
to entertain the proposal that I should write this up as a Java
program, or a program in any other language, in the new year. However,
I have two conditions: one, my rate is CAD 200 per hour or fraction
thereof, *payable in advance* for every hour you wish to spend on
this, and two, the deliverables, collectable at any point, are not
bound by any requirements related to factoring - only to being an
accurate implementation of your algorithm. If your algorithm is flawed
(and I strongly believe it is), I have no interest in "fixing" it for
you before being paid for my time.

In return, you will receive the complete program as-is at any point,
for review. The code will be written in a clear, concise style in
whatever language I select; within reason, I will use a language with
a stable community, so that the code will remain useful to you long
after you've decided my time is no longer worth your money.
(Personally, I think Haskell would be ideal for implementing the
algorithm as-written, as the code would strongly resemble the formulas
already used.)

Documentation for the implementation provided gratis, within reason.
Copyrights to the implementation and associated documentation will be
assigned to anyone you want; if the unthinkable happens and it
actually factors numbers like 1268651 correctly and in reasonable
time, you are not obliged to offer me anything. I will consider my
time paid for in full regardless.

I will not contribute one iota of theoretical work, nor privately
share with you any insights into factoring gleaned while transcribing
the algorithm.

Either of us may terminate the arrangement at any time. Programming
time paid for at that point will be completed, and the product handed
off as described.

I believe this is the best offer you are likely to get relating to
your search for a polynomial-time algorithm for factoring integers.
This is a good faith offer made in public, primarily to determine how
serious you are about your search.

F'up-to set to an appropriate newsgroup.

-o
 
J

JSH

I think it could be made on-topic by JSH presenting, rather than a vague
description of his idea and some claims, a specification of a program he
would like written in Java. Despite temptation, I accept that the
correctness and complexity of the algorithm are off-topic here, and will
not discuss them. Hint: I do read comp.theory, where the correctness and
complexity of a proposed algorithm would be on-topic.

I like that suggestion. I'll re-post to comp.theory and try to add in
more details.
To make this implementable, the pieces of his algorithm that he glosses
over would have to be filled in. For example, at the start he needs to
find a couple of numbers satisfying some constraints. Presumably, JSH
knows the polynomial time algorithms he intends to use to find those
numbers. The specification should include those algorithms, or
references to places where they are written up.

The whole algorithm should be described in either pseudo-code or links
to web pages containing pseudo-code.

Patricia

We'll see. It's a simple enough approach that it's not difficult to
do all that, but also may not be necessary. I'll fill in more details
at comp.theory and can even update things a bit based on discussions
on the math newsgroups.


James Harris
 
J

JSH

How much an hour are you offering?

If you survived the secret agents coming after you for the
implementation, I'd pay 0.

If you didn't, there would be a straight salary of 1 million dollars
(fantasy money in case your heirs did).

But then you could go collect some prizes or something and brag about
dodging sniper bullets.

I'm moving the discussion to comp.theory at Patricia Shanahan's
suggestion.

But, um, did it occur to anyone that as the coder of Class Viewer I
could probably code this thing myself?

So why wouldn't I?

I'm too freaking terrified that's why.

But I'm still not certain it works, so I'm talking it out, as the
worst thing would be to code it, have it factoring great and
immediately have a panic attack as I try to figure out how to survive
from that point on.


James Harris
 
J

JSH

Since I have run some tests on James' algorithm in the past, here is
part of my test code.  This does the timing of the factoring algorithm
over a range of bit sizes to get an impression of how the algorithm
scales with the size of the target number.

The discussion is moving. Besides, it's useless to put up code that
is NOT for the algorithm that is current.

And the current algorithm is also simpler.

I've posted to comp.theory and am ready to move on.

Please no more replies in this thread.

Your newsgroup cops might get restless.


James Harris
 
T

Tom Anderson

Sorry guess I'm really kind of showing off.

Looks like I've discovered the world's first polynomial time integer
factorization algorithm!!!

Thought I'd toss it out there for other Java coders to appreciate and
admire.

Never been done people. History in the making.

Just wanted you all to be a part of it.

Christ, you're not even trying to be convincing any more, are you?

tom
 
L

Lew

JSH said:
The discussion is moving. Besides, it's useless to put up code that
is NOT for the algorithm that is current.

And the current algorithm is also simpler.

I've posted to comp.theory and am ready to move on.

Please no more replies in this thread.

Sure, no problem.
Your newsgroup cops might get restless.

There are no such things here.
 
A

Andrew Thompson

...
Careful with line wrap on some of the longer print statements.

<http://pscode.org/twc/>
"The Text Width Checker (TWC) is a small
tool that allows easy checking of the number
of characters in lines of plain text. This
can be useful when drafting to text only
mediums such as usenet .."
 
J

JSH

I've found that you can solve directly for f_1 and f_2 when f_1*f_2 =
T, where T is a composite to be factored.

With all positive integers:

f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p

and 'a' is related to k mod p by

a^2 = (T)(k^2)^{-1} - 1 mod p

where p is what I call a helper prime.

Notice that because f_1 = ak mod p, ak must be greater than p, if f_1
is less than p, if k is coprime to T.

Note that a^{-1} mod p is the modular inverse mod p, as is (k^2)^{-1}
mod p.

To get the direct solution you pick p a prime where p>sqrt(T) and pick
for k a positive integer near p, coprime to p, <deleted>

It has been pointed out to me that the equation show that

nT - k^2 = f_1^2 mod p

so picking k directly is equivalent to guessing at the quadratic
residue mod p of one of the factors.

I should have noticed that before but didn't until a poster pointed it
out.


James Harris
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top