Integer factorization with q < 2p

mgb · 2009-10-24, 10:15

I have made some interesting observations re. integer factorization with pq = n and q < 2p

Here is my paper

PDF

R. Gerbicz · 2009-10-24, 10:58

Quote:

Originally Posted by mgb

I have made some interesting observations re. integer factorization with pq = n and q < 2p

Here is my paper

PDF

If p is the larger factor of n then q<=p so q<2*p is also true. What is the largest number that you factored by your method?

retina · 2009-10-24, 11:31

Quote:

Originally Posted by mgb

Here is my paper

Link needs JS to work.

Quote:

Originally Posted by mgb

PDF

Link needs a login to work.

Any chance of a simple attachment? Why the complication of using Google Docs?

TimSorbet · 2009-10-24, 11:34

Quote:

Originally Posted by retina

Any chance of a simple attachment? Why the complication of using Google Docs?

Attached. (taken from downloading it from Google Docs)

mgb · 2009-10-24, 12:41

Quote:

Originally Posted by R. Gerbicz

If p is the larger factor of n then q<=p so q<2*p is also true. What is the largest number that you factored by your method?

I have p < q. I am only using java to do this at the moment and that is limited to MAX_long. I have directly calculated the t value for many integers (p + q)/2 - s = t and it is always small. As I say in my paper t = Tmax/3 if q = 1.5p and this is the hardest to target but the array can be constructed with a minimal number of elements to test the range (E - 2Tmax/3 - x) to (E - 2Tmax/3 + x) for some x to find -t

mgb · 2009-10-24, 12:49

Quote:

Originally Posted by retina

Link needs JS to work.Link needs a login to work.

Link needs login to work.

Any chance of a simple attachment? Why the complication of using Google Docs?

You should need no login...
Tried to attach but I get an 'invalid' message. See pdf in Mini-Geek's post (thanks M-G).

mgb · 2009-10-30, 18:52

Has anyone tested this system or have any comments on it?

CRGreathouse · 2009-10-30, 19:53

Quote:

Originally Posted by mgb

Has anyone tested this system or have any comments on it?

From a brief look, several statements are wrong but that seems to be from carelessness rather than fundamental flaws. For example, #1 and #3 on the first page are wrong. The calculation of T_max seems a little worse... it assumes a strong bound on p that isn't stated anywhere. The first two implicit assumptions give up essentially no power, but the third reduces the algorithm from a general semiprime factoring algorithm to a more limited one that can factor only (what seems to be) a subset of semiprimes with relative density 0.

I don't understand the algorithm proposed, though. Step 4 of Case (1) requires knowing t, which in turn requires knowing a nontrivial factor of n. Looping through all possible t (from 0 to t_MAX) would seem to require more time than trial division.

But assuming this is addressed (clearly the author is aware of the issue, else t_MAX would not have been mentioned) I think the algorithm is fast only on numbers for which Fermat's factorization method is faster (and Dixon's, etc., faster yet).

CRGreathouse · 2009-10-30, 20:27

Quote:

Originally Posted by CRGreathouse

can factor only (what seems to be) a subset of semiprimes with relative density 0.

Here's a quick Excel chart supporting my statement. If anyone knows whether this trend holds asymptotically, I'd be pleased to know.

(Obviously a fast method to factor numbers of this form would still be of consequence, especially sicne RSA numbers are of this form.)

mgb · 2009-10-31, 09:26

For those who find my paper overly complicated (which it is) I will outline the algorithm again.

It is simplicity itself-

1. Define A and E as descirbed in the paper.

2. Create the inverses $a^{-m}, \, a^{-2m}...\,a^{-cm} \, (mod \, n)$

3. Find k such that $a^{A + k} \, = a^{-im} \, (mod \, n)$

4. $\phi{(n)}/2 = A + k + im$ . Done!

It is simply a question of finding k such that-

A + k = $\phi{(n)}/2 \, - \, im$ . It is as simple as that!

Tmax is $(\sqrt{n}/\sqrt{2} \, + \, \sqrt{n}*\sqrt{2})/2 \, - \, s$

I have rewritten my paper http://docs.google.com/fileview?id=0...NzlmODAw&hl=en

______________________________________________________

When I wrote this paper I was thinking in terms of RSA semiprimes and

factoring them and they are odd so #1 which says-

"s - p < q - s"

is correct except for the most trivial cases where t = 0 or p = q.

The example I give is-

p = 2003

q = 3001

s = 2451

2451 - 2003 = 448

3001 - 2451 = 550 < 448

#2 says-

"h is even so h = 2t" This is also true for the limitations set on p and q:

q is odd and so is p

If s is odd

