mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-01-23, 11:47   #1
tetramur
 
"unknown"
Jan 2019
anywhere

13 Posts
Default Why integer factorization is in P/FP?

http://www.optimization-online.org/D...12/08/3591.pdf
https://www.researchgate.net/post/Ca...olynomial_time
I have some reasons to verify it additionally.
1) This proof is so elementary, for that it is highly unlikely to be true.
2) Maybe it contains one or more fatal mistakes.
3) There is no known algorithms to factorize number that lie in P.

Last fiddled with by tetramur on 2019-01-23 at 12:00
tetramur is offline   Reply With Quote
Old 2019-01-23, 13:55   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

The second link is merely baseless speculation (no, AKS can't do that). If you need another reason to doubt the first, it claims a proof of P = NP along the way.
CRGreathouse is offline   Reply With Quote
Old 2019-01-23, 15:10   #3
tetramur
 
"unknown"
Jan 2019
anywhere

1310 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
The second link is merely baseless speculation (no, AKS can't do that). If you need another reason to doubt the first, it claims a proof of P = NP along the way.
What I already have said. There can not be elementary proof of P = NP. If it was true, why scientists searched for proofs since 1970s and could not find?
tetramur is offline   Reply With Quote
Old 2019-01-23, 15:21   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×3×7×83 Posts
Default

Quote:
Originally Posted by tetramur View Post
http://www.optimization-online.org/D...12/08/3591.pdf
https://www.researchgate.net/post/Ca...olynomial_time
I have some reasons to verify it additionally.
1) This proof is so elementary, for that it is highly unlikely to be true.
2) Maybe it contains one or more fatal mistakes.
3) There is no known algorithms to factorize number that lie in P.
The first link refers to a 2000 paper by Khachiyan and Porkolab. I don't have access to that paper. But, judging by the post here,
Quote:
Moreover, even for semidefinite programming problems (SDP) in its general setting (without extra assumptions like strict complementarity) no polynomial-time algorithms are known, and there are examples of SDPs for which every solution needs exponential space. See Leonid Khachiyan, Lorant Porkolab. "Computing Integral Points in Convex Semi-algebraic Sets". FOCS 1997: 162-171 and Leonid Khachiyan, Lorant Porkolab "Integer Optimization on Convex Semialgebraic Sets". Discrete & Computational Geometry 23(2): 207-224 (2000).
I would go so far as to say that the paper doesn't say what the claimant says it says.

I would also imagine that, if the 2000 paper actually led directly to factorization in polynomial time as indicated, somebody would have noticed right away.

I also point out that the claimant doesn't actually give an algorithm for solving the integer programming problem in polynomial time. He merely asserts that it can be done, and then says "do it." If I had a polynomial time factorization method, I would give examples applying it to "challenge" and "most wanted" factorizations.

Last fiddled with by Dr Sardonicus on 2019-01-23 at 15:22
Dr Sardonicus is offline   Reply With Quote
Old 2019-01-23, 20:51   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

246216 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
I would also imagine that, if the 2000 paper actually led directly to factorization in polynomial time as indicated, somebody would have noticed right away.
Yeah. Adam Smith (further refined by John Nash) can help define and constrain where the optimal solution space is.

Using only broad strokes, one can often quickly determine what is worth drilling down on, and what is a "rabbit hole"....
chalsall is online now   Reply With Quote
Reply

Thread Tools


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
Integer factorization with q < 2p mgb Math 36 2009-11-07 15:59
Integer Factorization mgb Math 16 2007-12-17 10:43
Integer Factorization 2 mgb Math 5 2007-07-23 12:55

All times are UTC. The time now is 14:49.

Tue Sep 29 14:49:26 UTC 2020 up 19 days, 12 hrs, 0 users, load averages: 1.50, 1.90, 1.89

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.