Here’s another “formula” for prime numbers, due to John H. Conway. Start with the number 2. Then, go down the following list of 14 fractions and multiply by the first one that would give you an integer answer. Now take your new number and go down the list, etc. Whenever you get a power of 2, 2[sup]N[/sup], N will be prime. Moreover, you will get the primes in order: 2[sup]2[/sup], 2[sup]3[/sup], 2[sup]5[/sup], 2[sup]7[/sup], 2[sup]11[/sup], etc.
> . . . it churned out thousands of results (we did not have the
> time to test all of them once they got very big, but we were
> unable to find a non-prime by random sampling).
Let me get this straight. You generated the first several thousand numbers produced by this formula. You looked at them and said, “Gee, they look like primes.” You tested a few of them and they happened to be primes, in fact. And from that, you conclude that this formula always produces primes. Um, not good enough. Show us the formula and let us test it.
I have no intention of doing that; there are two places left to look for the code;
My old computer at my last place of work (which was where I actually wrote the program), but that was some years ago now so it might be in a landfill somewhere.
My old computer at home; I’m not sure if the thing even boots anymore, but it’s worth a try.
Failing that, I need to find a way of remembering what it was; it is so tantalising because it’s right on the tip of my tongue. Maybe I need to get slightly drunk.
The Weak Force, the site Squink linked to mentions, about the method you describe, that:
Not that it isn’t wickedly cool and clever, but I just thought I’d point out that it’s a disguised version of one of the simplest and oldest methods of finding primes.
Oh, and one last thing: I just noticed that there are a few discrepencies between the fractions you list, and the ones listed on Mathworld. They give the series as:
Very close to yours, but different in the third-to-last and second-to-last positions. I’m at work now, so I can’t investigate how that affects the function of the algorithm. I leave that to someone else.
Naw, he’s already said too much. Clearly, he didn’t even test it, so that’s not necessarily what we’re looking for. Even as far back as 1837, Dirichlet proved that every arithmetic progression a + nd, where a and d are relatively prime positive intergers, generates an infinite number of primes as n takes on different integer values.
Both RSA and El Gamal public-key algorithms are based on exponentiation. RSA (which uses keys based on primes) is calculated with big-integer arithmetic, not bitwise AND or XOR like you’d use in other types of crypto.
I think you’re mixing apples and oranges. A 128-bit key is trivially short for most public-key systems, especially RSA and others based on primes. RSA typically uses keys of 2000-4000 bits. A 128-bit key is typically used in symmetric systems like AES which has nothing to do with primes. But you’re absolutely right that the best known way to break RSA is to factor the key, and the fact that that is a “hard” task is what makes it secure.
My point is that you’ve not only proved nothing, you haven’t even made a credible case for your claim. Why should we be impressed by your claim that there’s a formula (which you haven’t specified) that you claim to have looked at some of the output of (but which you haven’t shown to us) and which you’ve checked a few of for primality (and how many is that? 10? 100?)? Furthermore, do you really think that so simple a formula as the one you say you have (you say it’s something like n^2 + (n+1)^3 + (n+2)^4) would really have never been noticed by mathematicians in all this time? This is the SDMB. Why are you surprised by my being sceptical about such a claim?
I’m not trying to impress anyone; I didn’t (and still don’t) think it will turn out to be an original idea, perhaps only an unconventional and cumbersome way of expressing something else.
I would dearly love to show you the formula, but you may have noticed me mentioning that I can’t find it. The testing that we carried out consisted of checking the output by iterative division up until the results got too big (IIRC >1,000,000) to make it practical to check every one. After that we only checked the last digits (no 2s 5s or 0s and chose a few random blocks of 5 consecutive results. We didn’t find a non-prime, but I’m not stupid enough to think that this constitutes any kind of rigorous proof.
And we would dearly love to see it ! Even if it fails after a few dozen iterations, it could still form the basis for some very profitable bar bets. Pay no attention to these nattering nabobs of negativity
I didn’t start posting in this thread to try to prove anything, I posted because I was hoping that somebody would say “oh yeah, it sounds like youi tripped over X’s theorem” or some such.
The guy I showed it to at work (the other half of the ‘we’ that tested it, a graduate in some field of science) was nonplussed by the whole thing.
I just spent the whole evening checking the contents of a massive stack of floppies. Perhaps I should give it up now; it’s nowhere to be found.
O.K., you say that you checked every value of the formula up to 1,000,000. Suppose the formula grows approximately as fast as n^2 + (n+1)^3 + (n+2)^4, which you say looked sort of like the formula you tried. Since n = 30 makes the formula greater than 1,000,000, you only tried 29 values.
Incidentally, I know you said that that isn’t exactly the formula you tried, but only something like it, but it’s easy to show that it doesn’t work. n^2 + (n+1)^3 + (n+2)^4 = n^4 + (9 * n^3) + (28 * n^2) + (32 * n) + 17. This is composite whenever n is divisible by 17. In fact, by the same sort of argument, no formula which looks much like your formula could possibly only generate primes.
I can’t remember exactly what the formula was, only the way it looked on paper; this being the case, it is a little premature to assume how fast it grows; I seem to remember that the sequence of results started off at quite low values, so it seems likely that there is some important detail missing (like maybe it was subtraction instead of addition, or something)
My impression from the tone of your responses is that you think I’m bulshitting you, which, if true, I resent deeply; if this is deception then I am wholly taken in myself (Obviously I can’t entirely dismiss this possibility - false memories and all that).
I’ve spent the whole night searching for any trace of the program and there’s now very little hope that it will turn up; I am working right now on trying to retrace the steps that led me up to the idea - it began like this:
x[sup]2[/sup] + y[sup]2[/sup] = z[sup]2[/sup] has integer solutions
x[sup]3[/sup] + y[sup]3[/sup] = z[sup]3[/sup] does not (according to Fermat, and later proven by Wiles)…
…squares…two parameters…Pythagoras theorem relates to 2D figures, so maybe 3 parameters for cubes…
x[sup]3[/sup] + y[sup]3[/sup] + z[sup]3[/sup] = n[sup]3[/sup]???
Now I KNOW the above is complete nonsense; it was just an idle daydreaming thought, but onward from there something happened; I just have to try to remember what - it can’t have been terribly complex as my mental arithmetic is not the best, yet I was able to test it for a few low input values without paper.
(x+1)[sup]3[/sup] - x[sup]3[/sup] produces some interesting results which (on very cursory examination by my bleary eyes) seem to be primes or divisible only by primes, I’ll work on this again tomorrow but I must sleep now.
