Re: Mersenne: Trial Factoring: Back to the math.
Bruce Leenstra wrote: > What this list needs right now is a nice juicy math debate, so here goes: > I was reading the faq about P-1 factoring, and it talks about constructing a > 'q' that is the product of all primes less than B1 (with some multiples?) > ... > > Right now Prime95 constructs a list of possible factors, filters it (before > hand, or on-the-fly) and then uses the powering algorithm to calculate 2^p - > 1 (mod q) for each factor. Off-the wall question dep't.: How does the overhead for that compare to just calculating q, the product of all the primes of interest, and then gcd(q, target)? If you get 1, then q and target have no common factors. If you get anything else, your result is the product of the common factors. Clearly this can be an expensive calculation for large values of q and target, but then interatively testing all the primes isn't remarkably cheap either. _ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Lucas Wiman Mersenne Prime FAQ
[EMAIL PROTECTED] wrote: > > Forgive my ignorance but; > > In reading the Lucas Wiman Mersenne Prime FAQ I became confused at the Q5.3 > instruction. (see FAQ insert below). > > I want to know how many decimal digits are in a given MP. The FAQ seems to be right about the exact answer, once the exponents/digits typo is fixed. A handy approximation is: 10^3 = 1000 ~= 1024 = 2^10 So ten binary digits are slightly more than three decimal digits. Of course for large numbers, this is fairly innaccurate. 10^300 is quite a bit less than 2^1000, for example. 1.024^100 times less to be exact. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Slow CPU's in a Proliant 2500
Matt Goodrich wrote: > > I have just upgraded a Proliant 2500 from dual PPro 200's to dual Pentium II > 333 overdrive processors. ... > Now before I upgraded, I was running double check's on 2 exponents, 668. > I was getting about .515 second iteration times. > Now that I have upgraded, I am only getting .448 second iteration times. Might it just be the effect of slower cache? As I recall, the numbers were: P Pro256 or 512K one CPU clock to deliver data P II 512 K two Celeron 128 K one and on some tasks, Celeron outperforms P II at the same clock because of this. If the process is cache-bound and key data fits in both caches, this gives about the right numbers. P II cache runs at 333/2 which is to 200 roughly as .448 is to .515. Alternately. do you just need a differently optimised version of the code to get the best out of your P IIs? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: More P4 timings
[EMAIL PROTECTED] wrote: > > > At 08:07 PM 4/26/01 +0200, you wrote: > > [sniped] > > >> > > >> 1.4GHz P4, old code:0.126 sec. > > >> 1.4GHz P4, new code:0.048 sec. A bit less than a 3-to-1 improvement, since a third of .126 would be .42. > > >> 1.2GHz Athlon, 133MHz DDR: 0.084 sec. > > >> > > >> I have a few more optimizations up my sleeve. I think my goal > > >> of 0.040 seconds is achievable. > > Hey George: > > When will we begin to see this improved code in action? This would seem > to cut a 10 million exponent LL test time almost 280 hours, which is quite a > savings, and an increase to total throughput for the project. In the time I > can clear one exponent, it could now clear about 4.5 exponents. So how do you come to expect 4.5-to-1? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: [Fwd: P1363: Primality prover]
Is this of use here? Original Message Subject: P1363: Primality prover Date: Mon, 22 May 2000 06:27:24 +0200 From: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] - This is a stds-p1363 broadcast. See the IEEE P1363 web page (http://grouper.ieee.org/groups/1363/) for more information. For list info, see http://grouper.ieee.org/groups/1363/maillist.html - A beta release of CERTIFIX (a primality proving program I am writing) is available. It is based on the Goldwasser, Kilian & Atkin algorithm. CERTIFIX is an executable for Win95, Win98, NT (hardware Intel compatible). It is a freeware. Currently, it can certify a 1024 bit integer in less than 10 mn (AMD K6-2/450 processor). Download link: http://www.znz.freesurf.fr/files/certifix.zip (300 Kb) The package contains the 5 following files certifix.exe certifix.hlp readme.txt todo.txt changes.txt There is no "install" program. Just copy the files in the folder you want and click on CERTIFIX.EXE. Marcel Martin _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Fwd: Re: Mersenne: Re: Base e arithmetic
Pierre Abbat wrote: > Gosper's representation uses seven digits, the sixth roots of 1 and 0, > in base 2.5+sqrt(-3/4). Where do I find out more about that? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Are these lemmas useful?
Here's something I posted in 1996 to sci.crypt.research, now with some typos corrected. It produced little reaction there. I'm hoping someone here can see how to apply it to factoring, or perhaps just to the Mersenne case. --- forwarded message - Like many others I've been trying for some time to find a fast factoring algorithm and/or to break RSA. Not too surprisingly, I haven't succeeded ( yet? :-). I have, however, proved a couple of little theorems which I haven't seen in the literature. Can anyone: find errors in my proofs? tell me if they're original? apply them to factoring? Fermat's little theorem is that for any prime p and integer i: i^p == i mod p My 1st lemma generalises this to: i^(p^n) == i mod p The proof is by induction. Fermat gives us the i = 1 case. For the induction step: i^(p^n) = i^(p*p^(n-1)) = (i^(p^(n-1)))^p but by hypothesis (i^(p^(n-1))) == imod p so i^(p^n) == i^p mod p == imod p QED My 2nd lemma applies to a strong prime s s = 2r + 1 r,s both prime I'll also assume r odd, ignoring the r=2, s=5 case. Fermat gives us: i^s == imod s and for non-zero i: i^(s-1) == 1mod s i^2r == 1mod s but we also have n^r == nmod r (Fermat) n^s == n^(2r+1) == n^3 mod r so n^s = n^3 + kr for some integer k But n^s and n^3 both have the parity of n so kr must be even So if r is odd (if s > 5), k must be even. Which gives us: n^s = n^3 + 2jr for some int j or n^s == n^3 mod 2r whence i^(n^s) == i^(n^3) mod s Which is my 2nd lemma. end forwarded message -- The second lemma can be generalised to the case where s = 2r + t with s and t prime, i^(n^s) == i^(n^(t+2))mod s which reduces to the above if t = 1. I thought at one point this led to factoring N = xy with x, y prime. Very likely for some t you have: x = 2a + t y = 2b + t with a and b prime, in which case i^(n^xy) simplifies nicely. Unfortunately I couldn't find an efficient way to discover t. Can anyone suggest a method for that, or apply the lemmas in some other interesting way? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Prime search on SMP Linux
I'd like to search for Mersenne primes on my SMP Linux box. Info on the search is at: http://www.mersenne.org/prime.htm Machine is a dual Celeron 466, 256 megs. It is my server, basically single-user, powered up 24/7 and I'm not there all time. RedHat 6.1, 2.2.x kernel. I'd like to run one copy of the search code in such a way that it monopolises one CPU, in hopes it will succeed relatively quickly. Is there a way to do that? I'd also like to run a second copy at low priority, set up so it will not interfere with either the primary prime searcher or anything else I want to do with the machine. I'm assuming here that there's no multi-threading in the search code, that it would not be useful to try and run one search using both CPUs. Is that accurate? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