(odd - odd) - (odd - odd) = even - even = even

If s is even

(odd - even) - (even - odd) = odd - odd = even

______________________________________________________

The strong bound on p is that p >= $\sqrt{n}/\sqrt{2}$

The strong point of this system is that it identifies a small

Tmax and t is often very small indeed. This means that n can

be factored in at most t trials which is better by far than

simple trial and error for integers up to $\sqrt{n}$ .

I have factored many 10 digit integers in less than 10 trials.

This is something worth investigating further.

Fermat's factorization method would look at - to take the example above -

$y^2$ = (3001 - 2003)/2 = 499

My system looks at

t = (2003 + 3001)/2 - 2451 = 51, almost 10 times smaller. Even though we don't know what

t is we will find it quickly by trial.

So, in this instance, trial and error alone would factor 2003 x 3001 = 6011003 in 51 trials.

_________________________________________________________

As for the algorithm itself. I only put in Case 1. and Case 2. to illustrate

the structure of the system. The best way I have yet found is the last algorithm

described in the paper.

This algorithm calculates $m^{-1}, \, 2m^{-1}, \, 3m^{-1}...cm^{-1} \, (mod \, n)$

A, which is E - cm, will be such that

$\phi{(n)}/2 \, - \, (i + 1)m \, <= \, A \, <= \, \phi{(n)}/2 \, - \, im$

Since we have the inverse of $a^{im}$ (which is $a^{\phi{(n)}/2 \, - im}$ )

stored in the array it is simply a case of finding

$a^{A + k}$ = $a^{-im} \, (mod \, n)$ now

$\phi{(n)}/2$ = A + k + im. It is then a simple matter to factor n since we know

$\phi{(n)}$ I have rewritten my paper anyhow and I left out the illustrative algorithms

and concentrated on the last algorithm only. I hope it is clearer now.

The algorithm described in the paper is only one bare bones idea for finding a solution to the

Discrete Logarithm Problem for a very small exponent. I'm sure there are many other and even better ways.

Would anyone like to knock up a program to verify all this?

Thanks, mgb.

R.D. Silverman · 2009-10-31, 12:27

Quote:

Originally Posted by mgb

For those who find my paper overly complicated (which it is) I will outline the algorithm again.

It is simplicity itself-

1. Define A and E as descirbed in the paper.

2. Create the inverses $a^{-m}, \, a^{-2m}...\,a^{-cm} \, (mod \, n)$

What is a? What is m? What is the BOUND on m as a function of N?

Quote:

3. Find k such that $a^{A + k} \, = a^{-im} \, (mod \, n)$

Find k HOW? Direct seach? Do you have a bound on its value??

Quote:

4. $\phi{(n)}/2 = A + k + im$ . Done!

It is simply a question of finding k such that-

A + k = $\phi{(n)}/2 \, - \, im$ . It is as simple as that!

This method is hopeless for anything reasonably sized. It is purely
exponential.

Quote:

The example I give is-

p = 2003

q = 3001

s = 2451

Stop giving tiny, trivial examples. Try something reasonable; say
p,q, are 50 digits.

Quote:

The strong bound on p is that p >= $\sqrt{n}/\sqrt{2}$

The strong point of this system is that it identifies a small

Tmax

HOW small as a function of N??? In fact, Tmax is a purely exponential
function of (pq). Hint. Let N = pq, p = (1+epsilon)q. q ~ N^1/2.
Now look at (p-q).

Quote:

and t is often very small indeed.

Try it for 50 digit primes. Anything is small for 5 digit primes. Suppose
that p,q, ~ 10^50 and (p-q) ~ 10^48 (i.e. their first two digits match;
this is close). How big is t????

Can anyone imagine doing 10^48 modular exponentiations???????

Quote:

This means that n can

be factored in at most t trials which is better by far than

simple trial and error for integers up to $\sqrt{n}$ .

What is "simple trial and error"? And your claim is hollow since you have
not bounded t. Nor have you said anything about the cost of each
individual trial.

Quote:

I have factored many 10 digit integers in less than 10 trials.

BFD. The cost of each "trial" is LARGE (a full modular exponentiation
and inverse). The cost of an iteration is Fermat's method is trivial: a
single subtraction.

This is an exponential algorithm, you have tried it on only trivially
sized problems, and you have failed to analyze its complexity.

It is HOPELESS.

Quote:

This is something worth investigating further.

Not in my opinion.

Quote:

Fermat's factorization method would look at - to take the example above -

$y^2$ = (3001 - 2003)/2 = 499

My system looks at

t = (2003 + 3001)/2 - 2451 = 51, almost 10 times smaller. Even though we don't know what

