Why does P=NP break public key cryptography?

boarhog · 22 days

If you know it's a prime. But that is not the comment I responded to. I responed to a comment which said it's "quite a lot harder if you don't [know it's prime]". So the explicit context is that you don't know it's a prime. So your "assumption" turns out to be wrong.

"You wouldn't be allowed to input a non-prime number to the algorithm." is likewise wrong.

You're thinking of the wrong algorithm. The algorithm you are thinking of can only be used if you know the number is prime. But as has been explicitly stated, we do not know this, so that algorithm is not even in consideration.

boarhog · 22 days

Not actually quite a lot harder. For a probablility of (3/4)^k , the complexity of checking if it is a prime is approx O(k*log(n)). So for example checking that 1,000,000,000,000,000,000,000,000,000,001 is prime with a failure rate of 2^-100 takes only about 28 times longer than checking if 101 is prime. Basically, it's really quick.

JimKB · 23 days

I'd be willing to bet that the result you gave me would have a factor <128 bits. And anyways, I think a 6-core machine with a GPU could find a 38 bit factor in a day.

Edit: More precisely, using GMP-ECM, a single core of my computer would have a 99.8% chance of factoring the product of two 40 bit numbers in 24 hours. I can't seem to figure out how to make it utilize my other cores and my GPU.

Edit: Even mroe specifically, it took my computer 1 hour 52 minutes to factor the product of two test 128 bit primes when I utilized my graphics card.

Edit: and your by-hand multiplication of two 128 bit numbers would require you to accurately take the product of two digits 1444 times, and then take make a total of 2243 digit additions on average. That's a total of 3687 operations. Assuming it takes you a second to locate, read, and write each of those operations, that will take you almost exactly an hour, with ZERO breaks. But wait a second. Let's take a guess, that if you were to take a 100 problem test with these sorts of simple problems, you'd get about 99.8% right. That's like getting 100% 4/5 times, and 99% 1/5 times, seems reasonable for us fallable humans. But that means if you're doing 3687 operations, that's an average of over 7 mistakes you would make while multiplying these numbers. So even if you were to try to be really accurate, my guess is you'd make at least one mistake. So you're going to need to do out the multiplication twice to make sure you didn't make any errors. So now that takes you two hours. And if you want to make my computer take a whole day to factor it, you're going to need to multiply two 45 digit numbers. And without doing out that whole calculation as before, long multiplication is quadratic in time, so (45/38)^2=1.4 so you're going to need to spend 1.4 times as long, or about three hours. But that's just to outdo my machine. To "outdo every machine for eternity", let's just substitute "outdo one of the largest factors found by general methods", which is a 232 digit factor. The time will be (232/38)²⁼³⁷ times as hard for you to multiply, i.e. taking you 75 straight hours. So that's like two weeks of your time if you're working 8 hour days. But we're also neglecting the higher order terms that come in for how long it takes you do check your work. And this is just scratching the surface of every computer ever forever... a worldwide botnet+the top ten super computers could do much better in just a couple years.

JimKB · 23 days

I claim that my personal computer could factor any pair of primes you could accurately multiply by hand.

RKstarfox · 24 days

Ah, the old reddit swit...NO I REFUSE!!!

TitoTheMidget · 25 days

Commenting here because everyone else missed it: There is a best system of counting votes: it's called the Condorcet winner. The only catch is that it doesn't always give you an answer, but if it does, it's always right.

The way you do this is you treat the listing not as points, but as rankings. Basically, you pair up all 15 possible pairs of your candidates. Then, for each pair, you determine which candidate is preferred more, by simply counting the number of times candidate A is ranked above candidate B, and vice versa. Now, if there is a candidate which wins in every one of these matchups, that candidate is the Condorcet winner.

In this particular case, it's easy to see that these "no confidence" votes simply count as abstaining for all the comparisons which do not involve their preferred candidate.

Hopefully your elections will have a condorcet winner, because then the choice is obvious.

tdobson · 27 days

Yes. Entirely different programs.

Jtl4231 · 27 days

Because it's a failure, it will not be widely known in the future, and thus nobody will think to visit the party, thus causing it to be a failure... it's the only stable time loop.

cjstop · 27 days

Their names are not adequately obscured. Look, I can figure out most of them! http://i.imgur.com/nhTuN.jpg

jason-samfield · 1 month

