20091024, 10:15  #1 
"Michael"
Aug 2006
Usually at home
2^{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 Last fiddled with by mgb on 20091024 at 10:18 
20091024, 10:58  #2  
"Robert Gerbicz"
Oct 2005
Hungary
3^{2}×179 Posts 
Quote:


20091024, 11:31  #3  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
3·17·131 Posts 
Quote:
Quote:
Any chance of a simple attachment? Why the complication of using Google Docs? 

20091024, 11:34  #4 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10B7_{16} Posts 
Attached. (taken from downloading it from Google Docs)

20091024, 12:41  #5 
"Michael"
Aug 2006
Usually at home
2^{2}×3×7 Posts 
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
Last fiddled with by mgb on 20091024 at 13:12 
20091024, 12:49  #6  
"Michael"
Aug 2006
Usually at home
2^{2}·3·7 Posts 
Quote:
Tried to attach but I get an 'invalid' message. See pdf in MiniGeek's post (thanks MG). Last fiddled with by mgb on 20091024 at 13:38 

20091030, 18:52  #7 
"Michael"
Aug 2006
Usually at home
54_{16} Posts 
Has anyone tested this system or have any comments on it?

20091030, 19:53  #8 
Aug 2006
5,987 Posts 
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). Last fiddled with by CRGreathouse on 20091030 at 19:58 
20091030, 20:27  #9  
Aug 2006
5,987 Posts 
Quote:
(Obviously a fast method to factor numbers of this form would still be of consequence, especially sicne RSA numbers are of this form.) 

20091031, 09:26  #10 
"Michael"
Aug 2006
Usually at home
2^{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 3. Find k such that 4. . Done! It is simply a question of finding k such that A + k = . It is as simple as that! Tmax is 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 >= 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 . 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  = (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 A, which is E  cm, will be such that Since we have the inverse of (which is ) stored in the array it is simply a case of finding = now = A + k + im. It is then a simple matter to factor n since we know 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 20091031 at 09:33 
20091031, 12:27  #11  
"Bob Silverman"
Nov 2003
North of Boston
1110101010100_{2} Posts 
Quote:
What is a? What is m? What is the BOUND on m as a function of N? Quote:
Quote:
exponential. Quote:
p,q, are 50 digits. Quote:
function of (pq). Hint. Let N = pq, p = (1+epsilon)q. q ~ N^1/2. Now look at (pq). Quote:
that p,q, ~ 10^50 and (pq) ~ 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:
not bounded t. Nor have you said anything about the cost of each individual trial. Quote:
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:
Quote:
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:
anything reasonably sized. And slower than Fermat's method for anything small. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Utility of integer factorization.  jwaltos  Other Mathematical Topics  8  20150522 12:20 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
CADO workshop on integer factorization  akruppa  Factoring  14  20080918 23:52 
Integer Factorization  mgb  Math  16  20071217 10:43 
Integer Factorization 2  mgb  Math  5  20070723 12:55 