[Ecm-dev] Proposal from George. Literally.
alexander.kruppa at mytum.de
Ven 6 Mai 23:27:54 CEST 2005
Paul Zimmermann wrote:
> Date: Fri, 06 May 2005 21:24:14 +0200
> From: Alexander Kruppa <alexander.kruppa at mytum.de>
> I think it's a splendid idea!
> [George, I answer by email since I do not read regularly mersenneforum.]
> Indeed! About the k*b^n+c form, can prime95 deal with b<>2?
Not yet, but in an earlier mail George mentioned that he plans to look
> Recognizing such a form is easy if k=1 and b is not too large,
> but for general k I have to think about it.
As long as the user passes the number as an expression of this form
(k*b^n+c), the expression parser could return the relevant parameters to
the callee. We'd probably have to keep some flags in the save file
entries so the DWT works when resuming. None of this would be hard to do.
> Also, I don't see why 2) is simpler than 1). 2) will also require to
> have several optimized prime95.dll for different machines, no?
> Assuming 2), for which configurations will you provide prime95 libraries?
> Windows, MacOS, Linux? x86, powerpc, x86_64?
Prime95 only works on x86 architecture, the performance relevant
functions are written in hand-optimized assembler. I looked at the GWNUM
library for factoring Fermat numbers with GMP-ECM 6.0, it can autodetect
the cpu type at run time. It's pretty conventient to use.
Using the ECM stage 1 code of Prime95 has the advantage that we'd get to
use a stage 1 that is highly optimized for FFT multiplication, and it's
ready to go - except for the interface, no new code will need to be written.
About the interface: GMP-ECM would like to be able to pass either the
sigma or A paramter for the curve. For resuming, we'd need to be able to
pass the x-coordinate of the point to start with (also needed if the
curve is specified by A). For the -go option, we'd have to be able to
pass an arbitrary precision integer that the initial point get
multiplied by. And for resuming, we'd need a B1done parameter, so that
only primes and prime powers B1done < p^k <= B1 are processed. And
So I'd like to propose this interface:
int ecmStage1 (
unsigned long b,
unsigned long n,
unsigned long B1,
unsigned long B1done,
unsigned long *sigma_or_A,
unsigned long *num_being_factored_array,
unsigned long num_being_factored_array_len
unsigned long *x_array,
unsigned long *x_array_len
unsigned lont *go_array,
unsigned long go_array_len)
Stage 1 should compute the A parameter from sigma if sigma_is_A == 0,
otherwise read A directly. If *x_array_len == 0 and sigma_is_A == 0, the
starting point x should be computed from sigma, if *x_array_len != 0 or
sigma_is_A != 0, the starting point should be read from *x_array. The
combination *x_array_len == 0, sigma_is_A != 0 is illegal.
Then multiply x by the value in go_array, then by
p^[floor(log_p(B1)) - floor(log_p(B1_done))] for all p<=B1.
After all the multiplications are done, normalize the point to Z=1 and
return it via *x_array if no factor was found. If a factor was found,
return that via *x_array.
For the return codes, I'd suggest
0 = success, but no factor
1 = factor found (during sigma->A conversion or normalization)
2 = could not handle this k,b,n,c combination
3 = out_of_memory
Plus d'informations sur la liste de diffusion Ecm-discuss