Primo

[Stargate38]

Yeah. It cost me $600 + Kaspersky Internet security. I've switched to MSE (Security Essentials) so I wouldn't have to pay an annual subscription fee. It was worth it though. AFAIK, I have no viruses atm. However, I need some help. Can someone please tell me what causes these symptoms?:

1. I drag an artwork image to iTunes and the computer freezes.
2. I try to hard reset and reboot, but the Windows Aero process (dwm.exe) won't start.
3. I get read errors on system files.
4. I try to reboot again, but it freezes on the "Starting Windows" screen (the graphics don't appear, just the text).
5. I use a Linux Boot Disc to try and copy my files to an external hard drive, but I get one of the following errors: "Input/Output error", "Value too large for defined data type" on some of them.

What causes this? How do I fix it? Until I do, I have to run Windows in a VM using Virtualbox. It just isn't the same. I can't play my favorite racing game (Midtown Madness 2) without having to set the graphics to "Software (no 3D Video Card)".

[paulunderwood]

Sounds like a bad disk, but I could be wrong.

Check the cables are plugged in snuggly. Back up your data and run some disk checks from UBCD, is my advice. I had one go bad recently -- it had problems writing super blocks when installing Gentoo -- it would not run mkfs.ext3 cleanly.

[Andi_HB]

You can try to boot in Safe Mode. http://www.redmondpie.com/how-to-boo...s-8-safe-mode/
After this backup your Data.
Then to Run CHKDSK http://windows8themes.org/how-to-run...windows-8.html
Hope it works for you.

[Stargate38]

I have Windows 7, not 8. I got this computer in 2010.

[henryzz]

Originally Posted by VBCurtis

Computers often crash more often than every 5-6 years when you get your music from google searches. It's a good thing you got a new computer- the newness does prevent crashes, after all.

If it happens for that sort of reason you reinstall windows rather than getting a new one. I personally find it best to reinstall every couple of years anyway as windows seems to get slower the longer it is installed.

[yoyo]

Originally Posted by bearnol

Correct. Also if you use the latest source (atkin243) it should be identical between different OSs
J

I'll try to Boincify the source and create a Boinc application out of it. I enclose the changes with #ifdef BOINC. Currently the input/output is handled via stdin/stdout, don't know if I have to change this also. Additional the application exits with something != 0 if e.g. the number is a composite. This I have also to change.
When I'm done, I'll send you the changed source.

BTW: Why is the source named atkin?

yoyo

[bearnol]

That would be like calling the GMP-ECM source "lenstra243" :)

[Batalov]

Originally Posted by Stargate38

Yes, I'm sure that I will still have a 32-bit Windows VM at the time, even if 128 or even 256-bit operating systems are around, but I just want to know when on Earth he is going to make another Windows version! How in this entire universe do I get the source code from him?! Do I have to send him an E-mail or something? When is he ever going to make Primo open-source? Sorry about all those hard-to-answer questions, but I really want Marcel to make another Windows version!

That (snapshot below) will surely get him to finally reply to you.

I don't think you will like his answer, I am afraid.

[henryzz]

You surprised me for a minute there. primeprover is my other(newer) username. I got fed up of people calling me henry.

[danaj]

Originally Posted by yoyo

I compiled gmp-ecpp on a Linux 64 bit system, but didn't got it static compiled, libgmpxx.a is missing. Is there a way to get a static version of it for Suse Linux?

How long does it needs to compute a prp certificate for a 500 digit prp?

yoyo

I'm not sure how much people care, but I have an open source ECPP implementation that is much faster than GMP-ECPP, and doesn't use gmpxx. It runs on 32-bit and 64-bit machines, including Win32 (command line). It would take a little massaging to turn into a standlone program (it is part of a Perl module now). If anyone wanted, I could do it. Average times for 500-digit PRP's is about 60 seconds, with certificate. I could also have a standalone program optionally link into GMP-ECM for the factoring.

It uses FAS with a fixed list of polynomials (either 500 or 2650 depending on whether you want the data size to be 35k or 1.2MB). The fixed list makes it fast when it can find factors, but as the size increases the chances are higher that it can't find factors quickly. Under 200-digits this is a non-issue as they're easy. The killer is level 0 since we can't backtrack. I wouldn't really recommend it for 1000+ digits unless you could handle waiting. It's also all single-core. The list of future enhancements is long.

Note that I had the advantage of writing my software after GMP-ECPP and GMP-ECM, had plenty of help from open source, books (e.g. Cohen), and lots of free articles available. It also doesn't come close to Primo, nor is that my target. Honestly I just wanted something than my BLS75 theorem 5/7 prover.

