[Ecm-dev] Proposal from George. Literally.

George Woltman woltman at alum.mit.edu
Mer 11 Mai 16:26:16 CEST 2005

I've hacked at the code and am ready to start integrating it with 
GMP-ECM.  I won't
have time to work on it today, but tomorrow I'll download mingw and see if 
I can get
the two to link together.

A few minor issues came up.

1)  In case of user interrupt, I want to return both x and z to write to a 
save file.
Normalizing the coordinate, especially during system shutdown, could take 
too long
for large numbers.

2)  I've added an option to force the code to do stage 1 for the 3 multiply 
reduction case (b <> 2).  While it won't make sense for Cunningham numbers, it
might make sense as numbers get very large.  I don't expect you'll use this 
option now.

3)  I've added a way to pass in an arbitrary number for the 3 multiply
generic reduction case (set k=b=n=c=0).  Again, probably for use at a later
date (or never).

/* Return codes */

#define ES1_SUCCESS             0       /* Success, but no factor */
#define ES1_FACTOR_FOUND        1       /* Success, factor found */
#define ES1_CANNOT_DO_IT        2       /* This k,b,n,c cannot be handled */
#define ES1_MEMORY              3       /* Out of memory */
#define ES1_INTERRUPT           4       /* Execution interrupted */
#define ES1_CANNOT_DO_QUICKLY   5       /* Requires 3-multiply reduction */
#define ES1_HARDWARE_ERROR      6       /* An error was detected, most */
                                         /* likely a hardware error. */

/* Option codes */

#define ES1_DO_SLOW_CASE        0x1     /* Set this if ecmStage1 should */
                                         /* do slow 3-multiply reduction 
cases. */


Input number (3 possibilities):

1) k,b,n,c set and num_being_factored_array = NULL.  k*b^n+c is factored.
2) k,b,n,c zero and num_being_factored_array set.  num_being_factored is
    worked on using generic 3-multiply reduction
3) k,b,n,c set and num_being_factored_array set.  num_being_factored is
    worked on - it must be a factor of k*b^n+c.

A_array, B1 are required

B1_done is optional.  Use it to resume a stage 1 calculation.

x_array, z_array is the starting coordinate.  If z_array is not given, then
z is assumed to be one.

stop_check_proc is optional

options are defined above


On success:

x_array is set to normalized coordinate

On factor found:

x_array is set to the factor found

On interrupt:

B1_done is set to the last prime below B1 that was processed
x_array and z_array are set to the current coordinate.  The (x,z) coordinate
is not normalized because it will be slow for large numbers.  This is
unacceptable during system shutdown.  Caller must allocate x and z arrays
large enough to hold any k*b^n+c value.


int ecmStage1 (
         double  k,                      /* K in K*B^N+C */
         unsigned long b,                /* B in K*B^N+C */
         unsigned long n,                /* N in K*B^N+C */
         signed long c,                  /* C in K*B^N+C */
         unsigned long *num_being_factored_array,        /* Number to factor */
         unsigned long num_being_factored_array_len,
         unsigned long B1,               /* Stage 1 bound */
         unsigned long *B1_done,         /* Stage 1 that is already done */
         unsigned long *A_array,         /* A - caller derives it from sigma */
         unsigned long A_array_len,
         unsigned long *x_array,         /* X coordinate */
         unsigned long *x_array_len,
         unsigned long *z_array,         /* Z coordinate */
         unsigned long *z_array_len,
         int     (*stop_check_proc)(void),/* Ptr to proc that returns TRUE */
                                         /* if user interrupts processing */
         unsigned long options) 

No virus found in this outgoing message.
Checked by AVG Anti-Virus.
Version: 7.0.308 / Virus Database: 266.11.8 - Release Date: 5/10/2005

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