mersenneforum.org > Math An equivalent problem for factorization of large numbers
 Register FAQ Search Today's Posts Mark Forums Read

2012-04-11, 22:37   #1
HellGauss

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 key-point 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/(a-x), 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]
Attached Files
 primi_eng.pdf (88.2 KB, 163 views)

Last fiddled with by HellGauss on 2012-04-11 at 22:47 Reason: This forum can host files!

 2012-04-11, 22:54 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-04-12, 00:16   #3
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by HellGauss The key-point 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/(a-x), and then consider the polinomy P(x) obtained as a Taylor expansion of this new ratio.

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.

2012-04-12, 00:52   #4
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

23·1,109 Posts

Quote:
 Originally Posted by R.D. Silverman This sort of approach has been looked at extensively.
Which means, other smart people have come up with the idea before.
Which for my 2 centavos is a good thing.

 2012-04-12, 13:52 #5 HellGauss   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 $-N(x^{g+1}-\alpha^{g+1})/(x-\alpha)$ But this is probably useless... Thanks again. PS: I'm Italian
 2012-04-12, 14:01 #6 akruppa     "Nancy" Aug 2002 Alexandria 246410 Posts Judging by Bob's posting, this might well go in the Math forum.

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 1 2017-09-28 10:14 CRGreathouse Factoring 55 2014-04-11 15:05 g0ods Software 9 2009-09-15 14:12 ET_ Factoring 15 2008-03-12 21:24 Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 03:15.

Wed Nov 25 03:15:11 UTC 2020 up 76 days, 26 mins, 4 users, load averages: 2.19, 1.92, 1.58