Menu
▾
▴
Re: [flint-devel] Square-Free Algorithm
|
From: Bill H. <goo...@go...> - 2008-08-01 02:19:36
|
Hi Richard,
I noticed here that you have a function for raising a polynomial to a
power modulo another poly. I just added such a function to zmod_poly
which should be more efficient. It uses the repeated squaring trick.
It is called zmod_poly_powmod. I also added a function for multiplying
two polynomials modulo another, called zmod_poly_mulmod.
Bill.
2008/7/15 Richard Howell-Peak <ric...@gm...>:
> I agree, the goto's are not very nice it's just how the algorithm was
> written in the paper. I've basically got some code for doing the other
> stuff, you can have a look at it here. Obviously none of it's optimised but
> I'd quite like to get a working version of Berlekamp as soon as possible
> then worry about optimisation later.
>
>
> /**
> * Initialises an array of zmod_poly's
> */
> void zmod_poly_arr_init(zmod_poly_arr_t arr, unsigned long p)
> {
> arr->len = 1;
> arr->used = 0;
> arr->factors = (zmod_poly_t*) malloc(sizeof(zmod_poly_t));
> zmod_poly_init(arr->factors[0],p);
> }
>
> /**
> * Initialises one of specified length
> */
> void zmod_poly_arr_init_len(zmod_poly_arr_t arr, unsigned long p, unsigned
> long length)
> {
> arr->len = length;
> arr->used = 0;
> arr->factors = (zmod_poly_t*) malloc(sizeof(zmod_poly_t) * length);
> for(unsigned long i=0; i< length; i++)
> zmod_poly_init(arr->factors[i],p);
> }
>
> /**
> * Frees up memory being used
> */
> void zmod_poly_arr_free(zmod_poly_arr_t arr)
> {
> free(arr->factors);
> arr->len = 0;
> arr->used = 0;
> }
>
> /**
> * Adds an extra element to the array
> */
> void zmod_poly_arr_add(zmod_poly_arr_t arr, zmod_poly_t add)
> {
> //how much space left in the array?, if none make a new one twice as big
> (for efficiency) and copy contents across
> if(arr->len == arr->used)
> {
> zmod_poly_arr_t temp;
> zmod_poly_arr_init_len(temp, zmod_poly_modulus(add), arr->len * 2);
> //copy it across
> for(unsigned long i=0; i < arr->len; i++)
> {
> zmod_poly_set(temp->factors[i], arr->factors[i]);
> }
> //add in the extra one
> temp->len = arr->len*2;
> zmod_poly_set(temp->factors[arr->used], add);
> temp->used = 1 + arr->used;
> zmod_poly_arr_free(arr);
> arr[0] = temp[0];
> } //plenty of space left, just add it to the end
> else
> {
> zmod_poly_set(arr->factors[arr->used], add);
> ++arr->used;
> }
> }
>
> /**
> * Concatenates array res to equal array res + add
> */
> void zmod_poly_arr_cat(zmod_poly_arr_t res, zmod_poly_arr_t add)
> {
> for(unsigned long i=0; i < add->used; ++i)
> zmod_poly_arr_add(res, add->factors[i]);
> }
>
> //Getters and Setters
> /**
> * Get the number of elements currently in the array
> */
> unsigned long zmod_poly_arr_get_size(zmod_poly_arr_t arr)
> {
> return arr->used;
> }
>
> /**
> * Gets the product of all the factors
> */
> void zmod_poly_arr_product(zmod_poly_t result, zmod_poly_arr_t arr)
> {
> zmod_poly_init(result, zmod_poly_modulus(arr->factors[0]) );
> zmod_poly_set_coeff_ui(result, 0 , 1);
> for(unsigned long i=0; i < arr->used; ++i)
> zmod_poly_mul(result, result, arr->factors[i]);
> }
>
> /**
> * Dumps the array to stdout
> */
> void zmod_poly_arr_print(zmod_poly_arr_t output)
> {
> printf("\n");
> for(unsigned long i=0; i < output->used; ++i)
> {
> zmod_poly_print(output->factors[i]);
> printf("\t");
> }
> printf("\n");
> }
>
> /**
> * Prints the product of all elements in the array
> */
> void zmod_poly_arr_print_res(zmod_poly_arr_t output)
> {
> zmod_poly_t res;
> zmod_poly_init(res, zmod_poly_modulus(output->factors[0]));
> zmod_poly_set_coeff_ui(res, 0, 1);
> for(unsigned long i=0; i < output->used; ++i)
> {
> zmod_poly_mul(res, res, output->factors[i]);
>
> }
> zmod_poly_print(res);
> }
>
> /**************************** Utility functions for zmod_poly's
> *****************/
>
>
> /**
> * Returns the derivative of a polynomial mod p, where p is the prime
> * that is already associated with the polynomial x.
> * <p>
> * This is done in a very naive way, simply going through the polynomial
> * differentiating term by term reducing the product mod p each time
> *
> * @param zmod_poly_t The polynomial to be derived
> * @return The derivative of the original polynomial
> */
> void naiveDiff(zmod_poly_t x_primed, zmod_poly_t x)
> {
> //Now we compute the derivative in a very naive way :)
>
> unsigned long degree = zmod_poly_length (x);
> long length = zmod_poly_degree (x);
>
> zmod_poly_init( x_primed , zmod_poly_modulus(x));
> for (unsigned long i=1; i<degree; i++)
> {
> unsigned long coeff = zmod_poly_get_coeff_ui ( x , i);
> unsigned long newCoeff = i*coeff;
> zmod_poly_set_coeff_ui ( x_primed, i-1, newCoeff);
> }
> }
>
>
> /**
> * This is slightly more efficient but basically does the same thing
> */
> void zmod_poly_diff(zmod_poly_t x_primed, zmod_poly_t x)
> {
> //get the degree of the polynomial we are working with
> unsigned long degree = zmod_poly_length (x);
> //make sure new poly is in the same base
> unsigned long p = zmod_poly_modulus(x);
> zmod_poly_init( x_primed , p);
> unsigned long coeff;
> //Loop through and diff term by term
> for (unsigned long i=1; i<degree; i++)
> {
> coeff = zmod_poly_get_coeff_ui ( x , i);
> if(coeff!=0)
> zmod_poly_set_coeff_ui ( x_primed, i-1, (i%p) *coeff);
> }
> }
>
>
> /**
> * Repeated square algorithm, efficiently computes a to the exp mod <f>
> using the repeated square method
> */
> void zmod_poly_repeated_square(zmod_poly_t res, zmod_poly_t a, unsigned long
> exp, zmod_poly_t f)
> {
> //unefficient way, quick fix:
> zmod_poly_t a_exp,temp;
> zmod_poly_init(a_exp, zmod_poly_modulus(f) );
> zmod_poly_init(temp, zmod_poly_modulus(f) );
> zmod_poly_init(res , zmod_poly_modulus(f) );
>
> zmod_poly_set(a_exp,a);
> for(unsigned long i=1; i<exp; i++) //calculate a_exp = a^exp
> zmod_poly_mul(a_exp ,a_exp ,a);
> //for A = QB + R we get divrem(Q, R, A, B);
> zmod_poly_divrem( temp , res, a_exp , f );
> }
>
> /**
> * Raises a polynomial to the nth power
> * Sets res to f^n
> */
> void zmod_poly_power(zmod_poly_t res, zmod_poly_t f, unsigned long n)
> {
> zmod_poly_set(res, f);
> for(unsigned long i=1; i < n; ++i)
> zmod_poly_mul(res, res, f);
> }
>
> --
> Richard
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>
>
|
