20120411, 22:37  #1 
Apr 2012
5 Posts 
An equivalent problem for factorization of large numbers
First of all, hello to everyone in this forum (this is my first post here).
I've started this thread in the primegrid forum, and i have been suggested to ask to this community which have an higher % of skilled matematicians (i'm 'only' an engineer). I'm just asking for an opinion on the following idea for decomposing large numbers: it is the statement of an equivalent problem which (obviously) i have not solved. I had this idea some years ago and i always asked myself if it was a good idea.... so why not share it on the internet? The keypoint is synthesized as follows: we have a big N and we want to find p such that N/p is integer. Instead of solve this problem we can work on N/(ax), and then consider the polinomy P(x) obtained as a Taylor expansion of this new ratio. I've write a very short report as a pdf (there are some formulas unwritable in text mode). Also sorry for bad english. http://www.filefactory.com/file/4t8q.../primi_eng_pdf The file is hosted by a free hosting service. Just select "slow download" , enter the captcha and wait for the countdown. EDIT [I've attached the file to the message] Last fiddled with by HellGauss on 20120411 at 22:47 Reason: This forum can host files! 
20120411, 22:54  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·2,399 Posts 
This forum does support tex. Use [tex]\pi[/tex] which would be rendered as . It's spelled "polynomial" (not trying to pick on you, just improving the English ). What's your native language?
Edit: I see you edited in the PDF, that hadn't occurred to me Last fiddled with by Dubslow on 20120411 at 23:00 
20120412, 00:16  #3  
Nov 2003
2^{6}·113 Posts 
Quote:
I looked at you .pdf. I did not scrutinize each statement, but it seems cogently written. The gist of the paper is to turn the factoring problem into one of diophantine approximation. This sort of approach has been looked at extensively. The final polynomial inequality can be solved using techniques of lattice basis reduction; a fairly high dimensional lattice reduction. Applying (say) LLL or similar techniques to such problems has been shown by a number of people to lead to purely exponential algorithms. (e.g. Coppersmith) The technique is generally hopeless for factoring. 

20120412, 00:52  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2^{3}·1,109 Posts 

20120412, 13:52  #5 
Apr 2012
5 Posts 
Thanks for your replies, and also for referring the Coppersmith algorithm.
It is enough for me to know that someone else has followed this approach. One last remark before closing this problem, which seems to be a bad road to follow, as stated by R.D. Silverman: The polynomial i have written in the last formula may be written also as But this is probably useless... Thanks again. PS: I'm Italian 
20120412, 14:01  #6 
"Nancy"
Aug 2002
Alexandria
2464_{10} Posts 
Judging by Bob's posting, this might well go in the Math forum.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Transforming the factorization problem into a game  Alberico Lepore  Alberico Lepore  1  20170928 10:14 
Methods of attacking a large factorization  CRGreathouse  Factoring  55  20140411 15:05 
Dual Core P95 64Bit P4 Equivalent problem  g0ods  Software  9  20090915 14:12 
Fermat numbers factorization  ET_  Factoring  15  20080312 21:24 
How do I get LARGE numbers  Bundu  Software  5  20040826 01:56 