No. that's not true. What SmilinyYellowSofa suggests is entire possible, and is not the same as the realist position. All we know is that the particles don't have definite spins/locations/momenta, and that their measurements will correlate in a certain way. However, given a certain set of measurements with a certain set of correlations as determined by quantum mechanics, the process by which these "random" outcomes is determined is unknown, and, as SmilingYellowSofa suggests, this could be driven by some sort of deterministic process.

You're conflating two seperate ideas: 1. That particles do not have spin/whatever before you measure them. 2. That when measured, the measurements are unpredictable.

mathbje · 1 month

Fork bomb, I believe?

CerealKilla1 · 1 month

Uh, not really a question, but my friend is writing a TV show in which the main character has a similar backstory. Good Luck!

snowballman · 1 month

Are you saying these events are correlated?

moordeb · 1 month

Aspergers is not socially fatal. Certainly it could be in a self-fulfilling prophecy way, if you think it is impossible for you to change because of it. However, I'd suspect that your real problem is that your Aspergers exacerbates the issue of you not experiencing affection as a child. There are plenty of people with Aspergers who give and receive affection (if not precisely in the same manner as others).

Not just for her sake, but also for your own, you should consider trying to experience affection in a positive way. Certainly explaining to her that this is something new to you would be helpful: for most people, a lack of affection implies something which is missing, not simply an implicit assumption you had about your social relationships.

Aspergers is not a reason not to enjoy affection in your life.

MoreOvaltine · 2 months

No, you mean

when my around does what? You cut off mid sentence!! Tell me what my around does!!

WiglyWorm · 2 months

http://wiki.debian.org/DesertIslandTest

Perhaps what you want to do is attach a request for users to notify you, but don't make it a binding element of the license.

WiglyWorm · 2 months

If you want a required donation, the best way is to simply release it under a copyleft license (like the GPL) and make it clear that you are willing to negotiate other licensing terms with corporations. (Or you could offer it for sale for a fixed price under a commercial license). Basically you want to give two different groups of people different rights. The best way to do so is give it to them under different licenses.

kidthebilly · 2 months

https://www.youtube.com/watch?v=lXpmHuCE9Ls

Netzapper · 2 months

You can set it as your default output device easily. I thought you wanted on-the-fly switching between multiple sound cards. http://alsa.opensrc.org/FAQ026

Netzapper · 2 months

No, that's not what I'm asking... I'm asking what application you are using.

Netzapper · 2 months

If you're switching output devices on the fly, I'm guessing you're using some sort of audio production app? I'd expect it to either support device switching (i.e. select the hw:1 device you want to output to) or it to support jack, which is a much better solution for switching output devices on the fly.

Netzapper · 2 months

No, really, an ALSA-only desktop works perfectly. I run it, and I never have problems (as opposed to the numerious problems I've always encountered on the various computers I have when they had pulseaudio installed). Regardless of how much pulseaudio has improved, you still don't need it for regular desktop use. Everything supports ALSA. Use dmix as your default alsa device, and everything will just work. I promise you. Multiple applications playing sound simultaneously, etc. Plus, it will only be faster than pulseaudio.

Netzapper · 2 months

No, really, pulseaudio is not necessary for any apps. ALSA provides its own OSS compatibility layer. A lot of distros don't use pulseaudio, so it would be stupid for any app to use pulseaudio exclusively, even in the future. ALSA or OSS are both supported wherever pulseaudio is supported plus more places... why would anyone choose pulseaudio over them, especially since it doesn't offer real-time performance like jack does?

Netzapper · 2 months

You're doing ALSA wrong if you can't get multiple sounds at once. You should always use the dmix output. This will mix the audio in software if your card doesn't support it. This is perfectly well supported by any alsa app, and really should be what you are using. You should never be using hw:0 for direct audio output. Either use jack on to of hw:0, or use dmix on top of it. I'm surprised your system was not set up to use dmix by default. My guess is that because it was set up to use pulseaudio by default, it was misconfigured for the use case of ALSA only, making it seem like you needed pulseaudio.

As for controlling volume levels per application: Name an application which does not have an internal volume control... every flash video player I know has one. Every music player I know has one. Every synthesizer I know has one. Every DAW I know has one. Every game I know has one. Pulseaudio just adds an additional volume control, so now you have two volume controls per app, in addition to your system volume control, and the redundant knob on your speakers.

The only use case of pulseaudio is A) Poor quality apps that don't have built in sound control (and really, if it's only one app like this, you can just adjust the system volume to control it, and individually adjust the volume of your other apps). B) If you want to sling sound around between computers, without having to start up jack.

jeremybub

TROPHY CASE

jeremybub

TROPHY CASE

you'll need to login or register to do that

create a new account

login