Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Innovation, my TSP algorithm and factoring, timelines

Reply
Thread Tools

Innovation, my TSP algorithm and factoring, timelines

 
 
JSH
Guest
Posts: n/a
 
      08-23-2008
Turns out that there is a lag between pickup of any revolutionary idea
and its presentation.

I have research into the factoring problem which I think is kind of
good, though I didn't actually finish an algorithm as I decided it was
too dangerous. Gist of that research was to consider two congruences
where mathematicians typically consider one:

x^2 = y^2 mod p
z^2 = y^2 mod T

where T is the target composite to be factored and p is an odd prime
that I call a helper prime as it's just there to help you factor T. I
solved out the problem with a couple of additional variables as one of
my key problem solving techniques involves adding in extra variables,
or degrees of freedom as physics people like to say (I think as I'm a
physics person).

If I'm right then it turns out that I don't actually have to finish
out the research but the time lag until someone does, if I'm right,
would be anywhere from 6 months to 2 years which is kind of a W.A.G.
but I think it's roughly correct.

Now more recently I came up with an algorithm which I think solves the
Traveling Salesman Problem and in so doing proves that P=NP, as
naturally, from thinking I have a break on the factoring problem, I'd
go to TSP looking to apply the same type techniques against it!

And doing so I came up with two travelers where one is going backwards
in time and you multiply the costs along legs times the distance
between the two travelers to figure out the total cost of a path and
pick the least cost path, using a global variable.

Now THAT algorithm is a couple of weeks old but I've given a complete
algorithm, so that should speed things up, so I'd estimate that it'd
take from one month to a year before it's picked up somewhere in the
world if it is correct.

Which leaves me with nothing to do but wait.

Oh, so why not simply implement myself? Like solve the factoring
problem? Or directly prove that the TSP algorithm works?

Well, they might be wrong! And I don't want the disappointment if so!

And, I gain little with success. Now I'm some "crackpot" mouthing off
on Usenet. With success I'd have to be someone else. There'd be a
tremendous weight of public opinion on me when I did things that
people disapproved of, and the scariest thing is that whole role model
thing.

I don't want to be a role model.

And I don't want to answer a lot of stupid questions, so there.

If I were truly irresponsible I'd simply keep the research to myself
and let the world go hang.

But instead I'm at least putting it out there, though you people so
sorely tempt me. If I could just put all of it back in the bottle so
to speak, I'd be very tempted as trust me, it's a stupid world. I'm
really scared of being dragged down to doom with the rest of you
people, but hey, maybe that's just destiny.

So, in any event, I get to party, be irresponsible to an extent, and
have silly conversations with funny people who take themselves too
seriously and think they know more than they do, while not feeling
like I'm cheating the world as the information is out there.

People just have to use it.

Or not!

IF I am wrong, then of course, no one will ever do anything with my
ideas, so there.

It's a nice complete package which allows me to go back to silly
conversation with funny people.


James Harris
 
Reply With Quote
 
 
 
 
Joshua Cranmer
Guest
Posts: n/a
 
      08-23-2008
JSH wrote:
> I have research into the factoring problem which I think is kind of
> good, though I didn't actually finish an algorithm as I decided it was
> too dangerous.


Factoring's not dangerous... real security has progressed to more
advanced forms, like elliptic curves. RSA retracted its factoring
challenge because they considered the art sufficiently advanced that it
wasn't needed anymore. Factoring is essentially a solved problem.

> If I'm right then it turns out that I don't actually have to finish
> out the research but the time lag until someone does, if I'm right,
> would be anywhere from 6 months to 2 years which is kind of a W.A.G.
> but I think it's roughly correct.


From what I've read on sci.math, it seems that your factoring algorithm
as some subtle flaws, like the fact that is unable to a number like 6.
My questions on that forum still stand, months-old as they are.

Moving out of mathematics and into CS...

> And doing so I came up with two travelers where one is going backwards
> in time and you multiply the costs along legs times the distance
> between the two travelers to figure out the total cost of a path and
> pick the least cost path, using a global variable.


And that was wrong.

> Oh, so why not simply implement myself? Like solve the factoring
> problem? Or directly prove that the TSP algorithm works?
>
> Well, they might be wrong! And I don't want the disappointment if so!


So you want all the credit if it works and none of the toil of actually
checking it? The world doesn't work like that. He who makes it work gets
the credit.

