0
$\begingroup$

I've developed a bit of Mathematica code that can find primes within a range of numbers. For example, if I wanted all the primes between one million and two million, it could do that. Of what use is this code I invented ?

The only thing I could think of was that if one wanted to find two primes of a certain size for cryptography keys.

And the code could be used to test a specific number for primality, quickly.

And with the addition of code, it could be made to search for primes of a certain format, like safe primes.

I just invented this last week

Copy the following into Mathematica, select all, right-click on Convert To, choose StandardForm.

N[Sum[2/10^((n*(Floor[c/n] + 1) - c)*s), {n, 1, Floor[Sqrt[ c]]}] + Sum[ 2/(10^((n*(Floor[c/n] + 1) - c)*s)* (10^(ns) - 1)), {n, 1, Floor[Sqrt[ c]]}] + Sum[2/(10^((o^2 - o - c) s)*(10^(o*s) - 1)), {o, Floor[Sqrt[c]] + 1, max}], ((max + 1)^2 - c)*s]; AbsoluteTiming[Flatten[ Position[Partition[ RealDigits[%][[1]], s, s, -1], {(0) .., 2}]]] + c -end c=crossover s=spacing

The crossover is the number which you want to surpass. The spacing is difficult to determine, so I'll say that in general, if you use a number which is equal to the number of digits of the max^2, you should be safe. So for all primes up to $100^2 = 10000$, that is five digits, so use a 5 for the spacing. Follow this rule and you should be safe.

For those who are wondering, the code is based on a bigger structure of numbers formed by the Sieve of Eratosthenes.

$\endgroup$
  • 3
    $\begingroup$ In Mathematica, RandomPrime[{$i_\text{min}$,$i_\text{max}$}] gives a pseudorandom prime number in the range {$i_\text{min}$,$i_\text{max}$}. $\endgroup$ – fgrieu Mar 13 '15 at 19:35
  • $\begingroup$ PrimeQ is also of interest. $\endgroup$ – Thomas Mar 14 '15 at 4:02
  • $\begingroup$ I am not a Mathematica user, so I might be jumping to conclusions. However I strongly suspect it is possible to restructure your code to make it more readable. As for performance, how quickly would your code be able to find all the safe primes in a range such as $2^{8192}\pm 2^{28}$? $\endgroup$ – kasperd Mar 14 '15 at 14:33
  • $\begingroup$ @kasperd , I might be able to do that. That's a larger range of numbers than I've ever tried before though. Might take a day. $\endgroup$ – user24719 Mar 19 '15 at 3:30
4
$\begingroup$

I'm sorry to say that your code is likely to have essentially zero use.

Primes used for cryptography (e.g., RSA), are on the order of 2,048 and 4,096 bits of length, or respectively roughly 616 and 1,233 digits long. Algorithms already exist to rapidly find (random) primes of this size, and unless you've broken new ground in number theory, your approach is slower.

Additionally, the general trend lately is moving away from systems like RSA towards elliptic-curve based cryptosystems which have no need for the generation of primes.

$\endgroup$
  • 3
    $\begingroup$ RSA moduli today are 2048 bits and up; the two prime factors are half the modulus size. In addition to time, if this code like a standard sieve would need e.g. 2^512 bits of memory, that's not only more than you can fit on any single computer it's hugely more than you can fit on this planet. $\endgroup$ – dave_thompson_085 Mar 13 '15 at 23:22
  • $\begingroup$ @dave_thompson_085 Or even in this universe... $\endgroup$ – Thomas Mar 14 '15 at 2:57
  • $\begingroup$ @Stephen Touset , Actually it would be fairly easy for me to find all the primes between 616 digits and 1233 digits. It wouldn't be rapidly but it would find them all. $\endgroup$ – user24719 Mar 19 '15 at 3:35
  • 3
    $\begingroup$ @user24719 "it wouldn't be rapid" is an understatement, there physically wouldn't be enough energy in the entire universe to carry out the computation. $\endgroup$ – Thomas Mar 19 '15 at 23:17
  • $\begingroup$ Nor enough storage capacity to record them all. $\endgroup$ – Stephen Touset Mar 20 '15 at 17:16

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