[Ecm-dev] Proposal from George. Literally.

Alexander Kruppa 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>
> 
>    http://www.mersenneforum.org/showthread.php?t=4074
> 
>    I think it's a splendid idea!
> 
>    Alex
> 
> [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 
into it.


> 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?
> 
> Paul

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 
factors may

So I'd like to propose this interface:

int ecmStage1 (
double k,
unsigned long b,
unsigned long n,
long c,
unsigned long B1,
unsigned long B1done,
int sigma_is_A,
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


Comments?

Alex




Plus d'informations sur la liste de diffusion Ecm-discuss