> I don't want to be a role model.


While I don't wish mean to be rude, I doubt you would even if you solved
<insert major problem here>.

> But instead I'm at least putting it out there, though you people so
> sorely tempt me. If I could just put all of it back in the bottle so
> to speak, I'd be very tempted as trust me, it's a stupid world. I'm
> really scared of being dragged down to doom with the rest of you
> people, but hey, maybe that's just destiny.


With all due respect, AFAICT, your great innovations seem to be down a
dead-end path. Your surrogate factoring algorithm (AIUI) allows the
surrogates to get arbitrarily big without anything to really convince me
that it gets smaller. The TSP solution relies on simple properties that
do poor jobs of reflecting the complexity of the graph.


Well, at least we are on the road to reclaiming c.l.j.p....

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
 
 
 
JSH
Guest
Posts: n/a
 
      08-23-2008
On Aug 22, 6:13*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > I have research into the factoring problem which I think is kind of
> > good, though I didn't actually finish an algorithm as I decided it was
> > too dangerous.

>
> Factoring's not dangerous... real security has progressed to more
> advanced forms, like elliptic curves. RSA retracted its factoring
> challenge because they considered the art sufficiently advanced that it
> wasn't needed anymore. Factoring is essentially a solved problem.


They just won't pay. The numbers are still up.

Are you claiming that the other RSA challenge numbers have been
factored?

The Internet still uses public key encryption.

If P=NP, then a polynomial time solution is possible for factoring
meaning that public key encryption is no longer viable as a security
system.

It'd be the end of one way systems like it as well, meaning that
people would have to trade keys by some other means, like, oh, snail
mail.

> > If I'm right then it turns out that I don't actually have to finish
> > out the research but the time lag until someone does, if I'm right,
> > would be anywhere from 6 months to 2 years which is kind of a W.A.G.
> > but I think it's roughly correct.

>
> *From what I've read on sci.math, it seems that your factoring algorithm
> as some subtle flaws, like the fact that is unable to a number like 6.
> My questions on that forum still stand, months-old as they are.


Yeah, it won't factor numbers that have 3 as a factor because it uses
helper primes where the helper prime has to be less than the smallest
factor, so ironically it will not factor 15.

That's irrelevant to the issue of how well the technique might work
against really large numbers where there are other bigger practical
issues that I do not say have been solved.

> Moving out of mathematics and into CS...
>
> > And doing so I came up with two travelers where one is going backwards
> > in time and you multiply the costs along legs times the distance
> > between the two travelers to figure out the total cost of a path and
> > pick the least cost path, using a global variable.

>
> And that was wrong.


I'm not debating whether it is wrong or right. I'm merely stating
facts.

> > Oh, so why not simply implement myself? *Like solve the factoring
> > problem? *Or directly prove that the TSP algorithm works?

>
> > Well, they might be wrong! *And I don't want the disappointment if so!

>
> So you want all the credit if it works and none of the toil of actually
> checking it? The world doesn't work like that. He who makes it work gets
> the credit.


I don't have to check it.

If it's right then someone in the world will eventually use it.

So talk on the subject is irrelevant.

> > I don't want to be a role model.

>
> While I don't wish mean to be rude, I doubt you would even if you solved
> <insert major problem here>.


That would be nice. It's such a silly world.

Adults should be able to do as they please as long as they're not
hurting themselves or others.

> > But instead I'm at least putting it out there, though you people so
> > sorely tempt me. *If I could just put all of it back in the bottle so
> > to speak, I'd be very tempted as trust me, it's a stupid world. *I'm
> > really scared of being dragged down to doom with the rest of you
> > people, but hey, maybe that's just destiny.

>
> With all due respect, AFAICT, your great innovations seem to be down a
> dead-end path. Your surrogate factoring algorithm (AIUI) allows the
> surrogates to get arbitrarily big without anything to really convince me
> that it gets smaller. The TSP solution relies on simple properties that
> do poor jobs of reflecting the complexity of the graph.


I'm not doing surrogate factoring further. It's too dangerous.

I'm not discussing the merits of my optimal path algorithm.

> Well, at least we are on the road to reclaiming c.l.j.p....



Not really. My stated objective is to recruit for my Google Code
project implementing my optimal path algorithm. You claim it doesn't
work. Ok. Moving on.

Also I'm just hanging out and chatting.

