Mersenne: Distribution of factors among congruence classes

Hi all, I wrote a little program to show the distribution of factors among congruence classes, especially (mod 8) and (mod 120) (all others were as uninteresting as you would expect). What surprised me was that the distribution is not smooth at all, some congruence classes contain a lot more

Re: Mersenne: ECM question

Hi all, I have a different question concerning P-1 and ECM. Some time ago I asked which power to put small primes into when multiplying them into E ( factor = gcd(a^E-1,N) ). Paul Leyland, I believe, replied that the power for prime p should be trunc( ln(B1) / ln(p) ) ( log(B1) with base p ),

Mersenne: Worth it?

Hi, from stuff I saw on the list earlier I put together this estimate: The chance for Mp being prime if it has no factor below 2^q is 2q/p (if q is reasonably big, at i.e. 2^q much bigger than 2p+1). If we test the Mersennes in the 10M-digits range for factors to, say, 2^80, the chance for,

Re: Mersenne: Worth it?

Lucas Wiman wrote: P-1 factoring is based upon Fermat's little theorem which states that [...] What if we use 2 as a base? Well, for mersenne numbers, this might be to The problem is that 2 is not a primitive root (mod Mp). From a computers point of view, the mod Mp operation is a rotate

Mersenne: Factoring 2^n+1 and 2^n-1

Hi, Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1 numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity 2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much longer than on 2^n-1 of the same size.. That

Mersenne: Combining Prime95 and gmp-ecm

Hi, gmp-ecm version 5 can read ECM residues written by Prime95 to perform stage 2 on them. Stage 2 is asymptotically faster in gmp-ecm, but Prime95 has a much faster multiplication for large numbers, so this feature is mostly interesting for relatively small numbers (i.e. of a few thousand bits)