new factors

[Greenbank]

1125899916781741 | 21181*2^23496647+1
1125899921400869 | 24737*2^21400869+1

2 karma points if they spot anything interesting about those p.

(Don't get too excited, this is in development and nowhere near as fast as proth_sieve).

P.S. I know they are duplicates, but the important thing is p.

[Joe O]

They are beyond the pale!















>2^50

[Greenbank]

Indeed.

My siever is running at a massive 41 p/sec (on the same machine that does 440 kp/sec with proth_sieve).

It does very simple Baby-Steps Giant-Steps to solve the appropriate discrete logs for each k-value.

I'm looking into Pohlig-Hellman but all of the algorithms I've found on the internet are all slightly different and I'm a bit lost with it all.

I'm hoping that there's some aspect of Pohlig-Hellman that allows me to quickly work out that p will never factor k*2^n+1 whatever n is used. I think it might be looking at the low factors of p-1 (i.e. below 100) that, through Pohlig-Hellman, will result in an unsolvable discrete log which should be very quick to check. Anyway, more reading required.

I've also got to look for a good mul_mod algorithm (i.e. (a*b) mod p ) where a,b and p are all <64bit. I have to use the GMP library (swox.com/gmp) for this as the result of the multiplication could be up to 128 bits and no basic types in C handle this.

The direct mpn_ functions in GMP may speed it up a bit more, but I don't know how I'm going to make it go 10000 times faster to catch proth_sieve ;-)

The resulting x86 assembly (using gcc -S) doesn't look as good as it could be, but then I don't want to delve into the assembly world.

I've posted a few questions in places where I know Paul Jobling and Mikael Klasson lurk but no luck yet.

[Joe O]

Would you please check the speed of this program on your machine.

[Greenbank]

The machine I was running it on was a linux box (P4 3GHz non Xeon).

The only Windows machine I have is a dual 3GHz Xeon and that is running sbclient (secondpass).

When I did try and run it on that machine used up about 2 seconds of cpu time and then stopped itself. I did this on both a 'normal range' 882T to 883T and a > 2^50 range.

As an aside, Phil Carmody has replied to one of my posts so I'm off to investigate how Jacobi symbols can help speed up my program.

[garo]

Also, there is a discussion going on in this thread that may be useful to you.
http://www.mersenneforum.org/showthread.php?t=4310

[Joe O]

Originally posted by Greenbank
The machine I was running it on was a linux box (P4 3GHz non Xeon).

The only Windows machine I have is a dual 3GHz Xeon and that is running sbclient (secondpass).

When I did try and run it on that machine used up about 2 seconds of cpu time and then stopped itself. I did this on both a 'normal range' 882T to 883T and a > 2^50 range.

As an aside, Phil Carmody has replied to one of my posts so I'm off to investigate how Jacobi symbols can help speed up my program.

Oops, wrong program. This program has been running for years. I used it for all the high p ranges that I have done. Both AMD and Intel machines. At the very high p ranges it takes a very very long time to initialize but it does work and has found factors there.

[Joe O]

Those with older machines that do not have the cmov instruction sets may find this program of interest.

By the way, all three of these program were written by Paul Jobling and have been used by this sieve effort before.

[vjs]

I believe newpgen also works above 2^50 as well. The problem of course is speed, it's also important to note that proth does not miss any factors, AFAIK.

Some early implementations of some programs missed factors this is the worst possibile senario.

Greenbank all I can say at this moment is code for fun and post anything you want to share in the forum. You might have a unique insite if you work it through on your own etc.

[Greenbank]

Yup, my code is for fun. I doubt it will ever be anywhere near as fast as the others but it's interesting to play around.

While I do this I still have one machine running sbclient, and two machines sieving.

In doing this I've learn a lot about how exp_mod works, Galois Fields, discrete logs, Jacobi/Legendre symbols, quadractic reciprocity, etc.

It's going to make the first year of my maths degree (with the Open University) a lot easier. (Already have a Comp Sci degree).

[Greenbank]

I'll try the other program tomorrow. My windows machine is busy doing work stuff at the moment (boo!).

In other news I've realised why my sieve was so slow compared to the others (65p/sec compared to 440000p/sec for proth_sieve).

When I was calculating p/sec I was calculating how many actual primes I'd sieved per second. proth_sieve counts non-primes too (even though it doesn't bother sieving with them).

After fiddling the calculations my siever is now running at around 1800p/sec. Only need to make it 300 times faster now ;-).

I'm now doing a horribly implemented Pohlig-Hellman style check to remove k,p candidates on factors of p-1 less than 10000.

Going to look at the Index Calculus method to see if that can offer any (big) improvements.