Nothing has changed except you have clearly wasted your time if you
truly believe there is nothing to my research.

I, on the other hand, am continuing to popularize my research and can
do things like check Google search results (can you for anything you
do?) as well as look over site statistics for my various web sites.

How do you think I got to the point where my blog gets hits from over
80 countries?

And it's better here from my perspective as there are fewer cases
where I have people just calling me names or just wildly ranting or
replying with complete nonsense which is a major issue on other
newsgroups where posters have gone to drastic tactics to try and
control what they see as their newsgroups.

The newsgroup sci.crypt was crippled by someone just bombing it with
nonsense postings though I don't think that was my fault, but seemed
to be about other web wars.

Regardless, you do better NOT drawing interest with a lot of replies
to my posts as at best you help generate more attention for my
research where you can do the Google searches to see what that means,
or at worst you can attract some of the nastier denizens of Usenet who
might try to cripple your newsgroup--though hopefully that nonsense is
at an end.

The reality that I have nothing further to do but wait has not
changed.

And in the meantime I can hang out and chat, goof off, and just do
whatever while the innovation pickup lag goes through its inevitable
paces.


James Harris
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      08-23-2008
JSH wrote:
> The Internet still uses public key encryption.


Public key encryption does not equal RSA or other factoring. As I've
said before, there's elliptic curve; there are other even more secure
algorithms.

> If P=NP, then a polynomial time solution is possible for factoring
> meaning that public key encryption is no longer viable as a security
> system.


No, it just means you have to keep bumping up key sizes every few years.

> I don't have to check it.


You do if you want to claim that it's correct, which you do a lot of.

> I'm not doing surrogate factoring further. It's too dangerous.


No, it's not. To suggest otherwise is to demonstrate your ignorance of
computer security.

> I, on the other hand, am continuing to popularize my research and can
> do things like check Google search results (can you for anything you
> do?) as well as look over site statistics for my various web sites.


As I matter of fact, I can. But I'm not going to debase myself to such
pointless comparisons. Suffice to say, I would be willing to hazard that
the work of most posters in this newsgroup could easily outstrip you in
the most important metric, i.e., how many people actually use the product.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Junoexpress
Guest
Posts: n/a
 
      08-23-2008
> Turns out that there is a lag between pickup of any revolutionary idea
> and its presentation.
>

Although the waiting time for anyone picking up one of *your* ideas is
not finite.

> I have research into the factoring problem which I think is kind of
> good, though I didn't actually finish an algorithm as I decided it was
> too dangerous.


Just another lame attempt at avoiding reality...



M
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-23-2008
On Aug 22, 7:39*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > The Internet still uses public key encryption.

>
> Public key encryption does not equal RSA or other factoring. As I've
> said before, there's elliptic curve; there are other even more secure
> algorithms.
>
> > If P=NP, then a polynomial time solution is possible for factoring
> > meaning that public key encryption is no longer viable as a security
> > system.

>
> No, it just means you have to keep bumping up key sizes every few years.


Not with anything that would follow from my research.

If what I call surrogate factoring is viable then public key
encryption is dead.

People could literally crack public keys in seconds on a desktop, when
my own goal had been cracking one within 10 minutes, which is why I
stopped doing the research when I realized that if it could be made to
work, it would be super fast, as in unbelievably fast, ending public
key encryption over night.

You have no idea what you're poking at here.

If my research line in this area were fully exploitable as in correct
then it could literally collapse the global economy.

> > I don't have to check it.

>
> You do if you want to claim that it's correct, which you do a lot of.


Um, but if I'm claiming it's correct now, but have not checked it...

Seems to contradict your claim of what I must do.

> > I'm not doing surrogate factoring further. *It's too dangerous.

>
> No, it's not. To suggest otherwise is to demonstrate your ignorance of
> computer security.


If someone has extended the research and it is viable then they are
cracking public key encryption like it doesn't exist, right now.

If the optimal path algorithm is viable and proves that P=NP, then
someone might also know that they can crack ANY system that tries to
use the one way easy, other way hard approach, meaning they could
crack military encryption doing the same stuff.

And if the country that has done that is not a Western power then it
would keep that as a secret for strategic reasons, and that could have
happened by now.

If so, then the world as we know it will change, and there will be a
total change in the world order as THAT nation, will end up on top.