The certificates are easily described and the package contains a verifier (though both this ECPP and the verifier were written by the same person, so not ideal). Turning on verbose level 2 will make it output info similar to GMP-ECPP. The package includes an example program that takes GMP-ECPP output, converts it my certificate format, and runs it through the verifier.

Example 800-digit prime:

time perl -MMath::Prime::Util=:all -E 'prime_set_config(verbose=>1); my $n = random_ndigit_prime(800); say $n; my @cert = prime_certificate($n); say verify_prime(@cert);'
20443987985371566596196383035718301138174118185136736375705779502458572404079683337575649740211923543213839529101164807557895801091978585791974909550613164362845341198040458739088508085522277836083292077295057923913065207050715309876775997788289639660920939398400557690622108987139017387065179009994753379841185175425332623391136828022411037251049960076666776932000965866533734635780713134375834400742680057742212425454137230636013373166544738117887409423965569892090142198678900295557491760413057820608924605597955981164954891731105768573393261277499398151053969858546968985985530589739362587656228607497576381292050092944318149269465630547308922229724354728462102870709764369637421445463969412230511360022061146542697354493388050102621598092795803193704863955475238284185417352123117048327111186721
N[0] (800 dig) -120 (Hilbert 4)
 N[1] (797 dig) -6451 (Hilbert 17)
  N[2] (795 dig) -907 (Hilbert 3)
   N[3] (789 dig) -7828 (Weber 16)
    N[4] (774 dig) -627 (Hilbert 4)
     .....
    N[4] (774 dig) -627 (Hilbert 4)  2
   N[3] (789 dig) -7828 (Weber 16)  2
  N[2] (795 dig) -907 (Hilbert 3)  2
 N[1] (797 dig) -6451 (Hilbert 17)  2
N[0] (800 dig) -120 (Hilbert 4)  2
1

real    5m19.085s
user    5m18.658s
sys    0m0.009s

Primo 4.0.1 on my machine took a bit under 17 seconds for this number using 12 cores. With 1 core it was 73 seconds. For this number my program only had to backtrack from the first factoring level 3 times, so it could have been much, much worse. Primo has so many more discriminants available that numbers this size are simple.

[danaj]

BTW: Why is the source named atkin?

Because Cohen's Algorithm 9.2.4 is named "Atkin". It looks like the authors followed that book for most of the code (which is not a bad thing -- it's a very nice book).

Originally Posted by yoyo

I'll try to Boincify the source and create a Boinc application out of it. I enclose the changes with #ifdef BOINC. Currently the input/output is handled via stdin/stdout, don't know if I have to change this also. Additional the application exits with something != 0 if e.g. the number is a composite. This I have also to change.
When I'm done, I'll send you the changed source.

Some suggestions off the top of my head for GMP-ECPP:

- there is a big error in the polynomial root finder. I recommend looking at Cohen 1.6.1 and fix the code (IIRC, it's looping when it shouldn't). This would be a requirement if it were changed to FAS, as the existing code often fails when it shouldn't.

- There is an off-by-one error somewhere in the polynomial gcd code. It's worked around using some extra ifs, so not a huge concern unless you want to rewrite it.

- The fixed POLY_SIZE for the poly code is obtrusive. It'll blow out your stack if you have too many steps, and it's set too high for most use. Reducing it will make things run faster, but leads to other issues.

- Use GMP-ECM for factoring (best), change to a projective ECM, or use a good p-1 for stage 1. I do the latter, as my p-1 factoring is far faster than my ECM and usually finds what we need without much effort. I eventually move to ECM if necessary, which is when you really want something faster than the affine ECM in GMP-ECPP.

- precalculate at least some of the class polynomials. Maybe all the degree 1 and 2s. That will mean almost no class poly calcs once you get under 200 digits.

- Don't use a master switch for Hilbert vs. Weber. Find out if you can use Weber and use it if so, and Hilbert if not. I believe there's no good switch to control the Weber polys used, so it will waste lots of time using bad polys.

- Investigate the various papers that discuss how to estimate the precision needed to generate the polys and use them (plus a fudge factor if you want). Right now it has a global precision limit, which is not scalable at all (either it is small and then big numbers don't work, or it's big and you waste crazy amounts of time on smaller polys).

- polynomial multiplication via binary segmentation would be better with GMP. This probably isn't a big deal with this algorithm/code. It was *huge* with my AKS implementation, but probably not worth much here (it's also more clearly applicible to AKS).

Don't get me wrong -- I think it's fantastic that they wrote a working ECPP and published it as open source. It does great with numbers that start making n-1 provers take a long time (80-100 digits), and given time it will do 150-200 digit numbers. But it has room for improvement.