mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-04-11, 22:37   #1
HellGauss
 
Apr 2012

5 Posts
Default 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
File Type: pdf primi_eng.pdf (88.2 KB, 157 views)

Last fiddled with by HellGauss on 2012-04-11 at 22:47 Reason: This forum can host files!
HellGauss is offline   Reply With Quote
Old 2012-04-11, 22:54   #2
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

This forum does support tex. Use [tex]\pi[/tex] which would be rendered as \pi. 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 2012-04-11 at 23:00
Dubslow is offline   Reply With Quote
Old 2012-04-12, 00:16   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by HellGauss View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-04-12, 00:52   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

32·967 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Uncwilly is online now   Reply With Quote
Old 2012-04-12, 13:52   #5
HellGauss
 
Apr 2012

516 Posts
Default

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
HellGauss is offline   Reply With Quote
Old 2012-04-12, 14:01   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246410 Posts
Default

Judging by Bob's posting, this might well go in the Math forum.
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Transforming the factorization problem into a game Alberico Lepore Alberico Lepore 1 2017-09-28 10:14
Methods of attacking a large factorization CRGreathouse Factoring 55 2014-04-11 15:05
Dual Core P95 64Bit P4 Equivalent problem g0ods Software 9 2009-09-15 14:12
Fermat numbers factorization ET_ Factoring 15 2008-03-12 21:24
How do I get LARGE numbers Bundu Software 5 2004-08-26 01:56

All times are UTC. The time now is 02:17.

Wed Oct 21 02:17:31 UTC 2020 up 40 days, 23:28, 0 users, load averages: 1.81, 1.71, 1.67

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.