> > I, on the other hand, am continuing to popularize my research and can
> > do things like check Google search results (can you for anything you
> > do?) as well as look over site statistics for my various web sites.

>
> As I matter of fact, I can. But I'm not going to debase myself to such
> pointless comparisons. Suffice to say, I would be willing to hazard that
> the work of most posters in this newsgroup could easily outstrip you in
> the most important metric, i.e., how many people actually use the product..


Yeah, yeah, some of you have done Linux distribution stuff, or worked
on developing this or that, but none of you are the individual who
runs it all from start to finish, who has complete control, and is
competing against the world with the likes of Microsoft way behind.

And none of you can do a search on anything like "definition of
mathematical proof" and see your own personal definition come up #2,
just behind the Wikipedia.


James Harris
 
Reply With Quote
 
willo_thewisp@hotmail.com
Guest
Posts: n/a
 
      08-23-2008
On Aug 22, 8:35*pm, JSH <(E-Mail Removed)> wrote:
>
> Now more recently I came up with an algorithm which I think solves the
> Traveling Salesman Problem and in so doing proves that P=NP,
>

Hi, James. I see that you're still too stupid to understand the
counterexamples that have already been posted. Nice to see that
nothing's changed.
 
Reply With Quote
 
Alan Morgan
Guest
Posts: n/a
 
      08-23-2008
In article <(E-Mail Removed)>,
JSH <(E-Mail Removed)> wrote:
>On Aug 22, 7:39=A0pm, Joshua Cranmer <(E-Mail Removed)> wrote:
>> JSH wrote:
>> > The Internet still uses public key encryption.

>>
>> Public key encryption does not equal RSA or other factoring. As I've
>> said before, there's elliptic curve; there are other even more secure
>> algorithms.
>>
>> > If P=3DNP, then a polynomial time solution is possible for factoring
>> > meaning that public key encryption is no longer viable as a security
>> > system.

>>
>> No, it just means you have to keep bumping up key sizes every few years.

>
>Not with anything that would follow from my research.
>
>If what I call surrogate factoring is viable then public key
>encryption is dead.
>
>People could literally crack public keys in seconds on a desktop,


Depends on the key size and on the nature of the algorithm. If
factoring turns out to be O(n^5000000) then P=NP, but I don't see
that causing many practical problems. Even if it is something more
tractable you can just crank the key size through the roof.

Alan
--
Defendit numerus
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-23-2008
On Aug 22, 7:39*pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> JSH wrote:
> > The Internet still uses public key encryption.

>
> Public key encryption does not equal RSA or other factoring. As I've
> said before, there's elliptic curve; there are other even more secure
> algorithms.
>
> > If P=NP, then a polynomial time solution is possible for factoring
> > meaning that public key encryption is no longer viable as a security
> > system.

>
> No, it just means you have to keep bumping up key sizes every few years.
>
> > I don't have to check it.

>
> You do if you want to claim that it's correct, which you do a lot of.
>
> > I'm not doing surrogate factoring further. *It's too dangerous.

>
> No, it's not. To suggest otherwise is to demonstrate your ignorance of
> computer security.


Ok. Here's the research result at which I stopped which is a way to
solve for quadratic residues mod p, but the "p" which is for an odd
prime, can be replaced with an "N" for natural number which can be a
composite to be factored.

Given a quadratic residue q modulo p where p is an odd prime, where

k^2 = q mod p

it is a method to find k, which comes from reversing some of the
surrogate factoring equations.

As usual with my research you get additional variables as now you need
T, where

T = 2q mod p

and while you'll want the smallest T--because it has to be factored--
you must pick an odd T, where T - 2q must be non-zero.

Next you have to factor T, as with integer factors f_1 and f_2 of T,
where f_1*f_2 = T:

k is given by

k = 3^{-1}(f_1 + f_2) mod p.

And my analysis indicates that there should be a 50% probability that
you will get the correct k with each set of factors (weirdly too
simple, I know, but hey, just wrong?). Checking is done by just
squaring your k modulo p to see if you get back the correct quadratic
residue q.

Example: Let q=2, p=17 so T = 2(2) mod 17 = 4 mod 17.

Here T=21 does not work, but T = 55 does, and the answer then from