Each Fermat iteration is a single subtraction. Look at the cost
of one of your iterations. And one can always find special instances that
work quickly for an algorithm such as this that depends on special
properties of the primes.

Quote:

Would anyone like to knock up a program to verify all this?

Don't anyone waste their time. The algorithm is hopeless for
anything reasonably sized. And slower than Fermat's method for anything
small.

2009-10-31, 09:26	#10
mgb "Michael" Aug 2006 Usually at home 2²×3×7 Posts	For those who find my paper overly complicated (which it is) I will outline the algorithm again. It is simplicity itself- 1. Define A and E as descirbed in the paper. 2. Create the inverses $a^{-m}, \, a^{-2m}...\,a^{-cm} \, (mod \, n)$ 3. Find k such that $a^{A + k} \, = a^{-im} \, (mod \, n)$ 4. $\phi{(n)}/2 = A + k + im$ . Done! It is simply a question of finding k such that- A + k = $\phi{(n)}/2 \, - \, im$ . It is as simple as that! Tmax is $(\sqrt{n}/\sqrt{2} \, + \, \sqrt{n}\sqrt{2})/2 \, - \, s$ I have rewritten my paper http://docs.google.com/fileview?id=0...NzlmODAw&hl=en ______________________________________________________ When I wrote this paper I was thinking in terms of RSA semiprimes and factoring them and they are odd so #1 which says- "s - p < q - s" is correct except for the most trivial cases where t = 0 or p = q. The example I give is- p = 2003 q = 3001 s = 2451 2451 - 2003 = 448 3001 - 2451 = 550 < 448 #2 says- "h is even so h = 2t" This is also true for the limitations set on p and q: q is odd and so is p If s is odd (odd - odd) - (odd - odd) = even - even = even If s is even (odd - even) - (even - odd) = odd - odd = even ______________________________________________________ The strong bound on p is that p >= $\sqrt{n}/\sqrt{2}$ The strong point of this system is that it identifies a small* Tmax and t is often very small indeed. This means that n can be factored in at most t trials which is better by far than simple trial and error for integers up to $\sqrt{n}$ . I have factored many 10 digit integers in less than 10 trials. This is something worth investigating further. Fermat's factorization method would look at - to take the example above - $y^2$ = (3001 - 2003)/2 = 499 My system looks at t = (2003 + 3001)/2 - 2451 = 51, almost 10 times smaller. Even though we don't know what t is we will find it quickly by trial. So, in this instance, trial and error alone would factor 2003 x 3001 = 6011003 in 51 trials. _________________________________________________________ As for the algorithm itself. I only put in Case 1. and Case 2. to illustrate the structure of the system. The best way I have yet found is the last algorithm described in the paper. This algorithm calculates $m^{-1}, \, 2m^{-1}, \, 3m^{-1}...cm^{-1} \, (mod \, n)$ A, which is E - cm, will be such that $\phi{(n)}/2 \, - \, (i + 1)m \, <= \, A \, <= \, \phi{(n)}/2 \, - \, im$ Since we have the inverse of $a^{im}$ (which is $a^{\phi{(n)}/2 \, - im}$ ) stored in the array it is simply a case of finding $a^{A + k}$ = $a^{-im} \, (mod \, n)$ now $\phi{(n)}/2$ = A + k + im. It is then a simple matter to factor n since we know $\phi{(n)}$ I have rewritten my paper anyhow and I left out the illustrative algorithms and concentrated on the last algorithm only. I hope it is clearer now. The algorithm described in the paper is only one bare bones idea for finding a solution to the Discrete Logarithm Problem for a very small exponent. I'm sure there are many other and even better ways. Would anyone like to knock up a program to verify all this? Thanks, mgb. Last fiddled with by mgb on 2009-10-31 at 09:33

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Utility of integer factorization.	jwaltos	Other Mathematical Topics	8	2015-05-22 12:20
Integer factorization?	bearnol2	Information & Answers	7	2010-12-09 02:50
CADO workshop on integer factorization	akruppa	Factoring	14	2008-09-18 23:52
Integer Factorization	mgb	Math	16	2007-12-17 10:43
Integer Factorization 2	mgb	Math	5	2007-07-23 12:55

2009-10-24, 10:15	#1
mgb "Michael" Aug 2006 Usually at home 2²·3·7 Posts	Integer factorization with q < 2p I have made some interesting observations re. integer factorization with pq = n and q < 2p Here is my paper PDF Last fiddled with by mgb on 2009-10-24 at 10:18

2009-10-30, 18:52	#7
mgb "Michael" Aug 2006 Usually at home 54₁₆ Posts	Has anyone tested this system or have any comments on it?