Prime number support

[zak]

sorry for the delay, i was in a funeral. i will install it again on windows 7 without download anything. and will post a report in a few hours

[zak]

i must say that i don't use mathematica normally, some times years lapsed without using it until i buy a new pc, to see how much my new pc are speedy in calculating Pi to a million digits, and to a 10 million digits. but this may change after the new features.
mathematica v8.0.0 installation file size = 883 MB
i have checked the size of the installed mathematica on windows xp and it was 2,78 GB, and most of it is a documentation in the .nb file format. the main exe's are math.exe (158 KB), mathematica.exe (1.25 MB), MathKernel.exe (459 KB), Documentation files 1.49 GB,
systemFiles 1.25 GB, AddOns (33 MB), Configuration (107 kb).

before installing it on windows 7 (installed on another primary partition in the same pc) i have disabled the web connection.
after installation it askes for the register or register later so i choose register later, and it works (may be for 15 days).
the timings differ slightly but in practice it is approaching zero. the timings on all programming languages when dealing with less than milli seconds are not absolutly correct because many factors intervene here such as the operating system internal other actions. the 10^-17 seconds can be the result of time calculations algorithm and not the reality.

the same in windows 7 the mathematica size
2.78 GB, 17,073 files, 1,667 Folders

i have tried also Timing[N[Pi,10000000];] and it calculate it in 45 seconds. the ";" after N[Pi,10000000]; is to disable displaying the result which takes more time.
attached the picture from windows 7. i suggest if possible to try it, since it runs for may be 15 days without register.
the 1+1 before the calculations is to force the mathematica to launch its kernel, so the kernel will be available when using Timing.

[danbaron]

The installed version of Mathematica, could also have lists of big primes, yes or no?

[Johannes]

Dan, I was thinking much the same. Calculating a 125-bit next prime in zero seconds is too fantastic for words. You still have to try to factor the number to be absolutely certain and I can't see how they can do that this quickly for such a large number.

Hold the phone.

Zak, are you working with a 64-bit Windows? If so, ask Mathematica to find the next prime after 2^130. Another test would be to repeat the NextPrime for that big number several times. See if the next (say) 100 primes are all determined that quickly.


Having said that, since the approximate number of primes smaller than n is considered to be n/(ln n - 1), there are already 193,600,000 primes smaller than 2^32. Without too much trouble that list can be stored in 122,700,000 bytes (48 bits for every 210 numbers) and with some extra coding that can be decreased even further. But storing all IfPrime bits for 64-bit primes takes a couple of hundred of PETAbytes.


I've looked into the digits of pi thing and those are calculated directly. I downloaded PiFast which uses the Chudnovsky algorithm (How do they come up with these algorithms, let alone prove them to be correct?) and compared to that one Mathematica runs at a snail's pace. Ten million decimals of pi took 24.6 seconds on my machine. My own code, using a fairly optimal Machin-like formula would take (ahem) 104,000 seconds for the same task.

Maybe, if I really am bored I'll try to do the Chudnovsky algorithm as well. There's a square root in there...

[jack]

I also have the home edition of Mathematica but the home edition comes in 32-bit version only.

[danbaron]

I think zak already did this, but, I did it again.

I went to,

http://www.wolframalpha.com/ ,

and, I entered,

"FactorInteger[21130819027319923178509622632727980622577522491335986162202750512019525136688895741633235387039306968582318693021114825649130164135868576427684517893]" .

Super-Mathematica, "choked".

First, it calculated (maybe 10 seconds), and then said,

"Timed out. Try again with more time."

So, I clicked on, "Try again with more time.".

Then, it calculated some more (maybe 20 seconds), and finally gave up, saying,

"Computation timed out. No more results available.".

Apparently, it isn't going to be doing any one hour calculations for you!

(If it could factor numbers like this one, then, governments could use it to break prime number encryption, yes or no? (The number, 211308.., is 493 bits - three factors, but still, 493 bits.))

So, our experience is that it is easier for Mathematica to verify that a large prime, is prime, than it is for it to factor a large composite. What exactly, does that imply?

[zak]

i have tried Dan example , and no it does not factor it quickly, so i interrup it after half a minute. factorizing numbers is known that it is a hard problem in mathematics, and all the economy will collapse if someone discover a way to factor big numbers.
now to Johannes question, my OS is 32bit , either winxp or win 7.
regarding NextPrime of 2^130, i have to remember the looping instruction, so looping the program to 1000 it gives the result in about 4 seconds it is the time of printing the results, i attach the results in a rar file.
the mathematica code like this:

primenum = 2^130;
n = 1;
While[n < 1000, primenum = NextPrime[primenum]; Print[primenum]; n++]

attached a picture from windows xp

[Johannes]

(If it could factor numbers like this one, then, governments could use it to break prime number encryption, yes or no? (The number, 211308.., is 493 bits - three factors, but still, 493 bits.))

So, our experience is that it is easier for Mathematica to verify that a large prime, is prime, than it is for it to factor a large composite. What exactly, does that imply?

Answer to your first question: yes. Every single encryption scheme that is half decent uses the product of (at least) two very large prime numbers. If there was a way to factor that product encryption would die a quick death.

I'm with you on the second question. If they can say whether or not a number is a prime very quickly, but they can't factor at the same speed, then they're not factoring to determine primality. In other words, they must have a list of some sort. Factoring, in one way or another, is required to determine primality.