3k = 2( mod 17, is k = 11 mod 17, as 112 = 2 mod 17 as required.

To have an absolute case when you must get a solution for k, T mod 3 =
2 is required, and one of the factors f_1 or f_2 when both are
positive and non-unit must be greater than p (which again has to do
with why 15 doesn't work!), then k is given exactly by

k = (f_1 + f_2)/3

with 100% certainty.

If T mod 3 = 1, because p mod 3 = 1 and q is divisible by 3, then an
alternate set of equations can be used as then

T = 10q mod p

and

k = 19^{-1}(3(f_1 + f_2)) mod p

and an exact solution occurs if with positive factors f_1 or f_2 is
greater than p, both are non-unit, and z is divisible by 19 as then

k = 3(f_1 + f_2)/19.

That is an incredibly small bit of research in terms of physical size,
but if it's right, then public key encryption is dead, as replace the
p with N, where N is your target composite to factor, then calculate a
quadratic residue modulo N and then use the equations above to solve
for that same residue and you may get back your original or its pair.

i.e. If you start with 'a' you may get back 'b', where

a^2 = b^2 mod N

and factor N from (a-b) or (a+b), and THAT is what paused me and later
sent me looking for an algorithm for TSP.

But you say everything is fine, and no worries! So Joshua, we'll go
on your opinion here for the moment.


James Harris
 
Reply With Quote
 
JSH
Guest
Posts: n/a
 
      08-23-2008
On Aug 23, 1:16*pm, rossum <(E-Mail Removed)> wrote:
> On Sat, 23 Aug 2008 12:05:31 -0700 (PDT), (E-Mail Removed)
>
>
>
> (Alan Morgan) wrote:
> >In article <(E-Mail Removed)>,
> >JSH *<(E-Mail Removed)> wrote:
> >>On Aug 22, 7:39=A0pm, Joshua Cranmer <(E-Mail Removed)> wrote:
> >>> JSH wrote:
> >>> > The Internet still uses public key encryption.

>
> >>> Public key encryption does not equal RSA or other factoring. As I've
> >>> said before, there's elliptic curve; there are other even more secure
> >>> algorithms.

>
> >>> > If P=3DNP, then a polynomial time solution is possible for factoring
> >>> > meaning that public key encryption is no longer viable as a security
> >>> > system.

>
> >>> No, it just means you have to keep bumping up key sizes every few years.

>
> >>Not with anything that would follow from my research.

>
> >>If what I call surrogate factoring is viable then public key
> >>encryption is dead.

>
> >>People could literally crack public keys in seconds on a desktop,

>
> >Depends on the key size and on the nature of the algorithm. *If
> >factoring turns out to be O(n^5000000) then P=NP, but I don't see
> >that causing many practical problems. *Even if it is something more
> >tractable you can just crank the key size through the roof.


My research approach to factoring has been towards finding something
that would be faster than public key use, which I'm worried now can be
achieved--if the research is correct.

So, regardless of the size of the public key, it could be factored
faster than it could be used.

> >Alan

>
> Or switch from RSA-Public Key to El Gamal-Public Key. *There are many
> different versions of Public Key, of which only a subset depend on the
> difficulty of factoring.
>
> rossum


But if P=NP then there are polynomial time solutions out there for ANY
of them.

That's why I think the research community has resisted any claims of
proof of P=NP, for political and economic reasons, so that people
would use these systems without fear that down the line--out of the
blue--they could be completely cracked.

Possibly they have believed like the poster Alan Morgan that even if
factoring can fall to a polynomial time solution, it'd be a very slow
one, so they can rationalize their behavior as not being threatening
to security.

In considering my own latest research with the optimal path engine,
however, if it is correct then they are very, very, very wrong, and if
P=NP then super fast algorithms are possible that would make one way
systems non-viable.

That could have military implications as well if I'm reading some info
correctly that <gasp> the military has also thought to use one way
systems as well, though I'm not sure on that one, as I don't know
really what military agencies do for encryption.


James Harris
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
My TSP idea, google code and google group, thanks! JSH Java 0 08-03-2008 05:43 PM
Distance normalized TSP algorithm JSH Java 18 07-27-2008 03:31 AM
design timelines Trans Ruby 1 11-15-2007 01:11 PM
Richard Heathfield's TSP permutation algorithm whitehatmiracle@gmail.com C Programming 12 09-22-2006 10:12 AM
How to get CiscoIOSTSP3.1.zip (TSP Light TAPI driver)? Cisco 0 06-18-2005 08:19 AM



Advertisments