1
$\begingroup$

I know nothing of encrypting. I'm not even sure how to tag this. I wrote a program that can calculate this pretty quickly on my macbook pro 2.3GHz IntelCore i7. The two exponents are Mersenne primes, and no I did not use floats.

It calculated ((2^756839)-1) * ((2^1257787)-1) = a number 606,463 digits long. The exponentiation, multiplication, and all took about a minute? Would it be good for encrypting? Maybe not those numbers specifically, but in general because it wouldn't require me to use a supercomputer. And yes, that is 606,463 digits long. So prime*prime=N, where N, aside from 1 and itself, is only divisible by the two primes. Don't know if it'd be useful at all, but I did it for fun, for something else. I'm going to try working on the reverse(factoring N).

Improve this question
$\endgroup$
16
  • $\begingroup$ I'm sorry to say the answer is almost certainly no. Multiplying large numbers is something that has been studied in depth over the years, and the odds are your program does not provide a breakthrough. In the particular case you've given, there seems to be a shortcut to solving it anyway $\endgroup$
    – Cryptographeur
    Nov 6, 2013 at 16:56
  • $\begingroup$ I don't understand your second point, however, I do your first. Can I not use it myself for encryption? I mean, I have that entire number stored in a text file. It's 606,463 digits long. $\endgroup$
    – user2616745
    Nov 6, 2013 at 17:05
  • $\begingroup$ Working in binary notation (as your computer will be), $(2^{756839}-1)$ is the number given by 756839 consecutive 1's. Since $$(2^{756839}-1) * (2^{1257787}-1) = (2^{756839}-1)*2^{1257787} - 2^{756839} + 1$$ the answer will (in binary) have 756838 ones, followed by a single zero,followed by ~50100 ones, followed by 756839 zeros and then finally a 1. (nb: my counts may be out by +- a few, sorry, but the idea holds) $\endgroup$
    – Cryptographeur
    Nov 6, 2013 at 17:06
  • 2
    $\begingroup$ Just as a benchmark, Mathematica was able to compute the above in 0.01 seconds (as measured by Timing). My processor is an Intel i5-3570k at stock clock speeds. $\endgroup$
    – Reid
    Nov 6, 2013 at 17:26
  • 1
    $\begingroup$ @user2616745: Don't overestimate how much memory large numbers take up relative to the capacity of modern-day RAM. The two numbers you're multiplying only take up about 90 and 150 kilobytes, respectively... that's not much memory at all. $\endgroup$
    – Reid
    Nov 6, 2013 at 17:52

2 Answers 2

Reset to default
2
$\begingroup$

I can several possible questions in the original post, hopefully I'll manage to answer at least one of them here.

I have calculated a large $N$, with $\log_{10}(N)>600,000$. Is this suitable for RSA? We have that $\log_{10}(N)>6*10^5>2^{19}$, meaning $\log_2(N)>2^{19}$. Currently, implementations with $\log_2(N)\approx 2^{11}$ are coming into practice, making your choice of $N$ much much larger than those in use today. There's a nice little crypto.SE question here stating that there is no need for $N$ orders of magnitude greater than $2^{2048}$, with good references.

Is my multiplication algorithm good for taking the product of Mersenne Primes? I'm sorry to say the answer is almost certainly no. Multiplying large numbers is something that has been studied in depth over the years, and the odds are your program does not provide a breakthrough. In the particular case you've given (Mersenne primes), there is an efficient way to solve it anyway, so I suspect your implementation isn't as efficient as it could be:

Working in binary notation (as your computer will be), $(2^{756839}-1)$ is the number given by 756839 consecutive 1's. Since $$(2^{756839}-1) * (2^{1257787}-1) = (2^{756839}-1)*2^{1257787} - 2^{756839} + 1$$ the answer will (in binary) have 756838 ones, followed by a single zero,followed by ~50100 ones, followed by 756839 zeros and then finally a 1. (nb: my counts may be out by $\pm1$, but the idea holds)

Part of this answer is drawn from my comments on the original post.

Is my algorithm good for taking the product of two large integers? I do not know the headline speeds for integer multiplication in general, but I'm pretty sure you should be able to do this a lot more quickly than you have, especially since your multiplication doesn't make use of the binary representation of its operands. You can easily test this by downloading reference code for Big Integer multiplication and timing yours against that. If you have a licence, Magma or Mathematica are both good candidates for a first test. UPDATE: In the comments below, Reid provides benchmarking figures for Mathematica, demonstrating that your times are well off these, which should themselves be considered lower bounds.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Copying my comment from the original question: Just as a benchmark, Mathematica was able to compute the above in 0.01 seconds (as measured by Timing). My processor is an Intel i5-3570k at stock clock speeds. This was on Mathematica 8. So, this benchmark shows just how much research has been poured into fast integer multiplication. $\endgroup$
    – Reid
    Nov 6, 2013 at 17:27
  • $\begingroup$ Actually, it seems 0.01 seconds is the slowest. Having run the test about a dozen more times, my (admittedly unscientific) result is that the above computation takes somewhere around 0.006 seconds on average, or about 6 milliseconds. $\endgroup$
    – Reid
    Nov 6, 2013 at 17:46
  • $\begingroup$ How does it give you the full answer? Is it just displayed? I thought you'd need a cracker-jack load of Ram. I'm on 8GB. I need to study more, lol. $\endgroup$
    – user2616745
    Nov 6, 2013 at 17:49
  • $\begingroup$ @user2616745: Yep, it just gives me the answer in the prompt. Here is the notebook printed to a PDF (so this is pretty much exactly how the command shows up in the window, minus some minor styling differences). Edit: In fact, the bottleneck in Mathematica is actually writing the result to the notebook, not the computation itself... it visibly takes a second or so for the result to appear. But the computation itself (as you can see with Timing) doesn't take very long at all. $\endgroup$
    – Reid
    Nov 6, 2013 at 17:57
  • $\begingroup$ Hardcore computing!! I need to learn how to work in binary, or just learn more in general. Thanks a bunch! $\endgroup$
    – user2616745
    Nov 6, 2013 at 18:06
1
$\begingroup$

If it only multiplies mersenne primes then likely not.

For now I can think of RSA, DSA and the Diffie–Hellman key exchange for its uses (They use prime numbers).

There are not enough mersenne primes for it to be used by itself. May be in can be used as part of a process. (Specialization).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.